Способ поиска объекта с использованием устройства верификации и соответствующие устройства

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении защиты идентификации объектов для предотвращения отслеживания объектов третьими лицами. Способ поиска объекта, принадлежащего набору объектов, с использованием устройства верификации, причем устройство верификации и объекты из набора объектов выполнены с возможностью обмена элементами информации по меньшей мере через один канал связи, при этом каждый объект из набора объектов имеет первый соответствующий идентификатор, из которого получают множество представителей, причем в способе получают в устройстве верификации первое идентификационное слово (m_i;р(x_i)), относящееся к объекту, поиск которого выполняется, причем первое идентификационное слово образовано посредством применения первой функции кодирования к первому идентификатору объекта, поиск которого выполняется так, чтобы первое идентификационное слово зависело от подчасти множества представителей, получаемых из первого идентификатора, при этом подчасть определяется с помощью по меньшей мере одного переменного параметра (i), при этом выбирают случайным образом с помощью устройства верификации значение переменного параметра, определяющее подчасть множества представителей, получаемых из первого идентификатора; и передают от устройства верификации первое идентификационное слово, полученное по каналу связи. 4 н. и 10 з.п. ф-лы, 4 ил.

 

Настоящее изобретение относится к поиску объекта, принадлежащего набору объектов.

Под объектом подразумевается любой элемент аппаратных средств и/или программных средств, которые дополнительно могут быть связаны с устройством, системой или индивидуумом. В качестве неограничивающих примеров можно привести тег беспроводной идентификации, такой как RFID-метка (метка радиочастотной идентификации), идентификационная карта доступа, чип-карта, мобильный телефон, компьютер, подсоединенный к сети или др.

Известно использование устройства верификации для нахождения объекта. Последнее может также принимать различные формы в зависимости от типа объектов, для которых предназначен поиск. Устройство верификации может быть, например, считывающим устройством для беспроводной идентификации, таким как устройство считывания REID-меток, датчик, сервер или др.

Устройство верификации и объекты поддерживают связь друг с другом, по меньшей мере, через один канал связи, обеспечиваемый для этой цели, который может быть по требованию проводным или беспроводным.

Согласно первому известному способу, поиск объекта, принадлежащего набору объектов, с использованием устройства верификации выполняют путем передачи, из каждого объекта, по каналу связи соответствующего идентификатора и путем анализа в устройстве верификации принятых идентификаторов для того, чтобы прийти к заключению относительно наличия или отсутствия искомого объекта.

Согласно второму известному способу, поиск выполняют путем передачи, от устройства верификации, идентификатора искомого объекта через канал связи, и затем, если необходимо, путем приема по каналу связи ответа от объекта, который распознал свой идентификатор в этой передаче.

Этот второй способ является более экономичным по сравнению с первым, так как он позволяет ограничить количество сообщений, которыми обмениваются по каналу связи, и обработку, которая требуется устройству верификации для нахождения искомого объекта.

Однако этот второй способ имеет недостатки.

В частности, он не обеспечивает защиту идентичности объектов. В частности, это может быть проблематичным в случае, когда объекты относятся к индивидуумам, так как соблюдение прав частной жизни последних в дальнейшем не гарантируется. Это также проблематично в случае объектов, которые относятся к аппаратным средствам, которые имеют рыночную стоимость и/или финансовую ценность, причем желательно исключить возможность их отслеживания третьими сторонами.

Нарушитель, прослушивающий канал связи, может перехватить идентификатор, переданный устройством верификации, и раскрыть, путем обнаружения посланного ответа, кому принадлежит идентификатор этого объекта.

Задача настоящего изобретения заключается в том, чтобы выполнить поиск объекта при повышении защиты его идентичности.

Таким образом, в настоящем изобретении предложен способ для поиска объекта, принадлежащего набору объектов, с использованием устройства верификации, причем устройство верификации и объекты из упомянутого набора объектов выполнены с возможностью обмена элементами информации, по меньшей мере, через один канал связи, причем каждый объект из упомянутого набора объектов имеет первый соответствующий идентификатор, из которого можно получить множество представителей. Этот способ содержит следующие этапы, на которых:

- получают, в устройстве верификации, первое идентификационное слово, которое относится к объекту, для которого выполняется поиск, причем первое идентификационное слово образовано путем применения первой функции кодирования к первому идентификатору объекта, для которого выполняется поиск, для того, чтобы зависеть от подчасти множества представителей, которые можно получить из упомянутого первого идентификатора, причем упомянутая подчасть определяется, по меньшей мере, одним переменным параметром; и

- передают, из устройства верификации, первое идентификационное слово, полученное по каналу связи.

Использование функции кодирования, позволяющей вырабатывать первое идентификационное слово в зависимости только от одной части представителей, позволяет значительно повысить защиту идентичности объектов по сравнению с предшествующим уровнем техники, упомянутым во введении.

Согласно предпочтительным вариантам осуществления, которые можно объединить всеми предусмотренными способами:

- способ также содержит следующие этапы, выполняемые каждым объектом из упомянутого набора объектов, прослушивающих канал связи, на которых:

- принимают идентификационное слово, соответствующее первому идентификационному слову, переданному по каналу связи; и

- применяют первую функцию идентификации, связанную с первой функцией кодирования, к принятому идентификационному слову и к элементу информации, известному упомянутому объекту среди первого идентификатора упомянутого объекта и, по меньшей мере, одного представителя из множества представителей, которые можно получить из упомянутого первого идентификатора, для того, чтобы верифицировать, соответствует ли упомянутый объект искомому объекту; и/или

- индикация значения переменного параметра, который используется для формирования полученного первого идентификационного слова, передается из устройства верификации по каналу связи, и для каждого объекта из упомянутого набора объектов, прослушивающих канал связи, упомянутое применение первой функции идентификации принимает во внимание идентификацию значения принятого переменного параметра; и/или

- когда результат упомянутого применения первой функции идентификации показывает, что упомянутый объект соответствует отыскиваемому объекту, упомянутый объект отправляет ответ в устройство верификации через канал связи; и/или

- упомянутый объект имеет второй идентификатор, из которого можно получить множество представителей, второе идентификационное слово получается в упомянутом объекте путем применения второй функции кодирования к элементу информации, известному упомянутому объекту среди второго идентификатора упомянутого объекта и, по меньшей мере, одного представителя из множества представителей, которые можно получить из упомянутого второго идентификатора для того, чтобы зависеть от подчасти множества представителей, которые можно получить из упомянутого второго идентификатора, причем упомянутая подчасть определяется, по меньшей мере, с помощью одного переменного параметра, при этом ответ, посланный упомянутым объектом в устройство верификации через канал связи, включает в себя второе идентификационное слово; и/или

- идентификационное слово, соответствующее второму идентификационному слову, включенному в упомянутый ответ, принимают в устройстве верификации, устройство верификации применяет вторую функцию идентификации, связанную со второй функцией кодирования к идентификационному слову, принятому в устройстве верификации, и к элементу информации, известной устройству верификации среди второго верификатора упомянутого объекта и, по меньшей мере, одного представителя из множества представителей, которые можно получить из упомянутого второго идентификатора, для того, чтобы осуществить дальнейшую верификацию соответствия между упомянутым объектом и искомым объектом; и/или

- первая функция кодирования выполнена таким образом, чтобы в случае, когда она применяется к первому идентификатору искомого объекта, упомянутый переменный параметр выбирает, по меньшей мере, один представитель из множества представителей, который можно получить из упомянутого первого идентификатора, причем упомянутое применение первой функции идентификатора содержит сравнение между упомянутым представителем, выбранным с помощью упомянутого переменного параметра и, по меньшей мере, одного представителя из множества представителей, которые можно получить из первого идентификатора упомянутого объекта; и/или

- значение переменного параметра, который используется для формирования полученного первого идентификационного слова, выбирается случайным образом или почти случайным образом; и/или

- полученное первое идентификационное слово передается по каналу связи от устройства идентификатора кодированным способом с использованием кода с коррекцией ошибок; и/или

- канал связи представляет собой беспроводный канал, такой как радиоканал, и устройство верификации содержит считывающее устройство для беспроводной идентификации, и, по меньшей мере, некоторые из объектов из набора объектов содержат теги беспроводной идентификации; и/или

- возможность получения множества представителей, которые можно получить из идентификатора, предоставляется только объекту из упомянутого набора объектов, имеющих упомянутый идентификатор, и устройству верификации; и/или

- первая функция кодирования выполнена таким образом, чтобы единственное первое идентификационное слово могло быть результатом применения первой функции кодирования к нескольким различным идентификаторам среди набора всех возможных идентификаторов.

Более того, в настоящем изобретении предложено устройство верификации, выполненное с возможностью обмена элементами информации с набором объектов, по меньшей мере, через один канал связи, причем каждый объект из упомянутого набора объектов имеет первый соответствующий идентификатор, из которого можно получить множество представителей. Это устройство верификации содержит:

- блок для получения первого идентификационного слова, которое относится к объекту, для которого выполняется поиск, причем первое идентификационное слово образовано путем применения первой функции кодирования к первому идентификатору объекта, для которого выполняется поиск для того, чтобы зависеть от подчасти множества представителей, которые можно получить из упомянутого первого идентификатора, причем упомянутая подчасть определяется, по меньшей мере, одним переменным параметром; и

- блок для передачи по каналу связи первого идентификационного слова, полученного упомянутым блоком получения.

В настоящем изобретении также предложен объект, принадлежащий набору объектов, способных обмениваться элементами информации с устройством верификации, по меньшей мере, через один канал связи, и каждый из которых имеет первый соответствующий идентификатор, из которого можно получить множество представителей. Упомянутый объект содержит:

- блок для приема идентификационного слова, соответствующего первому идентификационному слову, переданному по каналу связи устройством верификации, причем первое идентификационное слово формируется путем применения первой функции кодирования к первому идентификатору объекта, для которого выполняется поиск, для того, чтобы зависеть от подчасти множества представителей, которые можно получить из упомянутого первого идентификатора, при этом упомянутая подчасть определяется, по меньшей мере, одним переменным параметром;

- блок для применения первой функции идентификации, связанной с первой функцией кодирования, к принятому идентификационному слову, и к первому идентификатору упомянутого объекта и к элементу информации, известной упомянутому объекту среди первого идентификатора упомянутого объекта и, по меньшей мере, одного представителя из множества представителей, которые можно получить из упомянутого первого идентификатора, для того, чтобы верифицировать, соответствует ли упомянутый объект искомому объекту.

В настоящем изобретении также предложена система для поиска объекта, принадлежащего набору объектов, с использованием устройства верификации, причем система содержит средство, подходящее для выполнения способа, упомянутого выше.

Другие особенности и преимущества настоящего изобретения станут очевидны из следующего описания неограничивающих примеров вариантов осуществления со ссылкой на сопроводительные чертежи, на которых:

фигура 1 - схема архитектуры примера системы, позволяющей выполнить настоящее изобретение;

фигуры 2-4 - схемы, показывающие неограничивающие примеры вариантов осуществления настоящего изобретения.

На фигуре 1 показано устройство 1 верификации и набор объектов, выполненных с возможностью обмена элементами информации через канал 2 связи. Показанные объекты 3-5, могут образовывать, только сами по себе, набор существующих объектов. Альтернативно, они могут соответствовать только объектам, которые могут поддерживать связь через канал связи в заданное время. Другие объекты можно при необходимости в дальнейшем добавить к ним или заменить их в другие периоды времени наблюдения.

Как показано во введении, каждый объект 3-5 может состоять из любого элемента аппаратных средств и/или программных средств, связанных при необходимости с устройством, системой или индивидуумом. В примере фигуры 1, объекты 3-5 были представлены как теги беспроводной идентификации, такие как RFID-метки (метки радиочастотной идентификации). Альтернативно, они могут быть идентификационными картами доступа, чип-картами, мобильными телефонами, компьютерами, подсоединенными к сети или другими. Более того, необязательно чтобы все объекты 3-5 имели одинаковый тип. Посредством иллюстрации они могут относиться к мобильному телефону в первом случае, RFID-метке, связанной с предметом во втором случае и компьютером в третьем случае.

Устройство 1 верификации может также принимать различные формы в зависимости от типа объектов, для которых предназначен поиск, как также указано во введении. Например, устройство 1 верификации может быть считывающим устройством для беспроводной идентификации, таким как RFID-считывающее устройство, которое изображено на фигуре 1, датчиком, сервером или др.

Канал 2 связи, со своей стороны, подходит для обмена элементами информации между устройством 1 верификации и объектами 3-5. Согласно требованиям, он может быть проводным или беспроводным. В примере фигуры 1, канал 2 связи является радиоканалом, поскольку устройство 1 верификации является RFID-считывающим устройством, и все или некоторые из объектов 3-5 являются RFID-метками. Когда объекты различного типа должны поддерживать связь с устройством верификации, можно использовать несколько каналов связи. Например, проводной канал связи и беспроводный канал связи можно использовать с проводными объектами и беспроводными объектами, соответственно.

Более того, канал 2 связи может быть простым, то есть, обеспечивать прямую связь между устройством 1 верификации и объектами 3-5, например, посредством заданной радиочастоты. Альтернативно, этот канал 2 связи можно более тщательно разработать. Например, он может состоять из набора коммуникационных ресурсов из сети связи, такой как компьютерная сеть, телекоммуникационная сеть или др.

Согласно настоящему изобретению, объект, принадлежащий набору объектов упомянутых выше, например, объекту 4, отыскивается с использованием устройства 1 верификации. Другими словами, знание отыскивается с использованием устройства 1 верификации, в отношении того, прослушивается ли объект 4 по каналу 2 связи. Если канал 2 связи является каналом с узким диапазоном, то это равносильно поиску, находится ли рядом с устройством 1 верификации объект 4.

Будет понятно, что тип устройства 1 верификации объектов 3-5 и канала 2 связи будет подходить для использования по назначению. Таким образом, если желательно иметь возможность проверить на наличие индивидуумов внутри конфиденциальных объектов или доступ малого числа индивидуумов к конфиденциальным объектам, то можно, например, использовать идентификационные карты доступа, снабженные RFID-чипами, которые ассоциированы с индивидуумами в качестве объектов, RFID-считывающее устройство в качестве устройства верификации и радиоканал, использующий частоты, подходящие для технологии RFID в качестве канала связи. Альтернативно, если желательно выполнить реализацию компьютерного приложения в режиме онлайн, условно зависимого от проверки идентичности, то канал связи может в дальнейшем состоять из ресурсов связи в компьютерной сети, используемые объекты могут содержать компьютеры, подсоединенные к этой сети, и устройство верификации является, например, сервером, подсоединенным к этой сети.

Конечно, можно предусмотреть другие примеры, согласно принципам настоящего изобретения, которые будут ясны специалистам в данной области техники.

Каждый из объектов 3-5 имеет соответствующий идентификатор, в том смысле, что существует связь между этим объектом и соответствующим идентификатором. Множество представителей можно получить из такого идентификатора. Например, идентификатор m, который относится к объекту, может непосредственно состоять из множества представителей m_k, где k находится в диапазоне от 1 до целого числа n, то есть m=(m₁, m₂, …, m_n). В этом случае, каждый представитель m_k можно получить из идентификатора m путем простого выбора m. В большинстве случаев, множество представителей m_k можно получить из соответствующего идентификатора m с использованием одной или более функций f_k генерации, предназначенных для этих целей. Это можно выразить, например, следующим образом: m_k=f_k(m). Можно также предусмотреть, чтобы одна функция f генерации позволяла выводить все представители m_k из идентификатора m, например, с помощью итерационного процесса, путем последовательного получения различных представителей из одного или более уже полученных представителей.

Идентификатор является, например, последовательностью значений, например, двоичных знаков, байтов или т.п. В случае, где m=(m₁, m₂, …, m_n), каждый представитель m_k может, например, образовывать одну или более последовательность значений m. Конечно, возможны другие конструкции, как будет ясно специалистам в данной области техники.

Каждый идентификатор является, предпочтительно, уникальным для того, чтобы избежать неоднозначности между объектами, идентифицированными таким образом. С другой стороны, некоторые идентификаторы могут при необходимости иметь общих представителей.

Идентификаторы можно выполнить в соответствии с заданной моделью. Посредством примера, идентификаторы можно выполнить в виде последовательностей n двоичных знаков, которые позволяют получить в общем 2ⁿ идентификаторов. Таким образом, можно получить число возможных идентификаторов, которое больше, чем число действительно вовлеченных объектов.

Каждый из объектов 3-5 может знать свой идентификатор или множество представителей, которые можно получить из своего идентификатора. Это знание может возникать из того факта, что идентификаторы и/или соответствующие представители хранятся в памяти объекта, который имеет к этому отношение. Альтернативно, его можно получить путем консультации внешней памяти посредством приема этих элементов информации от внешней памяти или др.

Устройство 1 верификации, со своей стороны, позволяет узнать идентификатор и/или множество представителей, которые можно получить из идентификатора каждого из объектов из набора объектов. Это знание может снова возникать из хранения в памяти устройства 1 верификации, из консультации внешней памяти, из приема этих элементов информации, из внешней памяти или др.

Преимущественно, возможность получения множества представителей, которые можно получить из идентификатора, предоставляется только объекту, имеющему этот идентификатор, и устройству верификации. Это можно выполнить несколькими способами.

Например, идентификатор, о котором идет речь, можно сохранить в защищенных устройствах памяти, к которым можно получить доступ, с одной стороны, только с помощью объекта, имеющего этот идентификатор, и, с другой стороны, с помощью устройства идентификатора. Идентификатор никогда не передается по каналу связи. Так как идентификатор упомянутого объекта не известен третьим сторонам, последние не могут получить его представителей.

Альтернативно или в качестве дополнения, представители идентификатора, о котором идет речь, можно сохранить в защищенных устройствах памяти, к которым, с одной стороны, может получить доступ только объект, имеющий этот идентификатор, и, с другой стороны, с помощью устройства верификации. Они не передаются одновременно по каналу связи. Поэтому третьи стороны не могут знать представителей, которые относятся к упомянутому объекту.

Можно также предусмотреть, чтобы идентификатор, о котором идет речь, был элементом общедоступных данных, но чтобы функция генерации, делающая возможным получение соответствующих представителей, была секретной. Таким образом, третья сторона, имеющая идентификатор, предотвращает возможность делать вывод от его соответствующих представителей.

Поиск объекта, согласно настоящему изобретению, использует концепцию идентификационного кода. Пример этой концепции идентификационного кода описан, в частности, в статье Рудольфа Ахлсведе и Гюнтера Дуека "Идентификация посредством каналов", Труды IEEE по теории информации, т.35, №1, январь 1989 г. (Rudolf Ahlswede and Gunter Dueck entitled "Identification via Channels", IEEE transactions bn information theory, Vol.35, No.1, published in January 1989).

Обычно, слово с такого идентификационного кода называется в дальнейшем идентификационным словом, вычисляется путем применения функции кодирования к идентификатору т, из которого можно получить множество представителей m_k, где k находится в диапазоне от 1 до целого числа n. Функция fc кодирования выбирается для того, чтобы полученное идентификационное слово зависело от подчасти множества представителей m_k. Другими словами, идентификационное слово может зависеть от одного или более представителей m_k из m, но не от всех представителей m₁, m₂, …, m_n. Подчасть множества представителей m_k, от которых зависит идентификационное слово, определяется, по меньшей мере, одним переменным параметром.

Функция fi идентификации связана с функцией fc кодирования, которая используется для вычисления идентификационного слова с из идентификатора m.

Свойства идентификационного кода представлены, например, ниже:

- если y1 является словом, полученным путем применения функции fc кодирования к идентификатору m, применение функции fi идентификации к y1 и к m или, по меньшей мере, к некоторым из их представителей, неправильно делает вывод относительно того, что отсутствует соответствие с вероятностью менее чем λ1; и

- если y2 является словом, полученным путем применения функции fc кодирования к идентификатору m', который отличается от m, то применение функции fi идентификации к y2 и к m или, по меньшей мере, к некоторым их представителям, неправильно делает вывод, относительно того, что существует соответствие с вероятностью менее чем λ1.

Чем меньше λ1 и λ2, тем более надежным является идентификационный код.

Преимущественно, функция fc кодирования, которая используется в рамках настоящего изобретения, может, более того, быть выполнена так, чтобы одно идентификационное слово могло быть результатом применения этой функции fc кодирования к нескольким различным идентификаторам среди набора всех возможных идентификаторов. Посредством неограничивающего примера, если каждый из идентификаторов состоит из ряда представителей, причем некоторые представители могут быть общими между, по меньшей мере, двух различных идентификаторов, то функция fc кодирования, состоящая из выбора представителя данного ранга из ряда представителей, может иногда возвращать то же самое значение, когда она применяется к двум различным идентификаторам.

Специфический или полезный пример идентификационного кода, который можно использовать в рамках настоящего изобретения, описан в статье Пирра Моулина и Ральфа Коеттера "Основы построения кодов идентификации для хороших водяных знаков", VIII конференция по безопасности, стеганографии и использованию водяных знаков мультимедийных контентов, Сан-Хосе, Калифорния; с.565-574; ISBN/ISSN: 0-8194-6112-1, январь, 2006 г. (Pierre Moulin and Ralf Koetter entitled "A framework for the Design of Good Watermark Identification Codes", Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, California; pp.565-574; ISBN / ISSN: 0-8194-6112-1, published bn January 2006). Конечно, любой другой идентификационный код можно использовать вместо него или в добавление к нему.

Поиск объекта, согласно настоящему изобретению, выполняется путем получения, при получении блока устройства 1 верификации, идентификационного слова с, которое относится к искомому объекту. Это получение можно выполнить путем вычисления, выполняемого в соответствии с принципами, раскрытыми выше, в устройстве верификации или в другом устройстве, передающем идентификационное слово, вычисленное в устройстве верификации, или совместно используемым способом между этими двумя устройствами. Альтернативно, это получение можно выполнить путем нахождения идентификационного слова с, которое относится к отыскиваемому объекту, например, в памяти устройства 1 верификации.

Сразу после получения идентификационного слова с в устройстве 1 верификации, блок передачи последнего передает его по каналу 2 связи. Так как канал 2 связи является общим для всех объектов, переданное идентификационное слово можно принять с помощью любого объекта 3-5, прослушивающего этот канал.

Каждый объект 3-5, принявший с использованием соответствующего блока приема идентификационное слово, соответствующее переданному идентификационному слову (с возможным исключением ошибок передачи в случае, когда канал 2 связи вносит ошибки, например, из-за шума), позволяет затем преимущественно применить с использованием соответствующего прикладного блока функцию fi идентификации, связанную с функцией fc кодирования к принятому идентификационному слову и к элементу информации, которую он знает среди своего идентификатора и, по меньшей мере, одного представителя из множества представителей, которые можно получить из своего идентификатора, для того, чтобы верифицировать, соответствует ли упомянутый объект искомому объекту.

Для того, чтобы повысить надежность верификации, которую выполняет каждый блок 3-5, идентификационное слово, полученное устройством 1 верификации, преимущественно передается с кодом передачи, который является кодом с коррекцией ошибок. Любой известный код с коррекцией ошибок можно использовать для этой цели. Далее каждый блок 3-5 преимущественно имеет связанную функцию декодирования, которая позволяет ему находить идентификационное слово, переданное устройством 1 верификации, без ошибок, или, по меньшей мере, с ограниченным количеством ошибок.

Приоритет будет предоставлен коду с коррекцией ошибок, который подходит для типа блоков 3-5, устройства 1 верификации и канала 2 связи. Посредством примера, если обмен элементами информации имеет место по каналу 2 беспроводной связи с очень большими шумами, то предпочтительным будет код с коррекцией ошибок, например, с высокой избыточностью.

Способ построения идентификаторов и их представителей можно также принять во внимание при выборе используемого кода с коррекцией ошибок. Например, если, по меньшей мере, одна из вероятностей λ1 и λ2, которые упомянуты выше, является более высокой, то желательно предоставить приоритет коду с коррекцией ошибок с возможностью коррекции большого количества ошибок для того, чтобы не ухудшить плохие характеристики идентификации.

Неограничивающие примеры варианта осуществления будут описаны ниже для иллюстрации возможного типа верификации, согласно настоящему изобретению. Во всех этих примерах принята архитектура, изображенная на фигуре 1, и предполагается, что объект 4 отыскивается с использованием устройства 1 верификации.

В примере, показанном на фигуре 2, идентификаторы объектов являются последовательностями значений, состоящими из ряда представителей. В частности, объект 4 имеет, в качестве идентификатора, m=(m₁, m₂, …, m_n), где m₁, m₂, …, m_n являются представителями.

Сначала устройство 1 верификации выбирает число i между 1 и n. Выбор i можно выполнить случайно или почти случайно. Затем устройство 1 верификации выбирает представителя m, из m из ранга i в последовательности m=(m₁, m₂, …, m_n). В этом случае, этот представитель m, затем образует идентификационное слово с.

В этом примере, выбор представителя с помощью своего ранга в идентификаторе m является переменным параметром, который определяет подчасть из множества представителей, которые можно получить из идентификатора m, в этом примере только один из n представителей.

Альтернативно, несколько индексов можно выбрать вместо единственного индекса i для того, чтобы выбрать более чем одного представителя. Например, случайный выбор чисел (i,j) между 1 и n при необходимости позволяет получить идентификационное слово с типа (m_i,m_j) или также любую комбинацию между m_i и m_j, такую как m_i+m_j.

На этапе 6 фигуры 2, устройство 1 верификации передает идентификационное слово m_i, полученное по каналу 2 связи. Преимущественно, устройство 1 верификации также передает по каналу 2 связи число i, которое было использовано для выбора представителя т; или любой другой идентификатор значения i. Эти два элемента информации можно передать в одном сообщении или в двух различных сообщениях.

Затем каждый из объектов 3-5, прослушивающих канал 2 связи, принявший идентификационное слово, соответствующее идентификационному слову m_i, переданное устройством 1 верификации, можно верифицировать то, отыскивается ли объект.

В частности, объект 4 принимает идентификационное слово $${\tilde{m}}_i$$ , которое соответствует m_i, с возможным исключением нескольких ошибок передачи. Он также преимущественно принимает число $$\tilde{i}$$ , которое соответствует i с возможным исключением нескольких ошибок передачи.

Функция fc кодирования, которая используется устройством 1 верификации, состоит из выбора представителя из множества представителей m₁, m₂, …, m_n объекта 4. Функция fi идентификации, связанная с этой функцией кодирования и которая используется объектом 4 (а также с помощью каждого из других объектов, прослушивающих канал 2 связи) заключается, со своей стороны, в нахождении представителя ранга $$\tilde{i}$$ в пределах идентификатора m объекта 4 и затем сравнения его с принятым идентификационным словом $${\tilde{m}}_i$$ .

В случае соответствия, объект 4 рассматривает, что объект в самом деле отыскивает и преимущественно посылает ответ 7 через канал 2 связи в устройство 1 верификации для того, чтобы информировать его об этом.

Следует отметить, что если число i не передается устройством 1 верификации, то верификация все еще возможна в блоке 4, но путем сравнения идентификационного слова $${\tilde{m}}_i$$ со всеми или некоторыми из представителей m₁, m₂, …, m_n, а не с единственным представителем ранга $$\tilde{i}$$ .

В приведенном выше примере, было рассмотрено, что объект 4 мог знать свой идентификатор m, например, так как он был сохранен в своей памяти. Если только представители m₁, m₂, …, m_n из m известны объекту, но не их порядок в пределах m, то можно также выполнить сравнение принятого идентификационного слова $${\tilde{m}}_i$$ со всеми или некоторыми из известных представителей объекта 4.

В этих двух последних случаях, соответствия между принятым идентификационным словом $${\tilde{m}}_i$$ и любым одним из представителей, известных или полученных из m с помощью объекта 4, может быть достаточно для принятия решения относительно того, что объект 4 является действительно отыскиваемым объектом.

В случае, где объект 4 посылает ответ 7 устройству 1 верификации через канал 2 связи, этот ответ может просто означать, что объект 4 рассматривает себя как соответствующий отыскиваемому объекту. Напротив, если объекты 3 и 5 не рассматривают себя как соответствующие отыскиваемому объекту, то они не посылают ответ в устройство 1 верификации. Последнее позволяет затем принять решение относительно того, что объект 4 действительно является одним отыскиваемым объектом.

Так как функция кодирования является вероятностной и не детерминированной, то можно, чтобы несколько объектов сами принимали решение относительно поиска объекта. В этом случае, устройство 1 верификации может принимать несколько ответов 7 на свой запрос 6 из нескольких объектов через канал 2 связи. Затем, было бы преимущественно, чтобы можно было уточнить свой поиск для того, чтобы идентифицировать отыскиваемый объект. Посредством примера, можно выполнить повторный запрос объектов 3-5 путем выбора и передачи пары (j,m_j), который отличается от (i,m_i). Предпочтительно, переданная пара (j,m_j) будет выбираться для того, чтобы избежать новую неоднозначность между объектами, которые послали ответы 7, то есть, для того, чтобы только один из этих объектов рассматривал себя как соответствующий отыскиваемому объекту.

В примере, показанном на фигуре 2, ответ 7, посланный объектом 4 через канал 2 связи, содержит информацию, основанную на том же самом принципе, как и запрос 6.

С этой целью, кроме m объект 4 знает, посредством хранения в своей памяти, например, второй идентификатор M=(M₁, M₂, …, M_n) или все или некоторые из своих представителей М₁, М₂, …, M_n без учета порядка. Он также имеет вторую функцию Fc кодирования, которая может отличаться или быть идентичной fc. Объект 4 затем позволяет получить второе идентификационное слово путем применения второй функции Fc кодирования к элементу информации, который он знает среди М и, по меньшей мере, одного из представителей M₁, M₂, …, M_n.

В примере, показанном на фигуре 2, вторая функция Fc кодирования является такой же, как и fc, и ее переменный параметр фиксируется на том же самом значении, как и выбранный устройством 1 верификации (то есть, i). Таким образом, ответ 7, посланный объектом 4, включает в себя второе идентификационное слово М;. Число i можно при необходимости передать в дополнение к M_i, если устройство 1 верификации не знает, что вторая функция Fc кодирования использует то же самое значение переменного параметра, как и fc.

Возможно, что второй идентификатор М является фактически тем же самым, как и первый идентификатор m. В этом случае, ответ 7 будет предпочтительно включать в себя пару (j,m_j), которая отличается от (i,m_i).

Факт включения дополнительной информации в ответ 7, может сделать возможным для устройства 1 верификации выполнение дополнительной верификации идентичности. Следует отметить, что этот режим работы не ограничен типом идентификатора, описанным со ссылкой на фигуру 2, но может применить любой используемый формат идентификатора.

Для того чтобы выполнить такую дополнительную верификацию идентичности, устройство 1 верификации предпочтительно имеет вторую функцию Fi идентификации, связанную со второй функцией Fc кодирования. Как было описано в отношении объекта 4, устройство 1 верификации применяет вторую функцию Fi идентификации к идентификационному слову $${\tilde{M}}_i$$ , принятому в устройстве 1 верификации, и к элементу информации, известному устройству 1 верификации среди идентификатора m объекта 4, и, по меньшей мере, одного из его представителей M₁, М₂, …, M_n.

Эта дополнительная верификация делает возможным подтверждение или, напротив, отрицание того, что объект 4 является искомым объектом. Эта опция полезна, так как она ограничивает ошибки идентификации, которые, вероятно, возникают в вероятностной модели настоящего изобретения.

По сравнению со способами предшествующего уровня техники, которые упомянуты во введении, пример, который был только что описан, позволяет понять, что изобретение позволяет авторизовать поиск объекта, который улучшает защиту своей идентичности.

Нарушитель, прослушивающий канал связи и априорно не имеющий знания идентификаторов объектов и их представителей, в общем, не сможет найти идентификатор m объекта 4 из переданных представителей m_i и M_i.

Задача нарушителя, прослушивающего канал 2 связи, становится особенно трудной, так как выполняемое кодирование является вероятностным и не детерминированным, поскольку оно не зависит, по меньшей мере, от одного переменного параметра. В результате, различные идентификационные слова позволяют выполнить идентификацию одного объекта.

Более того, общее количество возможных идентификационных слов гораздо больше, чем общее количество идентификаторов. Поэтому почти невозможно для нарушителя обнаружить все идентификационные слова, относящиеся к данному объекту, путем прослушивания канала 2 связи в течение ограниченного периода времени.

И даже в случае, если нарушитель смог узнать идентификаторы некоторых объектов и/или их представителей, то он необязательно сможет принять решение с достоверностью относительно идентичности объекта, который послал ответ, в частности, в случае, где функция кодирования должна, вероятно, приводить в результате к одному идентификационному слову, когда он применяется к нескольким различным идентификаторам.

Таким образом, настоящее изобретение, в частности, позволяет улучшить соблюдение частной жизни индивидуумов и сделать более трудным отслеживание устройства.

Другое преимущество настоящего изобретения состоит в его эффективности. В примере, описанном со ссылкой на фигуру 2, если предполагается, что каждый из представителей m₁, m₂, …, m_n, образующих идентификатор m, состоит из одного байта, то есть, восьми битов, то поиск может, приблизительно, потребовать только передачи одного байта (передачи m₁ на этапе 6). Для сравнения, передача целиком идентификатора m=(m₁, m₂, …, m_n) с помощью устройства верификации, как в предшествующем уровне техники, со своей стороны, требует n байтов.

Указанные выше преимущества не ограничиваются примером, описанным со ссылкой на фигуру 2, поскольку будут ясны специалистам в данной области техники.

На фигуре 3 изображен другой пример варианта осуществления настоящего изобретения. В этом примере, каждый из объектов 3-5 имеет идентификатор в форме соответствующего полинома. Представители, которые можно получить из такого идентификатора, представляют собой, например, оценки этого полинома в различных точках или коэффициенты этого полинома.

Например, идентификатор, который относится к объекту 4, может быть полиномом p(x), и соответствующие представители могут представлять собой оценки этого полинома в наборе определенных точек x₁, x₂, …, x_n, где n - целое число, то есть, p(x₁), p(x₂), …, p(x_n).

Функция fc кодирования, которая используется устройством 1 верификации, в этом случае, может, например, состоять из выбора одной из этих оценок случайным образом, например, p(x_i). Это идентификационное слово p(x_i) передается из устройства 1 верификации по каналу 2 связи на этапе 8.

После получения соответствующего идентификационного слова, каждый из объектов 3-5 прослушивающих канал 2 связи, сравнивает его со всеми или некоторыми из оценок, которые имеются, в его памяти, для того, чтобы определить возможное подобие.

В случае соответствия, например, для объекта 4, последний посылает ответ 9 в устройство 1 верификации через канал 2 связи. Этот ответ может, например, включать в себя оценку r(X_i), полученную путем применения полинома p в точке X_i, которая отличается от x₁, x₂, …, x_n. Альтернативно, ответ 9 может включать в себя оценку Р(х;), где Р - полином, который отличается от р. В качестве другой альтернативы, ответ 9 может включать в себя оценку p(x_j), с j, которая отличается от i.

На фигуре 4 показан другой пример варианта осуществления, в котором каждый объект имеет, в качестве идентификатора, число, например, которое находится в пределах 1000 и 10000, и в котором представители, которые могут быть получены из этого идентификатора, являются двоичными векторами с фиксированной длиной, например, 20000, и с весом, равным соответствующему идентификатору. Таким образом, все представители m₁, m₂, …, m_n, которые могут быть получены из идентификатора N, при этом N находится между 1000 и 10000, имеют, например, число 1, равное N, и число 0, равное 20000-N, причем эти представители отличаются друг от друга положением нулей и единиц. Следует понимать, что эти численные значения приведены посредством только иллюстрации, и они не ограничивают общность предмета обсуждения.

Устройство 1 верификации, которое отыскивает объект 4 идентификатора N, например, выбирает случайным образом представителя m_i идентификатора N, то есть, двоичный вектор, имеющий N битов в 1 и 20000-N битов в 0. Затем он передает представитель m_i в качестве идентификационного слова по каналу 2 связи на этапе 10.

Объект 4 знает свой идентификатор N, например, так как он хранит его в своей памяти. После получения идентификационного слова длиной 20000, соответствующий переданному представителю m_i, объект 4 вычисляет свой вес, то есть свое число 1 и сравнивает его с N. Это включает в себя функцию идентификации, применимую к принятому идентификационному слову и к идентификатору N объекта 4.

В случае равенства, объект 4 принимает решение, что он является объектом, который искали, и посылает ответ 11 в устройство 1 верификации через канал 2 связи. Этот ответ можно интерпретировать, как таковой, с помощью устройства 1 верификации. В этом примере, ответ 11 не содержит другой полезной информации.

Специалистам в данной области техники следует понимать, что примеры, описанные со ссылкой на фигуры 2-4, не являются ограничительными. Многочисленные другие возможности можно рассматривать, согласно общим принципам настоящего изобретения, которые описаны выше. В частности, можно использовать функции кодирования и/или идентификации, которые отличаются от описанных.

Следует отметить, что все или некоторые из операций, описанных со ссылкой на различные фигуры, можно выполнить полностью или частично с использованием программных средств, то есть, с использованием компьютерного программного продукта, содержащего кодовые инструкции, подходящие для этой цели. В качестве альтернативы или в дополнение, по меньшей мере, некоторые из этих этапов можно выполнить с использованием электронной схемы.

1. Способ поиска объекта, принадлежащего набору объектов, с использованием устройства (1) верификации, причем устройство верификации и объекты из упомянутого набора объектов выполнены с возможностью обмена элементами информации по меньшей мере через один канал (2) связи, при этом каждый объект из упомянутого набора объектов имеет первый соответствующий идентификатор, выполненный с возможностью получения из него множества представителей, при этом способ содержит этапы, на которых:
получают в устройстве верификации первое идентификационное слово (m_i;р(x_i)), относящееся к объекту (4), поиск которого выполняется, причем первое идентификационное слово образовано посредством применения первой функции кодирования к первому идентификатору объекта, поиск которого выполняется так, чтобы первое идентификационное слово зависело от подчасти множества представителей, получаемых из упомянутого первого идентификатора, при этом упомянутая подчасть определяется с помощью по меньшей мере одного переменного параметра (i), при этом выбирают случайным образом с помощью устройства верификации указанное значение переменного параметра, определяющее указанную подчасть множества представителей, получаемых из упомянутого первого идентификатора; и
передают от устройства верификации первое идентификационное слово, полученное по каналу связи.

2. Способ по п. 1, дополнительно содержащий этапы, выполняемые каждым объектом (3-5) из упомянутого набора объектов, прослушивающих канал (2) связи, на которых:
принимают идентификационное слово, соответствующее первому идентификационному слову (m_i;р(x_i)), переданному по каналу связи; и
применяют первую функцию идентификации, связанную с первой функцией кодирования, к принятому идентификационному слову и элементу информации, известному упомянутому объекту, из первого идентификатора упомянутого объекта и по меньшей мере одного представителя из множества представителей, получаемых из упомянутого первого идентификатора, для проверки соответствия упомянутого объекта искомому объекту (4).

3. Способ по п. 2, в котором индикацию значения переменного параметра (i), используемого для образования полученного первого идентификационного слова (m_i), передают от устройства (1) верификации по каналу (2) связи, а для каждого объекта (3-5) из упомянутого набора объектов, прослушивающих канал связи, учитывают при упомянутом применении первой функции идентификации принятую индикацию значения переменного параметра.

4. Способ по п. 2, в котором, когда результат упомянутого применения первой функции идентификации показывает, что упомянутый объект (3-5) соответствует искомому объекту (4), упомянутый объект посылает ответ (7; 9; 11) устройству (1) верификации через канал (2) связи.

5. Способ по п. 4, в котором упомянутый объект (3-5) имеет второй идентификатор, выполненный с возможностью получения из него множества представителей, второе идентификационное слово (M_i;р(X_i)) получается в упомянутом объекте посредством применения второй функции кодирования к элементу информации, известному упомянутому объекту, из второго идентификатора упомянутого объекта и по меньшей мере одного представителя из множества представителей, получаемых из упомянутого второго идентификатора, так чтобы второе идентификационное слово зависело от подчасти множества представителей, получаемых из упомянутого второго идентификатора, причем упомянутая подчасть определяется с помощью по меньшей мере одного переменного параметра (i), а ответ (7; 9; 11), посланный упомянутым объектом в устройство верификации через канал 2 связи, включает в себя второе идентификационное слово.

6. Способ по п. 5, в котором идентификационное слово, соответствующее второму идентификационному слову (M_i;р(X_i)), включенному в упомянутый ответ (7; 9; 11), принимают в устройстве (1) верификации, а устройство верификации применяет вторую функцию идентификации, связанную со второй функцией кодирования, к идентификационному слову, принятому в устройстве верификации, и к элементу информации, известному устройству верификации, из второго идентификатора упомянутого объекта (3-5) и по меньшей мере одного представителя из множества представителей, получаемых из упомянутого второго идентификатора, для осуществления дополнительной проверки соответствия упомянутого объекта искомому объекту.

7. Способ по п. 2, в котором первая функция кодирования выполнена так, что при ее применении к первому идентификатору искомого объекта (4) упомянутый переменный параметр (i) определяет по меньшей мере одного представителя (m_i) из множества представителей, получаемых из упомянутого первого идентификатора, а упомянутое применение первой функции идентификации содержит сравнение между упомянутым представителем, определенным с помощью упомянутого переменного параметра, и по меньшей мере одним представителем из множества представителей, получаемых из первого идентификатора упомянутого объекта.

8. Способ по п. 1 или 2, в котором полученное первое идентификационное слово (m_i) передают по каналу (2) связи от устройства (1) верификации кодированным способом с использованием кода с коррекцией ошибок.

9. Способ по п. 1 или 2, в котором канал (2) связи является беспроводным каналом, таким как радиоканал, а устройство (1) верификации содержит устройство беспроводного считывания идентификации, и по меньшей мере некоторые из объектов из набора объектов (3-5) содержат метки беспроводной идентификации.

10. Способ по п. 1 или 2, в котором возможность получения множества представителей, получаемых из идентификатора, предоставлена только объекту (3-5) из упомянутого набора объектов, имеющему упомянутый идентификатор, и устройству (1) верификации.

11. Способ по п. 1 или 2, в котором первая функция кодирования выполнена так, чтобы результатом применения первой функции кодирования к нескольким различным идентификаторам из набора всех возможных идентификаторов являлось единственное первое идентификационное слово.

12. Устройство (1) верификации, характеризующееся тем, что выполнено с возможностью обмена элементами информации с набором объектов по меньшей мере через один канал (2) связи, причем каждый объект из упомянутого набора объектов имеет первый соответствующий идентификатор, выполненный с возможностью получения из него множества представителей, при этом устройство верификации содержит:
блок получения первого идентификационного слова (m_i;р(x_i)), относящегося к объекту (4), поиск которого выполняется, причем первое идентификационное слово образовано путем применения первой функции кодирования к первому идентификатору объекта, поиск которого выполняется так, чтобы первое идентификационное слово зависело от подчасти из множества представителей, получаемых из упомянутого первого идентификатора, при этом упомянутая подчасть определяется с помощью по меньшей мере одного переменного параметра (i), при этом устройство верификации выполнено с возможностью выбора, случайным образом, указанного значения переменного параметра, определяющего указанную подчасть множества представителей, получаемых из упомянутого первого идентификатора; и
блок передачи по каналу связи первого идентификационного слова, получаемого с помощью упомянутого блока получения.

13. Тег беспроводной идентификации (3-5), принадлежащий набору тегов беспроводной идентификации, выполненных с возможностью обмена элементами информации с устройством (1) верификации по меньшей мере через один канал (2) связи, причем каждый из которых имеет первый соответствующий идентификатор, выполненный с возможностью получения из него множества представителей, при этом упомянутый тег содержит:
блок приема идентификационного слова, соответствующего первому идентификационному слову (m_i;р(x_i)), передаваемому по каналу связи с помощью устройства верификации, причем первое идентификационное слово образовано посредством применения первой функции кодирования к первому идентификатору тега (4), для которого выполняется поиск, так, чтобы первое идентификационное слово зависело от подчасти множества представителей, получаемых из упомянутого первого идентификатора, при этом упомянутая подчасть определяется с помощью по меньшей мере одного переменного параметра (i), при этом устройство верификации выполнено с возможностью выбора, случайным образом, указанного значения переменного параметра, определяющего указанную подчасть множества представителей, получаемых из упомянутого первого идентификатора; и
блок применения первой функции идентификации, связанной с первой функцией кодирования, к принятому идентификационному слову, и к первому идентификатору упомянутого тега, и к элементу информации, известному упомянутому тегу из первого идентификатора упомянутого тега и по меньшей мере одного представителя из множества представителей, получаемых из упомянутого первого идентификатора, для проверки соответствия упомянутого объекта искомому объекту.

14. Система поиска объекта (4), принадлежащего набору объектов, с использованием устройства (1) верификации, содержащая программные и/или аппаратные средства для выполнения способа по любому из пп. 1-11.