Двусмысленные схемы шифрования с пренебрежимыми вероятностями обнаружения: Интерактивные построения

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:00, 27 сентября 2015.
Deniable Encryption with Negligible Detection Probability: An Interactive Construction
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Markus Durmuth [@: 1]
David Mandell Freeman [@: 2]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

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

Введение

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

Понятие семантической безопасности оказалось очень полезным в большом количестве приложений. Однако существуют несколько сценариев, в которых семантической безопасности недостаточно. Например, семантическая безопасность не обеспечивает секретность сообщений, если противник может заставить отправителя или получателя сообщения раскрыть секретные ключи и/или случайность, которая была использована при формирования шифрования. В частности, семантическая безопасности не защищает схему шифрования от нападения, в том смысле, что если противник видит зашифрованный текст, а затем пытается заставить отправителя раскрыть все входы для шифрования (сообщения и случайность), тогда любые входы, показанные отправителем и согласующиеся с зашифрованным текстом, должны открыть истинное зашифрованное сообщение. В самом деле, многие схемы шифрования имеют только один набор возможных входов для зашифрованного текста. Это свойство шифрования может быть проблематичным в таких приложениях, как электронное голосования [2] или сохранение секретной информации при физических атаках, или в случае безопасных многосторонних вычислений при наличии адаптивного противника [3].

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

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

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

Наш вклад

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

Обзор нашего построения

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

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

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

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

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

Связанные работы

В дополнение к отрицаемости отправителя с -отрицанием, Канетти и соавт. [4] построили гибкую (то есть, с двумя алгоритмами) отправителя отрицаемую схему шифрования с незначительным отрицанием. Совсем недавно, О'Нил, Пейкер и Вотерс [5] объявили гибкую двусмысленную схему шифрования с незначительным отрицанием на основе структурного предположения. Мы рассматриваем эту последнюю работу по отношению к нашей: она не является интерактивной и достигает отрицания одновременно как для отправителя, так и для получателя, но построение использует различные честные и нечестные алгоритмы шифрования.

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

Некоторые подходы будут правдоподобно отрицающими. Этот термин обычно описывает инженерные методы, которые позволяют отрицать наличие зашифрованных данных или знание секретного ключа. Хорошо известным примером является система шифрования файлов TrueCrypt [6], где можно добавить секретные контейнеры внутрь зашифрованного блока, так что возможно отрицание их существования. Другой пример [7] использует стенографические измерения для скрытия зашифрованных данных в тексте. Эти методы не имеют формального доказательства или даже определения, и существуют атаки, которые могут выявить наличие и содержание зашифрованных данных [8]. Кроме того, эта форма отрицаемости обычно не подходит для онлайновых приложений, таких как электронное голосование.

Структура работы

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

Двусмысленное шифрование

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

для выполнения с входами и случайностями для и , соответственно. На выходе мы имеем для соответствующих сторон и открытые ключи .

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

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

Наше определение двусмысленного шифрования является перефразированием определение Канетти и соавт. [4] .

TemplateDifinitionIcon.svg Определение «Определение - Определение 2.1»
Пусть будет параметром безопасности. Эффективно вычислимый протокол для двух сторон и (отправителя и получателя, соответственно) называется – отправителе отрицаемой схемой шифрования открытого ключа, если выполнены следующие три условия:

Корректность: Мы говорим, что является правильным, если для всех сообщений мы имеем

для некоторой малой функции .

Пассивная безопасность: Две случайные величины определенные как

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

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

Следующие два распределения будут – вычислительно неразличимы:


Распределение слева создано реальным шифрованием со случайностью . Распределение справа получается, когда шифруем со случайностью , но говорим противнику, что случайность равна .

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

Не сложно показать, что отрицаемость (с малой ) подразумевает пассивную секретность.

TemplateLemmaIcon.svg Лемма «Лемма 2.2»
Двусторонний протокол , обладающий свойством отрицаемости из определения 2.1 для малой \mu (n) также обладает свойством пассивной секретности.

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


Отбирающее шифрование с открытым ключом

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

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

и алгоритм расшифровки как

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

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

TemplateDifinitionIcon.svg Определение «Определение - Определение 3.1»
Мы говорим, что является отбирающей, если выполнены следующие условия:
  • 1. Множество конечно, и распределение для

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

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

то следующие два распределения статистически неразличимы:

Заметим, что второе условие означает, что для всех малых значений мы получаем

Мы приводим два примера отбирающих схем шифрования в разделе 5.

Двусмысленный протокол шифрования

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

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

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

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

Когда Саре приходится раскрыть свою случайность, она покажет набор , в котором реальное шифрование из множества заменено на смоделированное шифрования из . Сара должна также показать распределенные случайности отбирающего шифрования. Однако, для этого она нуждается в помощи Рональда, в частности, ей нужен такой секретный ключ для индекса , что шифрует . Так как Рональд не может сказать, какое шифрование было отобрано случайным образом, то он отправляет обратно таких случайных пар индексов , что расшифровывают различные сообщения. Почти наверняка, он выберет хотя бы одну такую пару , что соответствует шифровке и соответствует шифровке , или наоборот. Сара отмечает такую пару, и Рональд посылает соответствующие секретные ключи . Знание секретных ключ для случайно сгенерированного шифротекста позволяет Саре использовать алгоритм SampleRand для создания случайностей, неотличимых от "реальных".

Теперь формально опишем нашу схему.

Протокол

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

  1. Входом для Рональда является параметр безопасности , обозначаемый как для простоты.
    • (a) Выбирает пару ключей для .
    • (b) Отправляет Саре.
  2. Входом для Сары будет бит . Сара вычисляет шифровок для и шифровок для при разных ключах, и выбирает дополнительных случайных шифротекстов:
    • (a) Выбирает случайное разбиение для непересекающихся подмножеств размера и соответственно.
    • (b) Для выбирает случайность шифрования , задает и вычисляет .
    • (с) Для , выбирает случайность шифрования , задает , и вычисляет .
    • (d) Для , выбирает случайный шифротекст .
    • (e) Отправляет Рональду.
  3. Рональд расшифровывает все шифротексты: задает для и выводит большинство .
  4. Рональд посылает пару индексов, соответствующих шифротекстам обратных сообщений, Саре.
    • (a) Устанавливает . Выполняет следующие действия для .
    1. Выбирает такую случайную пару индексов , что и
    2. Задает .
    • (b) Рональд посылает Саре.
  5. Сара выбирает такую пару индексов, что один из них принадлежит , а второй принадлежит :
    • (a) Выбирает такое случайное , что либо и , либо и . Если таких индексов не существует, то протокол останавливается.
    • (b) Отправляет Рональду.
  6. Рональд отправляет секретные ключи Саре.

На этом описание протокола заканчивается.

Стенограмма

Стенограмма протокола состоит из:

  1. Открытых ключей , отправленных Рональдом в шаге 1,
  2. Шифротекстов , отправленных Сарой в шаге 2e,
  3. Набора , отправленного Рональдом в шаге 4,
  4. Индексов , выбранных Сарой в шаге 5 (или решение остановиться), и
  5. Секретных ключей , отправленных Рональдом в шаге 6.

Алгоритм подмены Алгоритм Fake(подмены) определяется следующим образом: при заданном сообщении , случайность записывается как

для стенограммы . Если в видно, что протокол был прерван в шаге 5а, то алгоритм Fake выводит . В противном случае, выполняется следующие действия:

  1. Пусть и (В частности, мы имеем и ).
  2. Вычисляется
    • для
    • для
  3. Выводится

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

Ясно, что протокол работает за время кратное . Теперь покажем, что протокол практически никогда не прерывается в шаге 5а.

TemplateLemmaIcon.svg Лемма «Предположение 4.1»
Вероятность того, что Сара прерывает протокол в шаге 5а пренебрежима в .

Доказательство: Для задаем . По свойству 1 из определения 3.1 и для границ Чернова [9] мы имеем, с большой вероятностью для . Теперь в каждом исполнении шага 4(а)1, вероятность выбора пары либо для и , либо для </math> и , по крайней мере равна

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


Корректность

TemplateLemmaIcon.svg Лемма «Лемма 4.2»
Пусть будет отбирающей схемой шифрования открытого ключа, и пусть будет выходом Рональда, вычисленным . Тогда вероятность того (для и ), что , по крайней мере, равна .

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


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

где (*) следует из неравенства , которое в свою очередь вытекает из приближения Стирлинга [10].

Отрицаемость

TemplateTheoremIcon.svg Теорема Теорема 4.3
Пусть будет схемой шифрования открытого ключа. Если она семантически безопасна и делает отбор, то будет отправителе отрицаемой схемой шифрования.
Доказательство
Мы должны показать, что повторений удовлетворяют трем условиям определения 2.1 для малой . Лемма 4.2 показывает, что вероятность того, что сообщение Рональда равно сообщению Сары , по крайней мере, равна . Таким образом, повторение протокола раз и взятие большинства для дает правильный ответ c большой вероятностью при помощи границ Чернова [9].


Далее, лемма 2.2 показывает, что пассивная секретность вытекает из отрицаемости. Таким образом, осталось доказать только отрицаемость. Мы показываем, что если семантически безопасна и делает отбор, то для отдельного исполнения , два распределения из (2.3) будут -вычислительно неотличимы для некоторой малой . Если предположить, что это так, тогда стандартные рассуждения показывают, что соответствующие распределения для кратного параллельного повторения являются -вычислительно неотличимыми для некоторой малой .

Рассмотрим теперь единичное исполнение и определим серию игр. Игра будет выводить распределение левой части для (2.3), в то время как игра будет выводить распределение правой части для (2.3). Затем мы покажем, что для любого , выходы из игр и являются -вычислительно неотличимыми для некоторой малой . По неравенству треугольника, это означает, что два распределения в (2.3) будут --вычислительно неотличимы для некоторой малой .

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

--: Две стороны запускают протокол , как это определено в разделе 4.1, для входного сообщения и случайности для Сары, определенных формулой (4.1). Игра выводит сообщение , случайности , и стенограмму .

-: Две стороны запускают протокол, как в , но изменяют шаг 2d следующим образом:

  • (2d)' Для , выбираются случайные и , вычисляется прежние .

: Две стороны запускают протокол, как в Game1, но изменяют шаги 2e и 3, следующим образом:

  • (2e)' Рональду отправляется .
  • (3)' Рональд задает для всех и выводит большинство из .

Шифротексты теперь вычисляется во время выхода стенограммы. Выход тотже, как и в .

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

7.

  • (a) Выбирается случайное , не равное ни одному из индексов из шага 4, с .
  • (b) Вычисляется .

Выход тотже, что в , за исключением того, что выводится шифротекст вместо .

: Две стороны запускают протокол, как в , но теперь Сара изменяет все биты, которые она посылает Рональду (включая бит шифротекста ), в то же время вычисляя шифротекст в стенограмме для исходных битов (только с измененным ). Вновь опишем протокол, для простоты.

1. Рональд посылает пар ключей Саре.

2. Сара выполняет следующие действия:

  • (a) Выбирает случайное разбиение для непересекающихся подмножеств размера , и соответственно.
  • (2b)' Для выбирает случайность шифрования , задает и вычисляет .
  • (2с)' Для , выбирает случайность шифрования , задает , и .
  • (2d Для , выбирает случайные и , задает .
  • (2e Отправляет Рональду.

3." Рональд задает и выводит большинство .

4. Рональд посылает пару индексов, соответствующих шифротексту с противоположными сообщениями, назад Саре. (Этот шаг не идентичен соответствующему шагу в реальном протоколе).

5. Сара выбирает такую пару индексов, что один из них принадлежит , а второй принадлежит . (Этот шаг идентичен соответствующему шагу в реальном протоколе).

6. Рональд отправляет секретные ключи Саре.

7.

  • (a) Выбирается случайное , не равное ни одному из индексов из шага 4, с .
  • (b) Пусть для всех , и пусть .

Выход тотже, что в .

 : Две стороны запускают протокол, как в , но теперь Сара использует измененные биты для вычисления всех шифротекстов (включая шифротекст ).

7. Задается для всех .

8. Игра выводит стенограмму протокола и вычисляет поддельную случайность:

  • для
  • для

Мы задаем как в (4.2), и игра выводит вместо .

: Две стороны запускают протокол, как в , но Сара подделывает случайность для зашифрованного текста с индексом , выбирая . (Напомним, что ). Это выводится в соответствии с . За исключением этого изменения, вывод будет такой же, как в .

: Мы обращаем изменения, сделанные в и , задав

  • (2b-2d) Задается для всех .
  • (2e) Рональду посылается .
  • (3) Задается для и выводится большинство

: Мы обращаем изменения, сделанные в и задав

  • (2d) Для выбирается случайный шифротекст .

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

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

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

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

: Обратим внимание, что выход Рональда в шаге 4, а также остаток протокола, зависят только от открытых текстов сообщений, которые он получает в Шаг 2e. Поскольку Сара теперь знает все тексты, она может послать их в шаге 2e и вычислить для стенограммы позже. Таким образом, распределения выходов для и идентичны.

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

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

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

: Во-первых, распределение не меняется, а следовательно, распределение тоже. Во-вторых, обратим внимание, что процесс выбора пары на шаге 4 одинаков для и : так как Рональд выбирает пару индексов с противоположными открытыми текстами, то изменение всех битов для Рональда не влияет на этот выбор. Кроме того, поскольку расчет Сары для на шаге 5 зависит только от положения индексов в наборах , то расчет Сары для с использованием измененных битов точно такой же, как для вычислений в . Таким образом, распределения выходов для и идентичны.

: Пусть будет перестановкой порядка 2, применяемой к , и

Обратим внимание, что, в частности, это означает, что и .

Для всех , мы имеем и , а для всех , мы имеем и . Индекс появляется только на выходе, в качестве шифротекста , так что выход распределяется как  ; кроме того, мы имеем в .

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

  • Запуск для шифрования бита со случайностью , создание записи , и вывод и . (То есть, мы применяем перестановку для всех индексов вычисляемых элементов).
  • Запуск Game5 для шифрования бита со случайностью , создание записи и вывод и .

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

: Тот факт, что осуществляет отбор, означает, что эти два распределения статистически неразличимы.

Пусть задан секретный ключ , шифротекст , и случайность для одного из двух распределений (3.2). Мы можем смоделировать протокол, используя вместо , вместо , и вместо . Когда выбирается из , мы находимся в , и когда вычисляется через алгоритм SampleRand, мы находимся в . Таким образом, любой противник, который может различать эти две игры, способен выделить два распределения (3,2), что противоречит нашему описанию для .

: По тем же соображениям, что и для , выходы из этих двух игр идентичны.

: По тем же соображениям, что и для , и учитывая, что осуществляет отбор, результаты этих двух игр статистически неразличимы.

Применение

Квадратичные вычеты

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

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

Построение 5.1

  • Вычисляется , где являются -битными простыми числами. Выберите квадрант . Открытым ключом будет и секретным является .
  • Выбирается и выводится .
  • Пусть . Если , то выводится , в противном случае .
  • Если , то выводится случайное решение ; в противном случае выводится случайное решение .

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

TemplateLemmaIcon.svg Лемма «Предположение 5.2»
Схема шифрования открытого ключа из построения 5.1 будет осуществлять отбор.

Доказательство: В обозначениях определения 3.1, множество это , а множество это . Распределение является равномерным для . Поскольку , тогда распределение (3.1) будет равномерным распределением для .

Для второго условия, мы отметим, что для заданного значение распределено равномерно среди четырех возможных значений для , при . Так как реальная случайность вытекает из равномерного распределения , то два распределения (3,2) будут идентичны.


Односторонние перестановки

Наша вторая отбирающая схема шифрования строится на общих перестановках (см. [11, построение 10.27]):

Построение 5.3

  • Пусть выбирается из множества перестановок (при использовании в качестве параметра безопасности), и пусть . Пусть будет предикатом для . Открытым ключом будет , и секретным .
  • Выбирается и выводится .
  • Записывается и выводится .
  • Записывается и выводится .

Стандартным результатом (см. [[11], теорема 10.28]) будет то, что если это множество перестановок, то схема шифрования будет семантически безопасной. В частности, при RSA предположении мы позволяем быть функцией с предикатом [12] .


TemplateLemmaIcon.svg Лемма «Предположение 5.4»
Схема шифрования открытого ключа из построения 5.3 будет осуществлять отбор.

Доказательство: Поскольку берется равномерно из и является перестановкой, то первый компонент шифротекста будет равномерно распределен в . Кроме того, если это равномерно случайный бит, тогда второй компонент шифротекст является случайным и независимым от первого. Таким образом, распределение (3.1) является равномерным распределением в .

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


Заключение и открытые проблемы

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

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

Обе наши схемы основаны на сложности факторизации. Открытым остается вопрос о построении двусмысленной схемы шифрования из других предположений. Перспективным направлением для решения этой проблемы являются криптосистемы, основанные на сложности обучения с ошибкой (LWE), и структурных проблемах. В частности, LWE криптосистема Регева [13], представленная Джентри, Пейкертом и Вайкунатахом [13] обладает свойством, что перестановки могут быть встроены в секретный ключ, который позволяет его держателям эффективно выбирать из распределения случайностей, используемого в шифровании. Тем не менее, схема не имеет достаточного пространства для шифротекста, так что схема не осуществляет отбора, в соответствии с нашими определениями. До сих пор все методы, которые мы рассматривали для преодоления этой трудности, либо приводят с большой вероятностью к неравномерному распределению для реальных шифротекстов, либо уничтожают безопасность системы.

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

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

  1. Ruhr-University Bochum, Germany E-mail: [1]
  2. Stanford University, USA E-mail: [2]

Литература

  1. 1,0 1,1 1,2 1,3 Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984); preliminary version in 14th Annual ACM Symposium on Theory of Computing (STOC)
  2. Sako, K., Kilian, J.: Receipt-free mix-type voting scheme: A practical solution to the implementation of a voting booth. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 393–403. Springer, Heidelberg (1995)
  3. 3,0 3,1 Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation.In: STOC. pp. 639–648 (1996)
  4. 4,0 4,1 4,2 4,3 4,4 4,5 Canetti, R., Dwork, C., Naor, M., Ostrovsky, R.: Deniable encryption. In: Kaliski Jr., B.S.(ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 90–104. Springer, Heidelberg (1997)
  5. 5,0 5,1 O’Neill, A., Peikert, C.,Waters, B.: Bi-deniable public-key encryption (2010) (manuscript)
  6. TrueCrypt: Free open-source disk encryption software,http://www.truecrypt.org/
  7. Chapman, M., Davida, G.: Plausible deniability using automated linguistic stegonagraphy.In: Davida, G.I., Frankel, Y., Rees, O. (eds.) InfraSec 2002. LNCS, vol. 2437, pp. 276–287.Springer, Heidelberg (2002)
  8. Czeskis, A., Hilaire, D.J.S., Koscher, K., Gribble, S.D., Kohno, T., Schneier, B.: Defeating encrypted and deniable file systems: TrueCrypt v5.1a and the case of the tattling OS and applications. In: 3rd Usenix Workshop on Hot Topics in Security (2008)
  9. 9,0 9,1 Ross, S.: A First Course in Probability, 5th edn. Prentice-Hall, Englewood Cliffs (1998)
  10. Spitzer, F.: Principles of Random Walks, 2nd edn. Graduate Texts in Mathematics, vol. 34. Springer, Heidelberg (1976)
  11. Katz, J., Lindell, Y.: Introduction to modern cryptography. Chapman & Hall/CRC, Boca Raton (2008)
  12. Alexi, W., Chor, B., Goldreich, O., Schnorr, C.P.: RSA and Rabin functions: Certain partsare as hard as the whole. SIAM J. Comput. 17(2), 194–209 (1988)
  13. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 197–206. ACM, New York(2008)

Благодарности

Авторы благодарят Дэна Боне, Криса Пейкерта, Брента Вотерса и анонимным рецензентам за полезные советы и обратную связь при написании более ранних версий данной работы.