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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:12, 27 сентября 2015.
Computationally Secure Pattern Matching in the Presence of Malicious Adversaries
Finding Second Preimages of Short Messages for.png
Авторы Кармит Хазай [@: 1]
Томас Тофт [@: 2]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Здесь предлагается соответствующий протокол для высоко мотивированной задачи безопасности двухсторонней проверки по шаблону: Алиса задаёт текст длинной , в то время как Боб задаёт шаблон длинной . Целью Боба будет узнать где его шаблон встречается в тексте Алисы. Наша конструкция гарантирует полную симуляцию для вредоносного злоумышленника, полиномиально сложного злоумышленника (предполагается, что шифрование ЭльГамаля является семантически безопасным) при конкретных доказуемых вычислениях и затрат на связность для неизменной сложности цикла.
Кроме вышеуказанного, предлагается набор протоколов для различных безопасных задач поиска по шаблону: Шаблон может содержать групповой символ ( вычисление за цикл). Совпадения могут быть приблизительными, т.е. расстояние Хемминга может быть меньше, чем некоторая пороговая граница ( вычисление за цикл). Длинна, , шаблона Боба будет секретной вычисление за цикл). Длинна, , текста Алисы будет секретной ( вычисление за цикл).


Ключевые слова: поиск по шаблону, безопасное двухстороннее вычисление, полная симуляция, вредоносный злоумышленник.

Введение

При безопасном двухстороннем вычислении, два участника с секретными входами реализуют объединенное вычисление некоторой функции от их входов при котором сохраняются несколько свойств безопасности таких как конфиденциальность, корректность и др. Стандартное определение [1][2][3][4] обобщает безопасность с помощью сравнения выполнения такого протокола с «идеальным выполнением», где доверенная третья сторона вычисляет функцию для этих участников. В частности, в идеальной ситуации участники только отправляют свои входы по полностью безопасным линиям связи третьей доверенной стороне, которая затем вычисляет функцию корректно и отправляет выходное значение назначенному участнику. В то же время, говорится что реальный протокол безопасен если нет такого злоумышленника который бы смог сделать что-либо более вредоносное при выполнении реального протокола, чем при выполнении идеального.

Безопасное двухстороннее вычисление было широко изучено, и было показано, что любое полиномиально сложное двухстороннее вычисление может генерировано компилироваться в протоколе безопасной оценки функции с полиномиальной сложностью [Yao86[5], GMW87[6],Gol04[7]]. Эти результаты применяются в различных случаях, (для полудоверенного и вредоносного злоумышленников). Однако, чаще всего результирующие протоколы неэффективны на практике (частично из-за того что они обобщены и не используют какие-либо специальные свойства протокола в частности) и следовательно внимание уделялось созданию эффективных протоколов для специальных функций. Этот подход довольно успешно доказывается для полудоверенного злоумышленника (см., например [LP02[8],AMP04[9],FNP04[10],KS05[11],TPKC07[12]], тогда как при наличие вредоносного злоумышленника протоколы оказывались не практичными (заметным исключением является [AMP04][13]).

В данной работе рассматривается следующая классическая задача поиска: Ализа задаёт текст длинной , а Боб задаёт шаблон (т.е. слово для поиска) длинной , где размеры и известны. Целью Боба будет узнать где его шаблон встречается в тексте, в то время как Алиса не получает никакую информацию о шаблоне. Эта задачи широко изучалась уже не мало лет в силу своей практической реализуемости в приложениях для поиска текста, музыки, вычислительной биологии, получения данных, безопасности сети, и др. Наиболее известное приложение в контексте конфиденциальности это приложение для сравнения строк ДНК; к примеру, которое рассматривается в [GHS10][14]. Рассмотрим случай когда в больнице находится база данных ДНК участвующих в исследовательской работе, а исследователи хотят определить частоту появления определенного гена. Это классическое приложение поиска по шаблону, которое однако осложняется конфиденциальностью. Больнице нельзя предъявлять записи ДНК третьей стороне. В то же время, исследователи не хотят раскрывать информацию о гене с которым они работают, либо доверять выполнение корректного поиска больнице.

Хотя большинство существующих решений довольно практичны они не могут достичь требуемого уровня безопасности; смотрите для примера [Blo70[15],KMP77[16],BM77[17],ACR99[18],NM07[19]]. В данной работе мы сфокусировались на безопасном вычислении основной задачи совпадения по шаблону и некоторых её вариациях.

Наш вклад. Была достигнута эффективность значительно улучшенная на текущий момент для следующих задач:

  • Безопасная проверка по шаблону. Мы разработали эффективный протокол с непрерывным циклом для данной задачи, которому требуется возведений в степень и пропускная способность в групповых элементов. Наш протокол является основополагающим для следующих конструкций.
  • Безопасная проверка по шаблону с групповым символом. Эта задача – известный вариант классической задачи, где Боб (задающий шаблон) определяет новый «не значащий» символ в его алфавите, обозначенный как (групповой символ). Целью Боба будет нахождение всех месторасположений в тексте где встречается данный шаблон, при том, что может заменяться на любой символ. Эта задача была широко изучена с целью обобщить классическую модель поиска до поиска с ошибками. Этот вариант известен как поиск по шаблону с наличием незначащего символа и его можно решить за время [IR07][20]. В данной работе мы разработали протокол, который вычисляет эту функциональность при затратах .
  • Безопасный приблизительный поиск по шаблону. В данной задаче целью Боба является найти позиции, где расстояние Хемминга подстрок (текста) и шаблон будут совпадать не менее чем для . Мы разработали протокол для данной задачи реализующийся при затратах O(nm).
  • Безопасный поиск по шаблону где длинна шаблона или текста остаётся сокрытой. В заключении, мы рассмотрели два варианта с дополнительным требованием безопасности а именно сокрытием длинны входа. Решение данных задач может быть получена за время .

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

Предыдущие работы. Насколько это известно, первыми кто рассмотрел поиск по шаблону в контексте безопасного вычисления были [TPKC07][21]], тогда как при наличие вредоносного злоумышленника протоколы оказывались не практичными (заметным исключением является [AMP04][22], которые проанализировали безопасную версию оценки автоматов с забыванием для получения безопасного поиска по шаблону. Их протокол реализовал КМР алгоритм [KMP77] для полудоверенного злоумышленника. Если вкратце, КМР алгоритм работал за время и искал присутствие шаблона в тексте с помощью реализации того, что при нахождении несовпадения, тела шаблона было достаточно для определения следующего месторасположения совпадения. Их затраты были линейными относительно длинны входа.

Данная задача также изучалась Хазаем и Линделлом в [HL08][23] которые использовали оценку псевдослучайной функции с забыванием (PRF). Однако, их протокол реализовывал более слабое понятие безопасности называемое односторонней симуляционностью, которое не гарантировало полную симуляцию для случая взлома обоих участников. Единственной конструкцией реализующей полную симуляцию при наличие вредоносного злоумышленника была конструкция разработанная Геннаро и др. [GHS10][24]. Они использовали другой подход для реализации алгоритма и представили протокол, который выполняется за циклов и требует возведений в степень и такую же пропускную способность.

Наконец, в недавней работе Катза и Малка [KM10][25] представлено безопасное решение для обобщённой задачи поиска по шаблону, использующее обработку текста. А именно, участник, который задаёт шаблон имеет какую-либо дополнительную информацию о y и его целью является нахождение функции текста и y, для позиций в тексте где встречается шаблон. Они показали как преобразовать методику Яо для измененной схемы чтобы получить протокол, где размер изменённой схемы будет линейным для числа совпадений р и t (а не линейным в |t|). Их затраты определялись размером схем при количестве совпадений u (т.к. отправляет u таких схем). Однако, они рассматривали общий вход для некоторого порогового значения числа совпадений.

Насколько это известно, единственной работой связанной с вышеуказанными вариантами была работа Джарроуса и Пинкаса [JP09][26]. В данной работе авторы решали задачу нахождения расстояния Хемминга для двух строк равной длины при наличие вредоносного злоумышленника. Их протоколу необходим связанный переход с забыванием для каждого бита. Более того, затраты на их протокола увеличиваются относительно статистического параметра выполнения подпротокола для полиномиальной оценки с забыванием функциональности (а именно, протоколу необходимо возведений в степень, где есть степень полинома, т.е. длинна входа). И наконец, их протокол использует схему шифрования Пайлера и т.о. требуется наличие RSA модулей с неизвестной факторизацией. Наш протокол, с другой стороны, реализует отличный от этого подход и ему требуются линейные затраты, для случая строк равной длины.

Эффективность. Помимо предыдущих работ мы сравнили наши протоколы с обобщённой методикой Яо (формально доказанной Линделлом и Пинкасом) [LP07][27] для безопасного вычисления любой функциональности в двухстороннем взаимодействии. Напомним, что протокол Яо использует Булеву схему, которая вычисляет функцию, и её вычислительная сложность будет линейна для размера схемы. Отметим, что вычисление функциональности поиска по шаблону требует наличие схемы размером , т.к. данная схема будет сравнивать каждый шаблон с определённой позицией в тексте (как отмечалось в [GHS10][28], схема, которая реализует функциональность для оценки автоматов с забыванием, требует элементов, т.о. КМР метод здесь не будет способствовать увеличению эффективности). Следовательно, наш протокол для основной функциональности поиска по шаблону более эффективен, чем конструкция Яо даже в случае с полудоверенным злоумышленником; это является таковым и для других подходов основанных на использовании схемы.

План данной работы. Сперва представим соответствующие примитивы в Разделе 2. Следующие за ним разделы содержат наши протоколы. Основной протокол показан в Разделе 3. Затем он расширен до случая с групповыми символами в шаблоне (Раздел 4) и примерного поиска (Раздел 5). В заключении, в работе выявляются протоколы, которые скрывают длину шаблона и текст (Раздел 6 и 7).

Начальные данные и определения

В данной работе мы обозначаем параметр безопасности как . Функция является пренебрежимо малой в k (или просто пренебрежимо малая) если для каждого полинома существует значение такое, что для всех ; т.е. . Пусть и будут распределениями ансамблей. Говорят, что X и Y вычислительно неразличимы по признакам, обозначая это как , если для каждого полинома неравномерно разделяемого по признакам D существует пренебрежимо малая такая, что для каждого и

.

Схема шифрования ЭльГамаля

В основе предложенных протоколов находится аддитивно гомоморфный вариант шифрования ЭльГамаля - с распределённой расшифровкой над полем в котором DDH будет стойким, [ElG85][29]. В действительности, мы используем подход Брандта [Bra05][30] с некоторыми изменениями. Предлагается вычисление для участников относительно пространства шифртекста, в частности, запись означает , а - для шифртекстов и , и .

Доказательства нулевого разглашения для и шифрования ЭльГамаляДоказательства нулевого разглашения для G q   {\displaystyle \mathbb {G} {q}~\,\!} и шифрования ЭльГамаля

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

согласно Шнорру, позволяет доказывающему продемонстрировать знание решения x дискретной логарифмической задачи [Sch89][31].

согласно Чауму и Педерсену, демонстрирует равенство двух дискретных логарифмических задач (также как и знание решения) [CP93][32].

Сформулированный немного в другом виде, показывает, что 4 виды кортежа Диффи-Хеллмана или, что равнозначно, что шифртекст будет шифрованием 0.

показывает, что для шифртекста С, либо С либо является шифрованием 0, т.е. что это шифрование либо 0 либо 1. Это пожно напрямую получить из используя составное доказательство Крамера и др. [CGS97][33].

согласно Абе и др., демонстрирует, что участник доказывающий Р выполняет умножение для шифрования корректно [ACF02][34]. Т.е. для заданного шифртекста С, Р, известного f, вычисляет и ; ясно, что открытый текст будет произведением других открытых текстов.

позволяет доказывающему продемонстрировать что набор шифрований, , будет перестановкой и рандомизацией другого набора - т.е., что их открытый тексты равны. Любой протокол будет реализовывать решение Гротта [Gro03][35] с вероятностью 1.



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


,


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

Выполнения показывают, что С’ был получен из С путём возведения в степень, и что открытый текст зависит от R. Следовательно протокол демонстрирует, что C’ получен корректно. Далее т.к. верификатор получает только шифртекст с RR’ – который является равномерно случайным относительно R’ - является нулевым разглашением.


Распределённое шифрование ЭльГамаля

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

Отметим, что обмен ключами Диффи-Хеллмана [DH76][36] можно использовать для генерации открытого ключа и дополнительного разделения соответствующего секретного ключа [Ped91][37]. Участники сперва согласуют и g. Затем, каждый участник выбирает и отправляет другому. Затем, участники вычисляют и набор . Ясно, что секретный ключ связанный с этим открытым ключом будет . Для того, чтобы удостоверить своё корректное поведение в протоколе участники должны доказать знание их выполняя для . Обозначим этот протокол как который оперирует с функциональностью .

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

Нашим конечным примитивом будет вариация , где узнаёт где именно шифртекст m входа задан 0, но не более этого. сперва возводит С в случайную степень, не нулевую, рандомизирует результат, и отправляет его . Участники затем выполняют для проверки поведения . Затем они расшифровывают конечный шифртекст для , который утверждает что m = 0 тогда и только тогда, когда маскируемый открытый текст был 0. Симуляция тривиальна при заданном доступе к . Обозначим этот протокол как и связанную с ним идеальную функциональность как .

Основное линейное решение

В данном разделе мы покажем наше решение для классической задачи поиска по шаблону. Здесь Алиса задаёт n-битную строку t, а Боб задаёт m-битный шаблон р, и участникам нужно вычислить функциональность определённую как

где это пустая строка и это подстрока длинной m, которая начинается с j-ой позиции в t. Эту задачу подробно изучали уже несколько лет в связи с её потенциальной реализуемостью в приложениях м выявили, что она разрешима при линейной временной сложности [KMP77,BM77], когда не требуется определённый уровень безопасности. Мы проанализировали безопасную версию данной задачи, где Алиса не получает никакой информации о шаблоне при выполнении протокола, при котором Боб не узнаёт в свою очередь ничего о позициях совпадения в тексте. Для нашей установки, участники не разделяют информацию (за исключением длинны входа), хотя предполагается, что они связаны по аутентификационному связующему каналу, и что входы берутся из бинарного алфавита. Расширение этого для случая с большими алфавитами рассмотрено ниже. Наш алгоритм выявляет полностью линейные связующие и вычислительные затраты и реализует полную симуляцию при наличие вредоносного злоумышленника.

Здесь и ниже мы рассматриваем участников совместно (и безопасно) преобразовывающих свои входные значения из бинарного представления в элементы (полагается, что ; большие длины шаблонов можно применять, например, увеличив пространство открытого текста), при том, что две последовательные подстроки текста близки друг к другу. Прозе говоря, оба участника разбивают их вход на биты и шифруют каждый бит отдельно. Затем, участники отображают каждое m последовательное шифрование бит в простое шифрование, которое обозначается как m-символ для которого его бинарное представление получается из этих m бит. Т.о. задача заключается в сокращении совместимости двух элементов (находящегося в ). Отличительная особенность нашего протокола как раз таки эффективно вычисляет это отображение.

Теперь всё готово к тому чтобы показать детальное описание нашей конструкции.

Протокол

  • Входы: Входом Алисы будет бинарная строка t длинной n и целое m, а входом Боба будет бинарная строка р длинной m и целое n. Участники также разделяют параметр безопасности .
  • Протокол:
  1. Алиса и Боб выполняют протокол для генерации открытого ключа и соответствующих разделяемых значений и секретного ключа Алисы и Боба.
  2. Боб отправляет шифрования его m-битного шаблона, р, Алисе. Далее, для каждого шифрования участники выполняют доказательство нулевого разглашения , позволяющее Алисе проверить, что открытый текст будет побитно известен Бобу, т.е., что он определил битовую строку длинной m. Оба участника затем вычисляют шифрование шаблона Боба (1) используя гомоморфное свойство шифрования ЭльГамаля.
  3. Алиса отправляет шифрования бит её n-битного текста, t, Бобу. Далее для каждого шифрования участники выполняют , позволяющее Бобу проверить, что открытый текст будет побитно известен Алисе, т.е., что она в действительности определила шифрование битовой строки длинной n, которая ей известна.
  4. Пусть будет m-битной подстрокой текста Алисы t, начинающейся с . Для каждой такой строки оба участника вычисляют шифрование этой строки, (2)
  5. Для каждого оба участника вычисляют (3)
  6. Для каждого Алиса и Боб выявляют для Боба где именно открытый текст забит 0 с помощью . Боб затем выводит j, если это является искомым значением.

Корректность . Перед выполнением нашего доказательства, объясним его суть и продемонстрируем то, что протокол корректно определяет какая подстрока текста t совпадает с шаблоном р. Напомним, что значение Р, вычисляемое в Ур. (1) (Шаг 2) будет шифрованием шаблона Боба, это следует из гомоморфного свойства шифрования ЭльГамаля (4)

Отметим, что Р получается детерминистически из , следовательно Алиса и Боб задают одинаковые фиксированные шифрования. Аналогично в Ур. (2) вычисляемым на Шаге 4, участники рассчитывают шифрования подстрок длиной m текста Алисы, ,

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

Поэтому, просто остается для Боба безопасно определить какое из будет шифрованием 0 следующим образом

Безопасность . Теперь всё готово к доказательству следующей теоремы,

TemplateTheoremIcon.svg Теорема Теорема 1 (линейный поиск по шаблону)
Предположим, что и будут такими как описано в Разделе 2 и что (G,E,D) будет схемой ЭльГамаля. Тогда безопасно вычисляет при наличие вредоносного злоумышленника.
Доказательство

Доказательство. Отдельно докажем безопасность для случая взлома Алисы и Боба. Наше доказательство будет в гибридной модели, где доверенный участник вычисляет идеальную функциональность и .

Если взломали Боба. Пусть А обозначает злоумышленника контролирующего Боба. В таком случае необходимо доказать, что Боб не получает никакой информации кроме месторасположений совпадений в тексте. Построим симулятор S следующим образом, 1. S задан шаблон р длинной m, целое n и дополнительный вход А а также выполнение операций А над этими значениями 2. S эмулирует доверенного участника для следующим образом. Сперва выбирается два случайных элемента и предоставляются А, он разделяет значение и открытый ключ . 3. S получает от А m шифрования А входа для доверенного участника для . Если условия для которых функциональность выводит 1 не выполняются, S завершает работу отправляя доверенному участнику для и выводит А выходы. 4. В противном случае, S определяет Р согласно свидетельстве для и отправляет его доверенному участнику. Пусть Z будет набором возвращаемых индексов. 5. S определяет текст t’ который соответствует Z. Т.е. для каждого определяется подстрока . Для оставшихся индексов S использует заполнение битов 1. S завершает выполнение как только доверенный участник Алиса будет со входным значением t’. 6. Если по каким либо причинам А отправляет некорректное сообщение S завершает работы отправляя доверенному участнику для . В противном случае он выводит соответствующее значение для А.

Можно заметить, что S оперирует за вероятностное пролиномиальное время. Докажем теперь, что оценка злоумышленника будет вычислительно неразличима по признакам в силу сокращения безопасности ЭльГамаля. Напомним, что только разница между этими оценками относительно позиционирования совпадений шаблона в тексте может позволить разделить по признакам шифрования реального и симулируемого текстов. Предположим здесь, что существует устройство различения по признакам D для этих шифрований, тогда построим устройство различения по признакам взламывающее семантическое безопасное шифрование ЭльГамаля следующим образом. При получении открытого ключа pk и дополнительного входного значения t, участвует в выполнении с А и отправляет где . продолжает эмуляцию выступая в роли Алисы т.к. S не принимает его на Шаге 3, где ему необходимо отправлять шифрования . На данном шаге выводит два набора открытых текстов: (i) , и (ii) . Обозначим за набор шифрований получаемых в ответ. предоставляет А этот набор и завершает выполнение следующим образом. На Шаге 6 заменяет на шифрования 0 тогда и только тогда когда . В противном случае, отправляет шифрование случайного значения в . Ясно, что этот шаг будет вычисляться по разному для гибридного и симулированного случаев. Помимо этого, утверждается, что распределения шифрований будут идентичными. Это так потому, что для каждой позиции совпадения в тексте маскирующийся результат эквивалентен 0, а для каждой позиции несовпадения в тексте маскирующийся результат эквивалентен случайному элементу из . Следовательно, оценки злоумышленника будут идентичными. Наконец, реализует D для А выхода и выводит значения на выходе D. Отметим, что если даны шифрования t, то оценка злоумышленника будет распределена также как и в гибридном выполнении. Более того, если он получает шифрование t’, то оценка злоумышленника будет идентичной при симуляции S.

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

Сложность . Циклическая сложность будет постоянной, т.к. процесс генерации ключа и доказательства нулевого разглашения выполняются при неизменном значении цикла. К тому же, число изменяемых групповых элементов ограничивается O(n + m), т.к. будет n – m +1 подстрок длинной m, а каждому доказательству нулевого разглашения требуется постоянное число групповых элементов.

Согласно вычислительной сложности, ясно, что кроме Шага 4 везде необходимо применить не более O(n + m) возведений в степень. Отметим сперва, что Ур. (2) можно реализовать используя методы умножения и возведения в квадрат. А именно, для каждого вычисляется с помощью .

На это потребуется О(m) умножений для каждой позиции в тексте, что приведёт к О(mn) умножениям для всего текста. Но легко показать сокращение числа умножений до O(n). Проще говоря, в добавление к отправке шифрования 0 или 1 для каждой позиции в тексте, Алиса отправляет шифрование 0 или , соответственно, и доказывает согласованность. С практической точки зрения, может статься более эффективным вычисление О(m) умножений для каждой позиции, чем доказательство этой согласованности.

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

Вариации

Не бинарный алфавит. Алфавитами большего размера можно оперировать при помощи кодирования символов в виде элементов и использования s,а не бинарное понятие для и Р. Доказательство в ZK, что шифрование содержит корректный символ будет простым, например, его можно доказать в бинарном виде.

Длинные шаблоны. Когда длинна шаблона m (или размер алфавита s) будет большим, требование может не удовлетворяться. Этого можно избежать с помощью кодирования шаблона р и подстроки в несколько значений , Вычисляя шифрования разности , Алиса преобразует каждое шифрование в случайным образом, ненулевой экспонентой , и рандомизирует их а затем отправляет Бобу (и доказывает тем самым что всё было выполнено корректно). Участники затем выполняют для произведения этих шифрований и Боб выводит совпадение если найден 0. Отметим, что открытый текст этого произведения будет Т.о. если шаблон совпал, все реализуют то, что это будет шифрованием 0. Если один или более , то вероятность этого шифрования быть шифрованием 0 пренебрежимо мала.

Сокрытие месторасположений совпадений. Может потребоваться чтобы Боб узнавал только число совпадений, а не действительные их позиции. Одни из примеров выступает определение того, как часто некоторый ген проявляется относительно общей базы ДНК, при этом не выявляя конкретную последовательность некоторого ДНК. Это легко получить с помощью выполнения Алисой простого выбора равномерной случайной перестановки и действительной перестановки (и рандомизации) ур. (3). Шифрования отправляются Бобу, и выполняется , позволяющий ему проверить Алису. Наконец, выполняется и Боб выводит число полученных шифрований 0.

Корректность не изменяется: Шифрование 0 всё ещё свидетельствует о том. что совпадение найдено. Однако, в связи со случайной перестановкой применяемой Алисой, позиции перемешиваются, приводя к тому, что Боб не знает о действительных месторасположениях.

Защищённый поиск по шаблону с групповыми символами

Первичный вариант классического поиска по шаблону позволял Бобу отмечать места групповых символом, обозначенных как , в его шаблоне; это означало что они допустимы как для совпадения с 0 так и для совпадения с 1. Говоря более формально, участники вычисляли функциональность определённую как

где есть подстрока длинной m, которая начинается с j-ой позиции t, а определял то, какие эквивалентности допустимы для -позиции. Эта задачи широко изучалась уже не мало лет с целью обобщения основной подели поиска до поиска с ошибками. Этот вариант известен как поиск по шаблону с незначащими символами и разрешаем за O(n + m) время [IR07][38]. Безопасная версия данной задачи гарантирует, что Алиса не сможет выявить позиции групповых символов помимо требований безопасности для основной задачи.

Основная идея решения заключается в том же что и идея для стандартной модели, с двумя оговорками: Боб должен определить позиции групповых символов в зашифрованном виде, и подстроки текста Алисы должны преобразовываться т.о. чтобы они совпали с позициями в шаблоне. Корректность достигается существенным преобразованием протокола. Интуитивно понятно, что для каждой m-битной подстроки t, Боб заменяет значение Алисы на 0 в позиции группового символа что приводит к строке , см. Шаг 6 ниже. Аналогично, шаблон p’ получается из р заменой группового символа на 0. Ясно, что это приводит к равенстве битов и р’ для всех позиций групповых символов. Т.о. точно когда равен р для позиций не содержащих групповые символы.

Протокол

  • Входы: Входом Алисы будет бинарная строка t длинной n и целое m, а входом Боба будет бинарная строка р при алфавите длинной m и целое n. Участники также разделяют параметр безопасности .
  • Протокол:
  1. Алиса и Боб выполняют протокол для генерации открытого ключа и соответствующих разделяемых значений и секретного ключа sk Алисы и Боба.
  2. Для каждой позиции Боб сперва заменяет на 0 . Затем он отправляет шифрования шифрования для Алисе, и для каждого они выполняют . Затем, оба участника вычисляют шифрование «шаблона» Боба в бинарном виде,
  3. Для каждой позиции решётки Боба, он вычисляет бит обозначающий появление Затем он шифрует их и отправляет результат Алисе, и оба выполняют для каждого значения.
  4. Для каждого Боб и Алиса выполняют на . Это демонстрирует Алисе, что если будет множеством, то им же будет и , т.е. что только 0 проявлялись в позициях групповых символов.
  5. Алиса получает своё входное значение как это показано в Шаге 3 Протокола в Разделе 3. Она отправляет шифрования бит t Бобу. Затем участники выполняют для каждого шифрования.
  6. Для каждого входного каждой m-битной подстроки t начинающейся с позиции Боб вычисляет шифрование Он отправляет его Алисе, и они выполняют для каждой тройки , что позволяет Алисе проверить корректно ли Боб перемножил открытые тексты и преобразовал их т.о. в Оба участника затем вычисляют шифрования модифицированных подстрок текста Алисы .
  7. Протокол завершается как и протокол . Для каждого где участники вычисляют и выполняют . Это показывает Бобу который из открытых текстов будет 0. Для каждого он выявляет совпадения с шаблоном и выводит j.


Для выявления того, что протокол не предоставляет новые возможности вредоносного характера, сперва отметим, что спецификация Алисы такая же как а в основном протоколе . Что касается Боба, то доказательства корректного поведения ограничивают его только доверенным объёмом действий. Входные значения боба сперва показываются в виде битовой строки, Шаг 2. Выполнение на Шаге 3 затем выявляет что это будет «строка с групповыми элементами». И наконец, на Шаге 4 проверяется что каждый групповой символ от Другими словами, существует корректный вход при котором доверенный Боб будет отправлять шифрования значений, которыми может воспользоваться Боб злоумышленник. Единственная возможная реализация для злоумышленника Боба будет на Шаге 6, однако, при помощь идёт удостоверение его как корректного и доверенного участника. Формальная симуляция аналогична той что в Разделе 3. Определим следующую теорему:

TemplateTheoremIcon.svg Теорема Теорема 2 (групповые символы)
Предположим, что и описываются как это сделано в Разделе 2 и что (G,E,D) есть схема ЭльГамаля. Тогда безопасно вычисляет при наличие вредоносного злоумышленника.
Доказательство


Что касается сложности то самой затратной частью протокола будет Шаг 6, на котором от Боба требуется отправка шифрований, к Алисе, помимо непосредственного выполнения каждым из них. Следовательно, связующая и вычислительная сложности возрастут до O(nm), в то время как циклическая сложность останется неизменной.

Безопасный приближённый поиск

Второй вариацией будет приближённый поиск по шаблону: Алиса задаёт n-битную строку t, а Боб – m-битный шаблон р. Участники выявляют приближённые совпадения – строки с расстоянием Хемминга меньшим чем пороговое значение Это выполняется для функциональности определённой как

где обозначает расстояние Хемминга, а есть подстрока длинной m, начинающаяся с j-ой позиции в t. Предполагается, что участники разделяют некоторое пороговое значение . Отметим, что данная задача является расширением поиска по шаблону с задачей незначащих символов представленной в Разделе 4. Боб выявляет все совпадения при некоторой ограниченной ошибке вместо того, чтобы определять совпадения для ошибок находящихся на конкретных позициях.

Двумя из наиболее важных приложений приближённого поиска по шаблону будут проверка слов и совпадение последовательности ДНК. Наиболее поздний алгоритм для решения данной задачи не включающий конфиденциальность был предложен Амиром и др. [ALP00][39], который определял решение за время Наше решение достигает О(nm) связующей и вычислительной сложностей.

Основная идея данной конструкции заключается в том, чтобы участники безопасно преобразовали свои входы в бинарный вид как это показано выше. Затем, для выявления совпадений, участники сперва вычисляют (зашифрованные) расстояния Хемминга используя гомоморфные свойства шифрования ЭльГамаля (Шаги 5 и 6). Затем они проверяют будет ли для каждого Во избежании утечки информации эти результаты переставляются до окончательной расшифровки.

Протокол

  • Входы: Входом Алисы будет бинарная строка t длинной n и целое m, и пороговое значение , а входом Боба будет бинарная строка р при алфавите длинной m, целое n, и пороговое значение . Участники также разделяют параметр безопасности .
  • Протокол:
  1. Алиса и Боб выполняют протокол для генерации открытого ключа и соответствующих разделяемых значений и секретного ключа sk Алисы и Боба.
  2. Алиса отправляет Бобу и участники продолжают если
  3. Как и в базовом решении, Боб сперва отправляет шифрования бит своего m-битного шаблона, р, Алисе. Они затем выполняют для каждого значения.
  4. Алиса аналогично определяет шифрования её входа как и в ; для каждого значения участники выполняют .
  5. Для каждого каждой m-битной подстроки t начиная с позиции , Боб вычисляет (5) Он отправляет его Алисе, и для каждой тройки участники выполняют . Это позволяет Алисе проверить корректно ли Боб выполнил перемножения открытых текстов и преобразовал их тем самым в
  6. Для каждого каждой m-битной подстроки t начиная с позиции , оба участника вычисляют шифрования Отметим, что т.к. открытый текст будет , то открытый текст будет Для каждого - т.е. каждой подстроки – оба участника вычисляют
  7. Для каждого (т.е. для каждого расстояния Хемминга в котором будет рассматриваться совпадение) и для каждой подстроки длинной m начиная с позиции , оба участника вычисляют (6)
  8. Для каждого , Алиса выбирает равномерную случайную перестановку и применяет для множества , рандомизирует все шифрования, для и , и отправляет Бобу. Для каждой перестановки, , участники выполняют для , что позволяет Бобу проверить соответствие открытых текстов данным для всех (фиксированных) j.
  9. В заключении, Алиса и Боб выполняют для каждого при и . Это выявляет Бобу который из открытых текстов будет 0. Затем он выводит j тогда и только тогда, когда это будет для

Корректность следует из того, что: Открытые тексты из Уравнения (5) являются суммой Т.е. это будет числом различных битов р и - расстояние Хемминга – так как открытый текст будет .

Каждая выполняемая пороговая проверка использует тестов эквивалентности, один на каждое возможное значение , где каждый тест просто выявляет взаимосвязь k из при шифровании, Ур. (6), для которого участники маскируют и шифруют значения для Боба. Отметим, что стандартное маскирование совместно с перестановкой из Шага 8 позволяет нам быть уверенными, что для каждого потенциального совпадения, Боб либо получает равномерных случайных шифрований случайных значений, ненулевые значения, либо таких шифрований и простое шифрование нуля. Следовательно определим следующую теорему:

TemplateTheoremIcon.svg Теорема Теорема 3 (приближённый поиск)
Предположим, что и и будут определены как это сделано в Разделе 2 и что (G,E,D) будет схемой ЭльГамаля. Тогда безопасно вычисляет при наличие вредоносного злоумышленника.
Доказательство


Что касается сложности, то наиболее затратными шагами будут те, что связанны с расстояниями Хемминга, Шаги 5 и 6, т.к. они будут и . Завершающие шаги – вычисление, рандомизация (перестановка), и расшифровка - требуют , однако т.к. это не так уж и ресурсоёмко. Следовательно общая связующая и вычислительная сложности будут О(nm), тогда как циклическая сложность останется без изменений как и в предыдущих решениях.

Сокрытие длинны шаблона

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


где есть подстрока длинной m, которая начинается с j-ой позиции в t. Протокол , который реализует можно получить незначительно изменив . Для экономии места всё это представлено в полной версии данной работы.

Основная идея заключается в том, что Боб строит шаблон длинной М с помощью заполнения р M – m групповыми символами. В силу не полной корректности, интуитивно понятно, что выполнение для входа выведет желаемый результат, т.к. групповые символы позволяют нам игнорировать некорректные постфиксные значения . Это нас не удовлетворяет по двум причинам. Во-первых, групповые символы определяют совпадения по любому символу, однако, совпадения также должны находится когда групповые символы присутствуют и после конца текста (там где уже нету символов). Во-вторых, злоумышленник Боб не имеет полного доступа к использованию групповых символов – т.е. он не может определять расположение случайных символов, они должны присутствовать только в конце .

  • Совпадения при j > n – M + 1: Решение основополагающей задачи полностью представляется следующим образом: расширяем (компонуем) t символами которые совпадают только с групповыми. Если говорить более детально, то сперва пусть N = n + M – 1. Участники компонуют зашифрованный текст Алисы с М – 1 начальными шифрованиями 2,

Затем, вместо использования бинарного представления для шифрований Р’ и (Шаги 2 и 6 ) мы используем троичное представление

,

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

  • Выявление корректного : Во избежание наличия вредоносного злоумышленника, Боб должен продемонстрировать Алисе, что был построен корректно, т.е. что все групповые символы встречаются в конце шаблона. Это можно заделать показывая, что не будет монотонно увеличиваться, т.е., что 1 (не групповой символ) никогда не последует после 0 (групповой символ). Боб может продемонстрировать это выполнив для при

Сложность эквивалентна . В результате получаем следующую теорему,

TemplateTheoremIcon.svg Теорема Теорема 4 (сокрытие длины шаблона)
Полагается, что и определены так как это сделано в Разделе 2 и что (G,E,D) это схема ЭльГамаля. Тогда безопасно вычисляет при наличие вредоносного злоумышленника.
Доказательство


Сокрытие длинны текста

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

где это подстрока длинной m которая начинается с j-ой позиции в t.

Для экономии места мы здесь предоставим только её решение. Основная идея заключается в то, что Алиса компонует свой текст с N – n2s, и затем демонстрирует, что любое 2s будет встречаться в конце. Детали данного решения аналогичны указанному выше.

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

TemplateTheoremIcon.svg Теорема Теорема 5 (сокрытие длинны текста)
Предположим, что будут такими как определялось в Разделе 2 и что (G,E,D) будет схемой ЭльГамаля. Тогда безопасно вычисляет при наличие вредоносного злоумышленника.
Доказательство


Контакты авторов материала

  1. E-mail: [1]
  2. E-mail: [2]

Литература

  1. [GL91] Goldwasser, S., Levin, L.A.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
  2. [Bea92] Beaver, D.: Foundations of secure interactive computing. In: Feigenbaum, J. (ed.)CRYPTO1991.LNCS, vol. 576, pp. 377–391. Springer,Heidelberg (1992)
  3. [MR91] Micali, S., Rogaway, P.: Secure computation (abstract) (This is preliminary version of unpublished 1992 manuscript). In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992); This is preliminary version of unpublished (1992) (manuscript)
  4. [Can00] Canetti, R.: Security and composition of multi-party cryptographic protocols. Journal of Cryptology 13, 143–202 (2000)
  5. [Yao86] Yao,A.C.-C.:Howto generate and exchange secrets. In:Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS 1986, Washington, DC, USA, pp. 162–167. IEEE Computer Society, Los Alamitos (1986)
  6. [GMW87] Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 218–229. ACM, New York (1987)
  7. [Gol04] Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, New York (2004)
  8. [LP02] Lindell, Y., Pinkas, B.: Privacy preserving data mining. Journal of Cryptology 15(3), 177–206 (2002)
  9. [AMP04] Aggarwal, G., Mishra, N., Pinkas, B.: Secure computation of the k’th-ranked element. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 40–55. Springer, Heidelberg (2004)
  10. [FNP04] Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and setintersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
  11. [KS05] Kissner, L., Song, D.X.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)
  12. [TPKC07] Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient dna searching through oblivious automata. In: Proceedings of the 14th ACM conference on Computer and communications security, CCS 2007, pp. 519–528. ACM, New York (2007)
  13. [AMP04] Aggarwal, G., Mishra, N., Pinkas, B.: Secure computation of the k’th-ranked element. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 40–55. Springer, Heidelberg (2004)
  14. [GHS10] Gennaro, R., Hazay, C., Sorensen, J.S.: Automata evaluation and text search protocols with simulation based security. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 145–160. Springer, Heidelberg (2010) 212 C. Hazay and T. Toft
  15. [Blo70] Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)
  16. [KMP77] Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings.
  17. [BM77] Boyer, R.S., Strother Moore, J.: A fast string searching algorithm. Commun. ACM 20(10), 762–772 (1977)
  18. [ACR99] Allauzen, C., Crochemore, M., Raffinot, M.: Factor oracle: A new structure for pattern matching. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol. 1725, pp. 295–310. Springer, Heidelberg (1999)
  19. [NM07] Navarro, G., M¨akinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), 2 (2007)
  20. [IR07] Iliopoulos, C.S., Sohel Rahman, M.: Pattern matching algorithms with don’t cares. In: van Leeuwen, J., Italiano, G.F., van der Hoek,W., Meinel, C., Sack, H., Pl´aˇsil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 116–126. Springer, Heidelberg (2007)
  21. [TPKC07] Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient dna searching through oblivious automata. In: Proceedings of the 14th ACM conference on Computer and communications security, CCS 2007, pp. 519–528. ACM, New York (2007)
  22. [AMP04] Aggarwal, G., Mishra, N., Pinkas, B.: Secure computation of the k’th-ranked element. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 40–55. Springer, Heidelberg (2004)
  23. [HL08] Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 155–175. Springer, Heidelberg (2008)
  24. [GHS10] Gennaro, R., Hazay, C., Sorensen, J.S.: Automata evaluation and text search protocols with simulation based security. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 145–160. Springer, Heidelberg (2010) 212 C. Hazay and T. Toft
  25. [KM10] Katz, J., Malka, L.: Secure text processing with applications to private dna matching. In: To appear CCS (2010) SIAM J. Comput. 6(2), 323–350 (1977)
  26. [JP09] Jarrous, A., Pinkas, B.: Secure hamming distance based computation and its applications. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 107–124. Springer, Heidelberg (2009)
  27. [LP07] Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
  28. [GHS10] Gennaro, R., Hazay, C., Sorensen, J.S.: Automata evaluation and text search protocols with simulation based security. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 145–160. Springer, Heidelberg (2010) 212 C. Hazay and T. Toft
  29. [ElG85] ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4), 469– 472 (1985)
  30. [Bra05] Brandt, F.: Efficient cryptographic protocol design based on distributed el gamal encryption. In: Won, D.H., Kim, S. (eds.) ICISC 2005. LNCS, vol. 3935, pp. 32–47. Springer, Heidelberg (2006)
  31. [Sch89] Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Quisquater, J.-J., Vandewalle, J. (eds.) CRYPTO 1989. LNCS, vol. 434, pp. 239–252. Springer, Heidelberg (1990)
  32. [CP93] Chaum, D., Pedersen, T.P.:Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)
  33. [CGS97] Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103–118. Springer, Heidelberg (1997)
  34. [ACF02] Abe, M., Cramer, R., Fehr, S.: Non-interactive distributed-verifier proofs and proving relations among commitments. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 206–223. Springer, Heidelberg (2002)
  35. [Gro03] Groth, J.: A verifiable secret shuffle of homomorphic encryptions. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 145–160. Springer, Heidelberg (2002)
  36. [DH76] Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976)
  37. [Ped91] Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
  38. [IR07] Iliopoulos, C.S., Sohel Rahman, M.: Pattern matching algorithms with don’t cares. In: van Leeuwen, J., Italiano, G.F., van der Hoek,W., Meinel, C., Sack, H., Pl´aˇsil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 116–126. Springer, Heidelberg (2007)
  39. [ALP00] Amir,A., Lewenstein,M.,Porat, E.:Faster algorithms for stringmatching with mismatches. In: SODA, San Francisco, California, USA, pp. 794–803 (2000)