Протоколы поиска текста с безопасностью, основанной на симуляции

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:29, 30 октября 2015.
Text Search Protocols with Simulation Based Security
Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA.png
Авторы Rosario Gennaro [@: 1]
Carmit Hazay [@: 2]
Jeffrey S. Sorensen [@: 3]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

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

Введение

Безопасное двухстороннее вычисление определяется как объединённое вычисление нескольких функций над простыми входными значениями используя протокол взаимосвязей, удовлетворяющий как минимум конфиденциальности (никакая другая информация не раскрывается относительно выходной функции) и корректности (вычисляется корректное выходное значение). Текущее общепринятое стандартное определение (см. [1] следующее из [2][3][4]) обобщает безопасность с помощью сравнения выполнения такого протокола и «идеального выполнения», где учасник выступающий в роли третьей доверенной стороны просто отправляет входные значения по идеально безопасным каналам связи к доверенному участнику, который затем вычисляет функцию доверено и отправляет выходное значение назначенному участнику. В действительности, реальный протокол определяется как безопасный, если все атаки злоумышленника на реальный протокол можно реализовать в идеальном случае. В идеальном случае, злоумышленник не может сделать практически ничего, и это гарантирует, что аналогичное будет верно также и для реальности. Это определение безопасности часто называют основанным на симуляции потому что безопасность демонстрируется с помощью «симуляции» выполнения реального протокола в идеальном случае. Безопасное двухстороннее вычисление широко изучено, и известно, что любая эффективная двухсторонняя функциональность может быть безопасно вычислима [5] [6] [7]. Однако, это лишь возможный результат, который демонстрирует реализацию безопасного вычисления, в действительности, но не столь необходимый на практике. Одной из причин этому служит то, что результаты упомянутые выше обобщены, т.е. в них не учитываются какие-либо структурные свойства вычисляющихся специальных функций. В связи с этим исследовательские работы были сфокусированы на нахождении протоколов для конкретных функций: построение таких протоколов имеет решающее значение в случае реализации безопасного вычисления на практике.

Наш вклад

В данной работе были рассмотрены следующие задачи:

  • Безопасная проверка по шаблону. Была рассмотрена основная задача проверки по шаблону. В данной задаче, один участник задаёт текст а другой участник задаёт шаблон , при этом и обоюдно известны. Целью участника задающего шаблон является получения всех местоположений данного шаблона в тексте (их может быть несколько) при этом чтобы другой участник не получил никакой информации о шаблоне.
  • Оценка автоматов с забыванием. Для решения вышеуказанной задачи рассмотрим методику [8], которая сокращает задачу проверки по шаблону до автомата конкретного шаблона и текста в совокупности. Мы разработали протокол для безопасного вычисления оценки для .

Задача проверки по шаблону широко изучалась уже несколько лет в связи с её частой реализацией в приложениях. Но всё же пока не уделялось должного внимания проверки по шаблону в безопасной структуре. Нашей начальной точкой будет очень эффективный протокол, который вычисляет функцию для системы с «доверенным но подозрительным» участником. Это решение можно расширить для односторонней симуляции, также безопасной даже с изменением участника задающего шаблон. Этот первый протокол является независимым относительно протоколов с наличием злоумышленника, и сравним с односторонним симуляционным протоколом [9]. Однако, в связи с тем , что оба протокола достигают одинаковой асимптотической сложности, наш протокол будет более практичен, т.к. используемые конкретные константы в нашем случае можно легко расширить для задач установления взаимосвязи таких как поиск ориентировочного текста или поиск текста с групповыми символами. Наличие злоумышленника вводит много тонкостей рассмотренных для предыдущих систем и требует применения определённых методов. Это включает в себя введение новых подпротоколов таких как, например, протокол доказывающий, что был построен корректный автомат конкретного шаблона. Отметим, что наши протоколы являются первыми встречающимися в открытой литературе протоколами, которые достигают симуляционности для их задач с наличием злоумышленника. Безопасность основывается на схеме шифрования Эль Гамаля [10][11] и т.о. требуется относительно малый параметр безопасности (хотя допустим и любое аддитивно гомоморфное шифрование с безопасными распределёнными двухсторонними протоколам для генерации разделяемых ключей и выполнения расшифровки).

Причины рассмотрения данного вопроса

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

Выходит что здесь применимы основные решения для доверенного но подозрительного участника (уже рассмотренные прежде, см. ниже). Однако, у участников могут быть причины определения некорректного результата, т.о. доказательство точного выходного значения должно быть не менее важным чем само выходное значение. Более того, также необходимо удостовериться, что данные с которыми оперирует протокол корректны. К примеру, недобросовестная больница может продать «фальшивую» базу данных ДНК для исследовательских целей. Возможно некоторые доверенные сертификационные органы должны когда-нибудь сертифицировать базу данных как корректную для некоторых приложений. Тогда, свойства безопасности нашего протокола могут гарантировать, что только корректные данные будут использоваться в протоколе проверки по шаблону (Первым шагом нашего протокола является в случае с больницей – выявить шифрование данных, что можно заменить на выявление зашифрованных данных определённых сертификатом как корректные.)

Работы касающиеся данной темы. Задача безопасной проверки по шаблону была изучена Хазаем и Линделлом в [9], которые использовали псевдослучайную функцию оценки с забыванием (PRF) для оценки каждого блока размером m бит. Однако, достигает только более слабое понятие безопасности называемое односторонней симуляционностью, которое гарантирует конфиденциальность во всех случаях и требует чтобы одного из двух участников никогда нельзя было бы устранить для гарантии корректности. Это наталкивает на мысль, что протокол для вычисления оценки PRF с забыванием для соответствующего ключа (где гарантируется, что аналогичный ключ используется для всех PRF оценок) злоумышленника [12] достаточен для наличия вредоносного воздействия на безопасность. К сожалению, этого не будет, т.к. входные значения для PRF должны быть составными и не вполне понятно как это реализовать. А именно, для каждого i, последние m – 1 бита i-ого блока предполагаются начальными m – 1 битами последующего блока. Идея использования оценки автоматов с забыванием для получения безопасной проверки по шаблону берёт своё начало из [13]. Их протоколы, однако, безопасны только при доверенном но подозрительном участнике. Мы усилили их результаты для соответствия безопасности при наличии злоумышленника.


Эффективность нашего протокола

Когда применяется двухсторонний протокол для безопасного вычисления специальной функции, необходимо удостовериться, что результирующий протокол будет в действительности более эффективен, чем известное «обобщённое» решение для безопасного двухстороннего вычисления любой функции. Сравним наши протоколы с с двумя наиболее эффективными обобщёнными двухсторонними протоколами безопасными при наличии злоумышленников, основывающимися на методике изменения схемы предложенной Яо [5]. Напомним, что протокол Яо (который безопасен для полу доверенных участников) использует Булеву схему для вычисления функции, а её вычислительная сложность будет линейной для размера данной схемы.

  • Одним из результатов [14] было преобразование протокола Яо в стойкий для наличия злоумышленников протокол используя бинарную стратегию cut-and-choose. Это требует выполнение копий протокола Яо, где s является статистическим параметром безопасности, который должен быть довольно большим, чтобы был достаточно мал. Это требует симметричных ключей шифрования, и взаимосвязей показанных в [15], что в свою очередь является основным условием.
  • Другой общий результат из [16] использует специальный вид шифрования для изменения и применения эффективных доказательств нулевого разглашения (ZK) относительно схемы шифрования. Протоколу необходима общая связующая строка (CRS) содержащая стойкие RSA модули. Насколько это известно, на сегодняшний день нет эффективных методик генерации разделяемых стойких RSA модулей без применения дополнительной помощи извне. Более того, их протоколу требуется примерно 720 RSA возведений в степень на каждый элемент, в котором эти операции вычисляются по модулю 2048 в связи с использованием схемы шифрования Пайлера. Это означает что пропускная способность [16] также относительно высока.

Понятия и определения

В данной работе обозначим параметр безопасности как . Хотя длины входных значений неявно задано, но всегда полагаем, что они ограничены некоторым полиномом в . Говориться, что вероятностная машина выполняет вычисления за полиномиальное время (PPT) если она реализует расчёт за время, которое полиномиально только относительно параметра безопасности .

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

для каждого и

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

Доказательства нулевого разглашения

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

  • 1.Доказательство нулевого разглашения знания для следующего отношения: пусть для и будут тремя векторами шифртекстов каждый.
Таблица 1. Доказательства нулевого разглашения наших протоколов
Протокол Отношение/Язык Ссылка




[17]
[18]
[19]

Нужно доказать, что будет «повторным шифрованием» тех же сообщений зашифрованных либо в либо в , или, другими словами, что существует индекс такой, что для всех было получено путём умножения на случайное шифрование . Более формально,

для всех

Это подразумевает под собой вычисление участниками наборов и , где множества и будут открытыми случайными значениями. Доказывающий затем доказывает, что либо либо будет кортежом Диффи-Хеллмана.

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

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

и широко изучена. Современный на сегодняшний день протокол представлен в [20]. Мы используем более простой, хотя и менее эффективный (но достаточный для наших целей) протокол из [21], который является эффективным доказательством нулевого разглашения для с линейным вычислением и связующей сложностью а также неизменным числом циклов. Мы используем этот менее эффективный протокол потому что его доказательство доказывает реализацию для случая, где одна и та же перестановка используется для перемножения векторов шифртекстов.

Безопасные протоколы поиска по тексту

Поиск по тексту включает в себя последовательное сканирование текста, нахождение аналогов заданного шаблона. Эффективному поиску по тексту требуется анализ строки шаблона для выполнения сканирования, которое пропускает части текста, в которых необходимых совпадений вероятно нет, как это сделано и реализовано в КМР [8].

Поиск по шаблону определяется следующим образом: для заданной бинарной строки длинной и бинарного шаблона длинной , назодятся все места в тексте, где встречается шаблон . Иными словами, для каждого пусть будет подстрокой длинной m которая начинается с i-ой позиции в . Тогда, основной задачей поиска шаблона будет возвращение набора . Формально, мы рассматриваем функциональность определяемую как

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

Безопасный поиск по тексту при наличие «доверенного но подозрительного» участника

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

Протокол 1 .

  • Вход: Входом будет бинарная строка поиска , а для бинарная строка текста
Файл:Text search in the honest-but-curious setting.png
Рисунок 1. Поиск по тексту при наличие «доверенного но подозрительного» участника.
  • Допущения: Участники совместно согласуются на группе простого порядка , и генераторе для шифрования Эль Гамаля. Участник генерирует ключевую пару и выдаёт . Наконец, пока не записаны по разному, и .
  • Протокол:
  1. Шифрование шаблона. Участник строит матрицу шифртекстов определённую как где

    каждый будет равномерно случайно выбранным значением соответствующей длины. Матрица отправляется участнику .
  2. Сканирование текста. Для каждого отклонения вычисляет

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

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

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


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


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

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

Безопасный поиск по тексту при наличие злоумышленника

Рассмотрим безопасную версию КМР алгоритма [8], который ищет сходства с шаблоном в тексте путём выявления приблизительных совпадений, при появлении которых с помощью шаблона можно сказать где будет начинаться следующее совпадение, т.о. происходит уход от повторной проверки предыдущих совпадающих элементов. Говоря более общими словами, , входом у которого будет шаблон , строит автомат следующим образом: Обозначим за длину i-ого префикса для . сперва строит таблицу с входами, где i-ой вход обозначает наибольший префикс который окончанием совпадает с Эта таблица (как в Рис. 2) содержит соответствующее частичное совпадение, если было выявлено несовпадение в i-ом бите . Алгоритм выявляет для каждого бита текста каждое входное значение, которое достигает конечного состояния, или один бит для каждого расположения текста.

Файл:Construction of determinized KMP automaton for pattern 1100011001.png
Рисунок 2. Конструкция детерминизированного КМР автомата для шаблона 1100011001.

Отметим, что можно легко построить за время путём сравнения с самим собой для каждого согласования. строит свой автомат основанный на . Сперва он устанавливает и строит таблицу переходов следующим образом. Для всех и где обозначает i-ый вход в (обозначим наименования состояний в Q с помощью последовательных целых значений начинающихся с и до . Т.о., если нет совпадений префикса в i-ом входе, автомат идёт обратно в начальное состояние ). выявляет конструкцию устанавливая

В следующем разделе показывается общий протокол оценки для реализации безопасности и оценки с забыванием для автомата текста. Протокол работает для любого автомата (не только для КМР) и поэтому является независимым в данном понимании. После представления протокола оценки автомата, мы покажем как доказать в нулевом разглашении, что построения автомата являются корректными КМР автоматами.

Безопасная оценка автоматов с забыванием

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

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

Напомним, что начальной точкой был протокол из [13]. Их идея заключалась в наличии участников которые разделяли значение текущего состояния автомата, т.о., что по окончанию k-ой итерации участник с автоматом знал случайную строку тогда как участник с текстом знал Участники завершают каждую итерацию выполняя переход с забыванием при котором следующее состояние теперь разделялось бы между ними. Значительное упрощение их конструкции будет при наличие доверенного но подозрительного злоумышленника. К несчастью, мы не нашли действительный способ преобразования их методики в случай с наличием злоумышленника (даже используя переходы с забыванием стойкие к атакам злоумышленника).

Высокоуровневое описание. Начнём с кратного рассмотрения нашей конструкции; см. Рис. 3.

Файл:A high-level diagram of πAUTO.png
Рисунок 3. Высокоуровневая диаграмма.

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

В начале каждой итерации, участники узнают рандомизированное шифрование текущего состояния, и их целью будет найти шифрование следующего состояния. В итерации , выбирает из матрицы входной зашифрованный столбец всех возможных состояний для его входного значения (известного только для шифрования в текущем состоянии). Затем, используя гомоморфные свойства Эль Гамаля, участники выбирают с забыванием корректное следующее состояние: Пусть обозначает шифрование Участники вычисляют сперва набор , где соответствуют шифрованиям заданным в ; см. далее для получения более детальной информации. Только один шифртекст в данном наборе будет шифрованием , что выявляет позицию соответствующую текущему состоянию. Протокол выполняемый участниками обоюдно проверяет будет ли зашифрованное состояние, выполненное для конечной итерации, находиться в списке зашифровок допустимых состояний.

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

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

Протокол 2.

  • Вход: Входом будет определение автомата а входом - бинарная строка
  • Дополнительный вход: и для , для и параметр безопасности для обоих.
  • Условия: Предположим, что участники совместно согласуют группу простого порядка и генератор для пороговой схемы шифрования Эль Гамаля. Оба участника проверяют каждый полученный шифртекст на корректность, и выводят ошибку, если получен некорректный шифртекст.

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

  • Протокол:
  1. Установка ключа Эль Гамаля:

    a) Участник выбирает случайное значение и отправляет участнику значение Это доказывает знание используя

    b) Участник выбирает случайное значение и отправляет участнику значение Это доказывает знание используя Участники устанавливают (т.е. секретный ключ будет ).

  2. Шифрование таблицы переходов и возможных состояний:

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

    b) Для каждого шифрования доказывается знание используя

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

  3. Первая итерация:

    a) выбирает шифрование следующего этапа . Затем определяет , т.е. случайное шифрование следующего этапа и отправляет это

    b) доказывает, что используя доказательство нулевого разглашения для .

  4. Итерации : для каждого пусть обозначает шифрование ; участники выполняют следующее:

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

    b) переставляет и столбец  :

    • вычисляет для всех (отметим, что соответствует столбцу в матрице переходов – т.е. шифрований всех возможных следующих состояний задаются входным битом ) и отправляет для . Он также доказывает, что было вычислено корректно используя

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

      c) переставляет: Пусть обозначают переставляемые столбцы, которые отправляет . Если принимает доказательство он продолжает аналогично переставляя и рандомизируя используя случайную перестановку . доказывает корректность своих вычислений используя .

      d) Мультипликативное маскирование: Пусть обозначают переставляемые столбцы из предыдущего шага. соответствует переставляемому столбцу из матрицы переходов, который содержит номер состояний минус номер текущего состояния. Участники реализуют маскирование следующим образом: для каждого , выбирает и вычисляет . Затем он доказывает, что есть кортеж Диффи-Хеллмана используя (Шифрование нуля будет неэффективным шагом, т.к. ненулевые значения будут отображаться в случайные значения.) повторяет этот шаг и маскирует результат. Пусть будут результирующими замаскированными столбцами для и соответственно.

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

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

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

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

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

    b) маскирует шифртексты как в Шаге 4d и 4e. Пусть будет результирующим вектором.

    c) рандомизирует и переставляет . Он также доказывает корректность используя . Пусть будет результирующим вектором.

    d) Участники расшифровывают все шифртексты в а результат идёт только  ; для каждого шифртекста , участник отправляет и доказывает, что есть кортеж Диффи-Хеллмана. Эта информация позволяет расшифровать шифртексты, и принимает их если одно из расшифрованных значений эквивалентно одному дополнительному замаскированному значению .

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

TemplateTheoremIcon.svg Теорема Теорема 3.
Предположим, что и будут тему, что описаны выше и, что будет семантически безопасной схемой шифрования Эль Гамаля. Тогда безопасно вычисляет при наличие злоумышленника.
Доказательство
Интуитивно должно быть понятно, что автомат и текст остаётся секретными, если схема шифрования безопасна. Однако, формальное доказательство Теоремы 3 это не показывает. Рассмотрим, например, случай в котором взломан и нам необходимо симулировать работу . Симулятор будет выбирать случайный вход и выполнять код для него. Затем, чтобы доказать неразличимость по признакам этой оценки, необходимо упрощение схемы шифрования. Применяемое упрощение не работает по следующим причинам: для того чтобы симулятор закончил работу корректно необходимо «знать» текущее состояние, для каждой итерации ; но когда мы делаем упрощение Эль Гамаля нужно ввести шифртекст для текущего состояния, для которого расшифровка нам неизвестна, и это т.о. не позволяет нам перейти на следующую итерацию . Нетривиальное решение данной проблемы заключается в доказательстве того, что реальная и симуляционная оценки неразличимы по признакам для последовательности гибридных игр, в которых изменения неразличимости по признакам показываются с помощью работы симулятора, но всё же позволяют завершить выполнение симуляции. Что касается случая, когда взламывается то здесь доказательство ещё более просто в основном потому что не получает выходного значения. В частности, симулятор входа в каждой итерации использует экстрактор для .


Эффективность.' Представим анализ нашего протокола и сравним его эффективность с обобщёнными протоколами из [14][16] для безопасного двухстороннего вычисления при наличие злоумышленника. Мы показали эффективность обобщённых протоколов в Разделе 1. Схема, которая вычисляет требует наличие элементов. Т.к. последовательная схема размером которая вычисляет автомат с Q-состояниями над бинарным входным значением размером , обобщённый протокол реализует только комбинаторные схемы. Т.о. наш протокол улучшает вычислительную сложность над обобщённым решением в силу выполнения на или операций меньше в сравнении с [14] и [16] соответственно. При сравнении с [14][16] получаем следующее:

  1. Циклы вычисления: Наш протокол выполняется за циклов где это длинна текста, по сравнению с неизменной циклической сложностью [14][16]. Это так, потому что участники не могут инициировать новую итерацию перед завершением предыдущей. Применяя известные методики, циклическую сложность можно уменьшить до (т.е. до длины шаблона) с помощью деления текста на блоки размером ; см. Раздел 4 для более детального понимания данного вопроса. Отметим, что длина шаблона обычно очень мала, и приравнена к константе. Дополнительное преимущество можно получить если имеется некоторая утечка значимой информации. В частности, т.к. число циклов определено длиной шаблона, то шаблон можно разбить на блоки и выводить комбинированное значение их результатов. Это означат, что раскрывается дополнительная информация о тексте, т.к. тогда возможно идентифицировать появление в тексте соответствующих подстрок входного шаблона.
  2. Асимметрические вычисления: Общее число возведений в степень в протоколе включая доказательства нулевого разглашения будет . Что касается [14], там число таких вычислений зависит от числа выполнения переходов с забыванием, которое ограничено , где число привязок будет , а должно быть в этом случае достаточно большим, чтобы булл допустимо мал. Наконец, [16] нужно таких операций. Однако, после тщательного анализа данных затрат, получилось, что участники вычисляют примерно 720 RSA возведений в степень для каждого элемента, где чило элементов будет , что явно не реализуемо на практике. Более того, протоколу [16] также необходим параметр безопасности, обычно размером не менее 1024, согласно стойкому RSA предположению. Следовательно, все открытые ключи операций выполняются над группами по модулю этого значения (или большего, такого как ). Что же касается нашего протокола, использующего схему шифрования Эль Гамаля, это можно реализовать над группой эллиптических кривых, обычно, при помощи всего лишь 160 битных ключей.
  3. Симметрические операции: [14], в связи с использованием симметрической схемы шифрования, также требует выполнения таких симметрических вычислений.
  4. Полоса пропускания: В нашем протоколе, участники отправляют друг другу шифрований. Пропускная способность протокола [16] будет аналогичной (опять же с относительно высокими константами), тогда как [14], она определена шифрованиями симметрического ключа. В [15] показано, что взаимосвязь обладает наиболее малой пропускной способностью когда реализуется протокол со злоумышленником [14] .

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

Доказательство нулевого разглашения знания для КМР автомата

Ограничения по объёму не позволяют нам разъяснить полностью наш протокол для , но мы включим сюда его описание:

Протокол 3.

  • Дополнительный вход для доказывающего: Набор множеств, каждое из которых размером 2, таких что для всех и
  • Дополнительные входы для обоих: Простое значение такое что для простого , описание группы порядка для которой выполняется DDH предположение, и генератор группы .
  • Протокол:
  1. Для каждого доказывающий доказывает знание используя .
  2. Для каждой строки в матрице переходов доказывает следующее:

    a) Сперва он случайно переставляет и и выполняет для доказательства его вычислений.

    b) Он доказывает что существует в котором с помощью доказательства того, что есть кортеж Диффи-Хеллмана.

    c) доказывает корректность в два шага: (i) Он сперва доказывает, что оно соответствует корректному префиксу (ii) затем доказывает максимальное значение этого префикса ( обозначает r-ую длину префикса ).

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

    ii Доказательство существования префикса совпадающего с суффиксом : Для всех участники вычисляют шифрование /
    затем доказывает, что существует для которого есть кортеж Диффи-Хеллмана.

    iii Доказательство того, что соответствует наибольшему суффиксу: Затем доказывает, что не существует индекса в котором всё ещё , т.о. это подразумевает, что наибольший суффикс , который совпадает, однако,

    • Поэтому, для каждого и для каждого участники вычисляют шифрование для которого затем доказывает, что не является шифрованием нуля используя

  3. Если все доказательства успешно завершены, выводит . В противном случае он выводит.

Для рассмотрения детального доказательства и определения мы просим читателя обратиться к полной версии данной работы.

Протокол поиска по тексту с безопасностью основанной на симуляции

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

Напомним, что наша конструкция представлена для случая с наличием злоумышленника с полной симулируемостью и являющейся модульной в подпротоколах и . Рассмотрев подпротоколы участвующие в построении нашей схемы теперь мы готовы описать её целиком. Наш протокол состоит из двух основных этапов: сперва участники выполняют для которого доказывает, что он в действительности отправляет корректный КМР автомат, получаемый посредством , где оценивается Г для секретного значения входа . Для того, чтобы уменьшить циклическую сложность протокола, длинные тексты разбиваются на 2m частей и рассматриваются отдельно т.о. чтобы КМР алгоритм работал с каждым блоком независимо (т.о. все эти выполнения можно осуществить параллельно). Т.е. пусть , тогда текст разбивается на блоки и т.д., так, чтобы каждые два последовательных блока перекрывались в m битах. Это подразумевает то, что все совпадения будут найдены. Поэтому, общее число блоков будет l/m.

Протокол 4.

  • Входы: Входом будет бинарный шаблон , а входом будет бинарная строка .
  • Дополнительные входы: параметр безопасности , и размеры входов и .
  • Протокол:
  1. строит свой автомат согласно КМР спецификациям основанным на его входе и отправляет шифрования матрицы переходов и допустимые состояния , обозначенные как и .
  2. Участники выполняют доказательство нулевого разглашения где доказывает, что было построено корректно. Т.е. доказывает, что множество соответствует корректному КМР автомату и определённому входному шаблону длинной . Если выход при данных вычислениях будет , участники продолжают выполнение переходя к следующему шагу. В противном случае возникает отказ .
  3. отправляет шифрование к и другим участникам разбивая на блоки длинной в которых каждые последовательные блоки перекрываются в битах.
  4. Участники выполняют параллельных вычисления для этих блоков. Для каждого , пусть обозначает множество выходов для i-ого выполнения. Тогда возвращает
TemplateTheoremIcon.svg Теорема Теорема 4.
Предположим, что и такие как описано выше и что есть семантически безопасная схема шифрования Эль Гамаля. Тогда безопасно вычисляет при наличие злоумышленника.
Доказательство
Доказательство безопасности для будет состоять из совокупности доказательств описанных для и и в связи с эти здесь не опускается.


Эффективность. Т.к. затраты ограничены затратами , то для рассмотрения детального анализа читателю следует обратиться в Раздел 3.3. Общие затраты будут т.к. в большинстве случаев

Заключение

Наши протоколы для оценки автоматов с забыванием и поиска по шаблону работают в стандартной модели и не требуют ни CRS ни применения стратегии cut-and-choose. При задании строк длинной для текста и шаблона соответственно, оба протока будут иметь затраты связности и вычисления , что является даже асимптотически лучшим результатом, чем в общей схема для оценки автоматов с забыванием, которой требуется схема с элементами. В таблице 2 приведены сравнения вычислительных и связующих затрат для каждой из данных схем.

Таблица 2. Приведённые результаты

Циклическая сложность Связующая сложность Асимптотические вычисления Симметрические вычисления
Линделл-Пинкас [14] константа раз
128/256 бит
max (4m, 8s)
OT's
Джареки-Шматиков [16] константа раз
2048 бит
720 возведений в степень для каждого элемента Нет
Наш протокол
160 бит
Нет

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

  1. IBM T.J. Watson Research Center, Hawthorne, New York, USA E-mail: [1]
  2. Dept. of Computer Science and Applied Mathematics,Weizmann Institute and IDC, Israel E-mail: [2]
  3. IBM T.J. Watson Research Center, Hawthorne, New York, USA E-mail: [3]

Литература

  1. Canetti, R.: Security and composition of multi-party cryptographic protocols. Journal of Cryptology 13, 2000 (1998)
  2. 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)
  3. Beaver, D.: Foundations of secure interactive computing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 377–391. Springer, Heidelberg (1992)
  4. Micali, S., Rogaway, P.: Secure computation (abstract). In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992)
  5. 5,0 5,1 Yao, A.C.C.: How to generate and exchange secrets. In: SFCS 1986: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 162–167. IEEE Computer Society, Los Alamitos (1986) 350 R. Gennaro, C. Hazay, and J.S. Sorensen
  6. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC 1987: Proceedings of the nineteenth annual ACM symposium on Theory of computing, pp. 218–229. ACM, New York (1987)
  7. Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, New York (2004)
  8. 8,0 8,1 8,2 Knuth Jr., D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323–350 (1977)
  9. 9,0 9,1 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)
  10. Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654 (1976)
  11. El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)
  12. Jarecki, S., Xiaomin, L.: Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (2009)
  13. 13,0 13,1 Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient dna searching through oblivious automata. In: CCS 2007: Proceedings of the 14th ACM conference on Computer and communications security, pp. 519–528. ACM, New York (2007)
  14. 14,0 14,1 14,2 14,3 14,4 14,5 14,6 14,7 14,8 14,9 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)
  15. 15,0 15,1 Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: ASIACRYPT 2009, Tokyo, Japan. LNCS, pp. 250–267. Springer, Heidelberg (2009)
  16. 16,0 16,1 16,2 16,3 16,4 16,5 16,6 16,7 16,8 16,9 Jarecki, S., Shmatikov, V.: Efficient two-party secure computation on committed inputs. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 97–114. Springer, Heidelberg (2007)
  17. Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)
  18. 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)
  19. Hazay, C., Nissim, K.: Efficient set operations in the presence of malicious adversaries (2010)
  20. Groth, J., Ishai, Y.: Sub-linear zero-knowledge argument for correctness of a shuffle. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 379–396. Springer, Heidelberg (2008)
  21. Groth, J., Lu, S.: Verifiable shuffle of large size ciphertexts. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 377–392. Springer, Heidelberg (2007)