Пристальный взгляд на анонимность и надёжность в системах шифрования

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 09:58, 17 ноября 2015.
A Closer Look at Anonymity and Robustness in Encryption Schemes
A Closer Look at Anonymity and Robustness.png
Авторы Payman Mohassel[@: 1]
Опубликован 2010 г.
Сайт Computer Science Department,
University of Calgary
Перевели Roman Chistiakov
Год перевода 2015 г.
Скачать оригинал
Аннотация. В этой работе мы обращаем пристальное внимание на анонимность и криптостойкость в системах шифрования. Грубо говоря, анонимная схема шифрования скрывает личность держателя секретного ключа, в то время как криптоустойчивая схема гарантирует, что любой шифр-текст может быть верно расшифрован только с помощью секретного ключа, имеющегося у предполагаемого получателя.
В случае анонимного шифрования, мы показываем, что если анонимная схема шифрования с открытым ключом или основанная на идентификации (в случае атак с выбранным шифр-текстом (CCA)) используется в гибридном шифровании, то надежды на анонимность полученного шифрования не оправдываются. Мы показываем, что это происходит даже если анонимна компонента симметричного шифрования. С другой стороны, мы доказываем, что если метод инкапсуляции ключа вдобавок обладает слабой криптостойкостью, то полученное гибридное шифрование остаётся анонимным. Некоторые существующие анонимные криптосистемы известны как слабо криптостойкие, что делает их более привлекательными на практике.
В случае криптостойкого шифрования, мы создаём некоторые эффективные конструкции для преобразования любых PKE/IBE схем в слабо или сильно криптостостойкие. Наши конструкции добавляют совсем небольшие вычислительные издержки к оригинальным схемам, и дают шифр-тексты лучшего размера. Важное свойство наших трансформаций заключается в том, что они неключевые и не требуют никаких модификаций открытых параметров исходных схем.
Мы также представляем упрощение понятия крипостойкости, которое мы называем «свободой от коллизий». В первую очередь мы используем «свободу от коллизий» в качестве промежуточного понятия, показывая более эффективные конструкции для трансформации любой «свободной от коллизий» схемы шифрования в сильно криптостойкую. Мы верим, что эта простое понятие может успешно заменить криптостойкость в некоторых ситуациях на практике. Её достоинство в том, что большинство существующих криптосистем являются «свободными от коллизий» без каких-либо модификаций.

Вступление

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

Анонимность в гибридных схемах шифрования

Концепция анонимности в криптосистемах существует давно, однако была впервые формализована в контексте симметричных криптосистем [7][8][9], а позже была расширена на понятия шифрования с открытым ключом (PKE) и шифрования, основанного на идентификационной информации (IBE)[4][5]. Некоторые PKE и IBE системы в литературе, такие как Крамер-Шуп[10] и Бойен-Вотерс [11] в стандартной модели и DHIES [12] и Бонэ-Франклин [13] в модели случайного оракула являются анонимными. Однако в большинстве случаев PKE и IBE системы используются в качестве методов инкапсуляции ключа (KEM), чтобы зашифровать случайный ключ, который затем используется для шифрования сообщения при помощи симметричного метода инкапсуляции данных (DEM). Хорошо известно, что если KEM-компонента IND-CCA безопасна, а DEM-компонента IND-CCA, то результирующее гибридное шифрование также IND-CCA безопасно (например, [10])[п. 1]. Важно определить, можно ли утверждать подобное относительно анонимности.

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

Важное следствие: Построения ANON-CCA PKE или IBE схем недостаточно, чтобы гарантировать анонимность на практике, где чаще всего используются гибридные системы.

Положительный результат. С другой стороны, мы показываем, что если KEM-компонента обладает слабой криптостойкостью (см. определение в разделе 2), результирующая гибридная система получается CCA-анонимной. Это означает, что несмотря на наш отрицательный результат, использование большинства известных ANON-CCA систем, таких как Бонэ-Франклин, Крамер-Шуп и DHIES, которые известны как слабо криптостойкие [6], сохраняет анонимность. Это, в свою очередь, неверно для анонимной IBE схемы Бойена-Вотерса, которая не является слабо криптостойкой. Результат подчёркивает тесную взаимосвязь между анонимностью и криптостойкостью при проектировании анонимных схем шифрования.

Криптостойкость

Говоря неформальным языком, слабая криптостойкость означает, что шифр-текст не расшифровывается в корректный текст при использовании разных секретных ключей для двух различных личностей. Более криптостойкая версия требует, чтобы это было верно также для намеренно выбранных шифр-текстов. Концепция криптостойкости так или иначе изучается в [14] и [15], однако лишь недавно была формализована Абдалла и другими[6]. Нетрудно заметить, что достигнуть криптостойкости можно просто дописывая ключ к шифр-тексту и проверяя его при расшифровании. Основной недостаток заключается в том, что полученная криптосистема более не является анонимной. На самом деле, как обсуждается в [6] и далее подтверждается нашими результатами исследований анонимности гибридного шифрования, совершенно точно, что криптостойкость важна для анонимности систем. В [6] авторы изучают свойства криптостойкости некоторых существующих анонимных криптосистем и проектируют общие конструкции для преобразования любой IBE/PKE схемы в криптостойкую. Преобразование называют ключевым, если необходимо добавить дополнительные строки к списку публичных параметров оригинальной схемы и неключевым в противном случае. Важное достоинство неключевых конструкций в том, что свойство криптостойкости может быть добавлено без необходимости оповещения третьей стороны, такой как инфраструктура открытых ключей. Следовательно, пользователи системы могут добавить криптостойкость в схему уже после её запуска.

Неключевые трансформации для криптостойкости. В стандартной модели, мы проектируем неключевые конструкции для преобразования любой анонимной IBE/PKE схемы в слабо криптостойкую относительно атак CPA. В модели случайного оракула мы проектируем неключевые трансформации, которые обеспечивают сильную криптостойкость относительно атак CCA. В обоих случаях вычислительные издержки очень малы (они включают от одного до трёх вызовов хеш-функции), а также несмотря на то, что трансформация неключевая, размеры получаемых шифр-текстов лучше, чем раньше. Любопытный вопрос, остающийся открытым: можем ли мы получить подобную трансформацию в стандартной модели.

Свобода от коллизий. Мы также изучаем понятие свободы от коллизий, естественное упрощение понятия криптостойкости. Грубо говоря, криптосистема свободна от коллизий, если шифр-текст не расшифровывается в одно и то же сообщение при использовании разных ключей. Свобода от коллизий может быть достаточным свойством в некоторых сценариях на практике. Например, если получатель ожидает увидеть конкретное сообщение в качестве части протокола, но после расшифрования с использованием своего секретного ключа обнаруживает другое, он может определить ошибку и прекратить связь. Мы показываем, что схемы, такие как PKE-схема Эль-Гамаля [16] и IBE-сехма Бойена-Вотерса[11] строго свободны от коллизий, несмотря на то, что они не являются даже слабо криптостойкими. Следовательно, свобода от коллизий – менее строгое суждение о криптосистеме и большинство криптосистем удовлетворяют ей без каких-либо модификаций. Что более важно, мы проектируем более эффективные конструкции, преобразующие любую свободную от коллизий криптосистему в сильно криптостойкую.

Предварительно

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

пренебрежимо мало для любого PPT инвертора .

Общие схемы шифрования. Абдалла и другие [6] представили и использовали понятие общей схемы шифрования, которая включает в себя и PKE и IBE схемы. Мы тоже будем использовать это понятие, так как наши преобразования применимы и к PKE, и к IBE схемам. Общая схема шифрования (GE) представляет из себя кортеж алгоритмов. Алгоритм генерации параметров не имеет входных параметров и возвращает общие параметры и главный секретный ключ . Генератор ключа по входу , генерирует шифрующий ключ и расшифровывающий ключ . Шифрующий алгоритм по входу генерирует шифртекст для открытого текста . Детерминированный расшифровывающий алгоритм по входу возвращает исходный текст или , символизируя отказ. GE является PKE схемой, если и игнорирует параметр . GE является IBE схемой, если , что означает, что ключ, созданный алгоритмом по входу всегда совпадает с . Таким образом, мы получили, что понятие общего шифрования включает PKE схемы, IBE схемы и другие. Другими словами, существуют общие схемы шифрования, не являющиеся ни PKE, ни IBE схемами.

AI-{CPA,CCA} безопасность. Традиционно, определения приватности[1][2][3] и анонимности[4][5] для схем шифрования вводятся отдельно. Однако, при рассмотрении криптостойкости имеет смысл рассматривать эти понятия одновременно. Далее в тексте мы следуем определению из[6], которое объединяет эти два. Мы определяем AI-{CPA,CCA} безопасность (AI=ANON+IND) общей схемы шифрования через игру между испытателем и противником.

  • Установки: испытатель запускает
  • Запросы:
    • Запрос публичного ключа . Испытатель допускает и возвращает .
    • Запрос ключа расшифрования . Если или возвращает . Иначе и возвращает .
    • Запрос расшифрования . Если или возвращает . Иначе допускает и возвращает .
    • Испытательный запрос . Если или или или , возвращает . Иначе допускает и возвращает .
  • Предположение противника: противник возвращает бит

Обратите внимание, что используется только один испытательный запрос. В случае CPA атак не допускаются запросы расшифрования. Преимущество противника в AI-{CPA,CCA} игре:

Однако в некоторых случаях мы обсуждаем понятия анонимности (ANON-{CPA,CCA}) и неразличимости (IND-{CPA,CCA}) раздельно. Испытательный запрос в вышеприведённой игре может быть очевидным образом изменён, чтобы удовлетворять каждому из этих определений в отдельности. Обращаем ваш внимание, что подобные определения могут быть также применены в случае симметричного шифрования.

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

  • Установки: испытатель запускает
  • Запросы:
    • Запрос публичного ключа . Испытатель допускает и возвращает .
    • Запрос ключа расшифрования . Если или возвращает . Иначе и возвращает .
    • Запрос расшифрования . Если , возвращает . Иначе допускает и возвращает .
    • Заключительное сообщение (для WROB). Если или или или или , возвращает . Иначе допускает если возвращает , иначе возвращает
    • Заключительное сообщение (для SROB). Если или или или или , возвращает . Иначе допускает если и возвращает , иначе возвращает .

Подобно вышеописанному, в случае CPA атак не допускаются запросы расшифрования. Преимущество противника в {WROB,SROB}-{CPA,CA} игре:

В WROB игре противник создаёт сообщение , а – соответствующий ему шифр-текст с использованием ключа шифрования для одной из предоставленных личностей, в то время как противник в SROB игре создаёт C напрямую и не может получить его в результате честного шифрования. Заметьте, что в случае PKE схем противник не может выбирать ключи шифрования для личностей, на которые он нацелен. Они честно и независимо выбираются личностями самостоятельно, как в реальной жизни, так и в вышеприведённых играх.

Анонимное CCA гибридное шифрование

В этом разделе мы рассматриваем анонимные схемы шифрования в условиях атаки с выбранным шифр-текстом (ANON-CCA), определённые в разделе 2. Предыдущие работы в области шифрования с открытым ключом и шифрования, основанного на идентификации [4][5], изучили эти понятия и предоставили удовлетворяющие им конструкции. Однако в большинстве сценариев на практике, PKE и IBE схемы используются в рамках KEM/DEM парадигмы. Известно, что если KEM-компонена является IND-CCA безопасной и DEM-компонента в то же время IND-CCA, полученное гибридное шифрование также IND-CCA безопасно. По практическим соображениям, важно определить, можем ли мы утверждать подобное, говоря об анонимности полученной конструкции. Конкретно, мы пытаемся ответить на следующий вопрос: Если имеется ANON-CCA PKE или IBE схема и (ANON-CCA +IND-CCA) симметричная схема, будет ли результирующая гибридная схема шифрования ANON-CCA?

Отрицательный результат

Несколько неожиданно, мы отвечаем на приведённый выше вопрос отрицательно. Сперва мы приводим контрпример, объединяя ANON-CCA безопасную PKE/IBE схему и симметричное IND-CCA шифрование, так что анонимность полученной гибридной конструкции легко нарушается. Отрицательный результат легко обобщается на случай, когда симметричная компонента также является ANON-CCA. Важный вывод заключается в том, что для обеспечения анонимности на практике, там, где чаще всего схемы шифрования используют гибридные конструкции, недостаточно создания ANON-CCA PKE или IBE схемы.

TemplateExampleIcon.svg Пример Утверждение 31.
Существуют ANON-CCA PKE/IBE схема и симметричная аутентифицирующая схема шифрования (при условии, что сами по себе они безопасны) такие, что результирующее гибридное шифрование не является ANON-CCA.

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

TemplateExampleIcon.svg Пример Доказательство
Мы приводим доказательство для случая PKE схемы, но для IBE схем доказательство аналогично. Пусть (ANON-CCA + WROB-CCA) PKE схема шифрования. Подойдёт схема Крамера-Шупа или любая другая конструкция из данной статьи. Мы строим схему , оставляя алгоритмы генерации ключа и шифрования такими же, как и в и модифицируя алгоритм расшифрования таким образом, что если алгоритм возвращает символ , алгоритм должен возвращать , в остальных случаях он работает аналогично . Легко убедиться, что после такой модификации, остаётся ANON-CCA. в нашем контрпримере будет методом инкапсуляции ключа.


Для DEM компоненты мы используем IND-CCA схему, которая также связывающей ключ (понятие, представленное в [9]).

TemplateDifinitionIcon.svg Определение «Определение 1.»
Симметричная схема шифрования называется связывающей ключ, если для любого ключа , сгенерированного , любого сообщения и случайного , не существует ключа такого, что и .

Свойство связывания ключа гарантирует, что шифр-текст, полученный с использованием одного секретного ключа, не может быть корректно расшифрован с использованием другого секретного ключа. Фишлин[9] показал простой способ конструирования таких криптосистем из любого PRF. Для нашего контрпримера достаточно знать, что криптосистема с таким свойством существует. Теперь покажем, что соединение и в гибридное шифрование не является ANON-CCA. В частности, атакующий может нарушить анонимность схемы используя приведённую ниже простую стратегию. Вернёмся к ANON-CCA игре. Атакующий изначально посылает сообщение в качестве испытания в ANON-CCA игре и получает шифр-текст для случайного бита и случайного ключа . Затем А делает запрос расшифрования для шифр-текста с использованием публичного ключа для произвольного сообщения . Если ответ , возвращает , иначе . Чтобы увидеть, почему А нарушает ANON-CCA защиту схемы шифрования, отметьте, что если , то , согласно тому, как мы определили . С этого момента мы имеем . С другой стороны, если , то . Мы имеем согласно свойству связывания ключа схемы и тому факту, что с ничтожной вероятностью. Таким образом, с большой вероятностью верно угадывает бит . Пристальный взгляд на приведённую выше стратегию открывает, что для принятия нашего утверждения достаточно гораздо более слабого свойства, чем приведённое в определении 1. В частности, достаточно выполнения свойства связывания ключа для фиксированного сообщения и фиксированного секретного ключа ( и соответственно).

Усиление DEM-компоненты? Одно из потенциальных решений – использовать симметричную схему шифрования, которая имеет некоторые дополнительные свойства. В частности, один из вопросов заключается в том, позволит ли использование анонимного в условиях атаки с использованием выбранного шифр-текста симметричного шифрования в качестве DEM-компоненты создать анонимную гибридную конструкцию. К сожалению, ответ на этот вопрос также отрицательный. Легко показать, что приведённый выше отрицательный результат расширяется на любое понятие безопасности, связанное с симметричным шифрованием, если оно связано со свойством связывания ключа. Во всех таких случаях приведённое выше доказательство работает без существенных изменений. Анонимность симметричных криптосистем изучается в[9] под названием скрытие ключа. Авторы также создают IND-CCA безопасные симметричные криптосистемы, являющиеся одновременно скрывающими ключ и связывающими ключ. Это приводит к следующему утверждению:

TemplateExampleIcon.svg Пример Утверждение 32.
Существуют такие ANON-CC PKE/IBE схемы и (ANON-CCA + IND-CCA) симметричные схемы, что получаемое гибридное шифрование не является ANON-CCA.

Положительный результат

В свете полученных отрицательных результатов, напрашивается вопрос, какие же дополнительные свойства необходимы KEM компоненте для обеспечения ANON-CCA безопасности гибридной конструкции. Мы показываем, что если KEM-компонента обладает слабой криптостойкостью, гибридное шифрование получается ANON-CCA. Это означает, что несмотря на полученные выше отрицательные результаты, использование большинства известных ANON-CCA схем таких как Бонэ-Франклин IBE, Крамер-Шуп PKE и DHIES PKE, которые являются слабо криптостойкими[6], в гибридной конструкции является безопасным. Основная мысль доказательства заключается в том, что слабая криптостойкость гарантирует предсказуемое поведение расшифровывающего алгоритма во время расшифрования с использованием различных секретных ключей, и эта предсказуемость хорошо комбинируется со свойствами аутентифицирующей симметричной схемы, а именно IND-CCA безопасностью и целостностью шифр-текста (CTXT-INT). В последующем утверждении мы доказываем более сильный результат, чем нам необходимо при обсуждении понятия IA-CCA безопасности, которая комбинирует ANON-CCA и IND-CCA безопасность в одно определение. Основная причина в том, что это более сильное утверждение потребуется нам в следующем разделе. Доказательство для случая, когда необходима только ANON-CCA безопасная гибридная схема, аналогично.

TemplateTheoremIcon.svg Теорема Утверждение 33.
Если KEM-компонента гибридной конструкции является (AI-CCA + WROB-CCA) общим шифрованием и – одноразовое аутентифицирующее симметричное шифрование, тогда результирующее гибридное шифрование также является AI-CCA общей схемой шифрования.
Доказательство
Докажем утверждение через последовательность игр.

Игра 0. Это просто AI-CCA игра. Обозначим через случайный бит, сгенерированный испытателем, через испытательный шифр-текст , где – KEM-компонента и – DEM-компонента и через – секретный ключ, используемый DEM-компонентой.

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

Игра 2. Эта игра подобна игре 1 за исключением того, что в ответ на любой запрос расшифрования вида для , где и , испытатель возвращает . Заметьте, что игры 1 и 2 отличаются только если , т.е. зашифрованное с помощью сообщение также верно расшифровывается с использованием . Это возможность связана с преимуществом противника при выигрывании WROB-CCA игры и далее:

Игра 3. Эта игра подобна игре 2 за исключением того, что испытатель генерирует и использует случайный ключ (вместо ) при расшифровании компоненты закрытого ключа шифр-текста для испытательного запроса. Отличие между преимуществами противника в играх 2 и 3 связано с AI-CCA безопасностью в PKE-схеме:

Игра 4. Модифицируем игру 3 двумя способами. Во-первых, для испытательного запроса вместо шифрования сообщения испытатель шифрует константу . Во-вторых, для запросов расшифрования с использованием , где , испытатель возвращает {\bot}. Вероятность определения первого изменения зависит от IND-CCA преимущества противника в схеме, в то время как для второго изменения вероятность зависит от преимущества противника, играющего с целостностью шифр-текста (CTXT-INT) для . И IND-CCA, и CTXT-INT безопасность – свойства, имеющиеся у любой аутентифицирующей схемы шифрования.

Легко видеть, что вид противника в игре 4 не зависит от бита , так что преимущество противника в угадывании b – ровно . Объединяя всё вышесказанное, имеем:

Неключевые трансформации для криптостойкости

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

Преобразование AI-CPA схем

Следующая неключевая конструкция преобразует любую AI-CPA схему в (AI-CPA + WROB-CPA) схему. Конструкция 41. Пусть – AI-CPA общая схема шифрования и пусть – односторонняя функция над . Построим общую схему шифрования :

  • Генерация параметров (): По входу возвращает .
  • Генерация ключа (): По входу , , , возвращает .
  • Шифрование (): По входу , , генерирует случайное и возвращает
  • Расшифрование (): По входу , , , вычисляет . Если и возвращает ; иначе возвращает .

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

Сравнение эффективности. . Для реализации нашей схемы можно использовать криптографическую хэш-функцию фиксированной длины с выходом длины 128 бит (например, полученную соответствующим изменением длины выхода хэш-функции семейства SHA). Нам нужно только 128 бит по причине того, что от хэш-функции нам требуется только чтобы она была односторонней, но не защищённой от коллизий. Более того, при выборе из нам достаточно положить [п. 2]. Это означает, что PKE схема должна расшифровывать сообщение, которое только на 256 бит длиннее оригинального, а шифр-текст максимально расширяется аддитивным фактором в 384 бита против 768 бит в конструкции Абдалла и др.[6].

TemplateTheoremIcon.svg Теорема Теорема 1.
Пусть – AI-CPA безопасная общая схема шифрования, а – односторонняя фукнция. Тогда, схема из конструкции 41 является и AI-CPA и WROB-CPA безопасной.
Доказательство
Мы доказываем эту теорему через два отдельных утверждения. Утверждение 42 гарантирует, что приведённое выше преобразование сохраняет AI-CPA безопасность оригинальной схемы. Утверждение 43 устанавливает, что полученная схема также является слабо криптостойкой.
TemplateTheoremIcon.svg Теорема Утверждение 42.
Для любого PPT противника против существует PPT противник против такой, что
Доказательство
запускает . Когда посылает испытательный запрос , генерирует случайное значение и посылает своему испытателю в AI-CPA игре для . получает и посылает противнику . Запросы ключа расшифрования, сделанные , перенаправляются соответствующему оракулу в игре . Поскольку мы рассматриваем только CPA атаки, запросы расшифрования на и недопустимы. В конечном счёте, возвращает бит . также возвращает бит и останавливается. Очевидно, что преимущество перед такое же, как преимущество перед схемой.
TemplateTheoremIcon.svg Теорема Утверждение 43.
Для любого PPT противника против в WROB-CPA игре существуют PPT противник против в AI-CPA игре и против в игре односторонности, такие, что:
Доказательство
Мы доказываем это утверждение при помощи последовательности из двух игр.


Игра 0. Игра 0 – это WROB-CPA игра против схемы, определённая ранее. Если подробнее, противник посылает кортеж испытателю. Испытатель вычисляет для случайного . Затем он вычисляет . Если , испытатель возвращает , иначе .

Игра 1. Эта игра похожа на игру 0 за исключением того, что вычисляется следующим образом:

В остальном, игра остаётся точно такой же. Сначала покажем, что существует противник такой, что . запускает и получает кортеж . посылает ключевому оракулу запрос . Затем он генерирует случайное и посылает испытатель в IND-CPA игре против и получает для случайного бита . Затем расшифровывает , используя алгоритм и секретный ключ . Если результат расшифрования не , допускает , а иначе . Итак, мы имеем:

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

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

Собираем всё вместе:

Преобразование для AI-CCA схем

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

  • Генерация параметров(): По входу возвращает .
  • Генерация ключа(): По входу возвращает .
  • Шифрование(): По входу генерирует случайное и возвращает .
  • Расшифрование (): По входу вычисляет . Если или , возвращает , иначе вычисляет если , возвращает , иначе .

Эта конструкция – адаптация ранней версии схемы OAEP[17], основанной на любой односторонней функции с потайным входом (TDF). Два основных отличия в том, что, во-первых, мы преобразуем случайную схему шифрования вместо односторонней TDF, из-за чего мы используем для создания случайности в алгоритме шифрования и, во-вторых, поскольку наша цель – достигнуть криптостойкости, третья часть шифр-текста хэширует открытый ключ вместе с сообщением и случайной составляющей. Также интересно, что в отличие от оптимизированной OAEP схемы [18], которая шифрует как часть сообщения (с целью сокращения длины шифр-текста), из-за невозможности результата [6], который исключает неключевые избыточные коды, нет никаких шансов сделать то же самое в нашем случае.

Сравнение эффективности. Издержки длины шифр-текста состоят в двух хэш-значениях, каждое из которых даёт увеличение в 512 бит. Другое существующее решение – скомбинировать слабо криптостойкое шифрование с преобразованием[6] «из слабого в сильное». Это даёт бит, где – излишек преобразования, который сам по себе может быть достаточно большим (в зависимости от конкретного исполнения схемы).

TemplateLemmaIcon.svg Лемма «Теорема 2.»
Пусть – AI-CCA защищённая общая схема шифрования и и – случайные оракулы. Тогда схема с конструкцией 44 является и AI-CCA и SROB-CCA безопасной.

Мы доказываем эту теорему через два отдельных утверждения. Утверждение 45 гарантирует, что приведённое преобразование сохраняет AI-CCA безопасность исходной схемы. Утверждение 46 устанавливает, что полученная схема также является слабо криптостойкой.

TemplateTheoremIcon.svg Теорема Утверждение 45.
Для любого PPT противника против существует PPT противник против такой, что:
Доказательство
Доказательство. Докажем утверждение через последовательность игр.

Игра 0. В этой игре противник играет в AI-CCA игру с испытателем, используя вышеприведённую конструкцию. Испытатель задаёт три пустых списка , и . Любой запрос к оракулу, сделанный к или , возвращает в качестве ответа, если кортеж вида присутствует в или . Иначе испытатель генерирует случайное , добавляет в или и возвращает противнику. Обозначим испытательный запрос противника через , а ответный шифр-текст через для случайного бита и . Испытатель отвечает на запросы расшифрования, используя вышеописанный алгоритм. В конечном счёте, противник возвращает бит и побеждает, если . Для любого PPT противника имеем:

Игра 1. Эта игра подобна игре 0 за исключением того, что в ответ на запросы расшифрования в форме , где , если в имеется кортеж вида , испытатель анализирует и пересчитывает первые две компоненты шифр-текста, используя эти значения. Если они соответствуют и , присланным противником, он возвращает . Если значения не совпадают или кортеж вида отсутствует, испытатель возвращает . Для эти две игры отличаются только если он не знает запросы из списка, но может предположить . Это возможно с вероятностью для каждого запроса расшифрования. Таким образом,

Игра 2. Эта игра идентична игре 1 за исключением того, что если делает запрос к оракулу для или с входом , где – случайное сообщение, зашифрованное в шифр-тексте испытателя, испытатель возвращает и покидает игру. Согласно основной лемме игр, имеем:

Далее, свяжем вероятность получить с преимуществом противника , играющего в игру CCA-односторонности против схемы . Покажем, что для любого противника , побеждающего в игре , существует PPT противник , побеждающий в игре CCA-односторонности против оригинальной схемы. генерирует случайный индекс , затем запускает . Когда делает свой испытательный запрос , генерирует случайный бит и запрашивает шифр-текст с , чтобы получить для случайного сообщения . вычисляет и самостоятельно и отправляет противнику . В ответ на запрос к любому из трёх оракулов, если это запрос -го оракула, возвращает своему испытателю и останавливается. Иначе, если было запрошено ранее, он возвращает тот же ответ, а если нет – генерирует случайный ответ и добавляет кортеж в соответствующий список. В ответ на запрос расшифрования , где , использует собственный расшифрующий оракул для и выполняет алгоритм расшифрования . В этот момент для случайной составляющей критично быть извлекаемой из расшифрованного сообщения, вот почему используется в качестве случайности (иначе не сможет использовать компоненту подтверждения из алгоритма). Для любого запроса расшифрования , где , выполняет ровно то, что делает испытатель в игре 1. Легко видеть, что

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

Если не делает запросы оракулу, шифр-текст совершенно не зависит от бита , а значит,

Собирая всё вместе, имеем:

TemplateTheoremIcon.svg Теорема Утверждение 46.
Для любого противника против имеем .
Доказательство
Доказательство этого утверждения просто. Центральное наблюдение заключается в том, что шифр-текст корректен с использованием двух разных открытых ключей только если , где . Однако это происходит только с вероятностью из-за того факта, что – случайный оракул.


Свободное от коллизий шифрование и криптостойкость

В этом разделе мы представляем понятие свободы от коллизий, естественное упрощение понятия криптостойкости для общих схем шифрования. Свобода от коллизий требует, чтобы при использовании разных секретных ключей шифр-текст расшифровывался в два разных открытых сообщения. Основная идея заключается в том, чтобы использовать свободу от коллизий как отправную точку для создания криптостойких схем шифрования. В частности, мы проектируем более эффективную конструкцию для преобразования свободных от коллизий схем шифрования в сильно криптостойкие. Однако мы также убеждены в том, что свобода от коллизий - достаточное свойство для выполнения многих сценариев на практике. Подобно понятию криптостойкости, мы рассматриваем слабую и сильную свободу от коллизий (WCFR и SCFR). Интересно, что такие схемы как Эль-Гамаль[16] и Бойен-Вотерс[11] являются сильно свободными от коллизий, несмотря на то, что они не являются даже слабо криптостойкими. Таким образом, свобода от коллизий – менее строгое утверждение о схеме шифрования и большинство схем шифрования ему удовлетворяют без каких-либо модификаций. Следующая игра определяет два варианта:

  • Установки: Испытатель запускает .
  • Запросы:
    • Запрос публичного ключа . Испытатель допускает и возвращает
    • Запрос ключа расшифрования . Если или возвращает . Иначе и возвращает .
    • Запрос расшифрования . Если , возвращает . Иначе допускает и возвращает .
    • Заключительное сообщение (для WCFR). Если или или или или , возвращает . Иначе допускает если возвращает , иначе возвращает .
    • Заключительное сообщение (для SCFR). Если или или или или , возвращает . Иначе допускает если , возвращает , иначе возвращает .

В случае CPA атак запросы расшифрования не разрешены. Преимущество противника в {WCFR,SCFR}-{CPA,CCA} игре:

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

TemplateLemmaIcon.svg Лемма «Утверждение 51.»
Эль-Гамаль PKE и Бойен-Вотерс IBE схемы являются SCFR-CPA.

Доказательство этого утверждения довольно просто, но опущено из-за экономии места. Далее мы приводим конструкцию для преобразования сильно свободной от коллизий AI-CPA схемы в сильно криптостойкую. Сперва мы используем свободную от коллизий PKE схему шифрования, чтобы зашифровать случайное сообщение . Затем мы хэшируем случайное сообщение, используя защищённую от коллизий сжатия хэш-функцию . Затем мы используем сильный выжиматель (например, универсальную хэш-фукнцию), чтобы выжать оставшуюся случайность из и использовать как ключ для одноразовой симметричной схемы шифрования. Основания идея в том, что, во-первых, свобода от коллизий и защищённость от коллизий хэш-функции , в объединении дают сильную криптостойкость полученной схемы. Если конкретнее, нетрудно оказать, что если существует противник, взламывающий сильную криптостойксть , существует противник, находящий коллизию для : отыскивающий коллизию противник расшифровывает один и тот же шифр-текст, используя секретные ключи, соответствующие двум различным открытым ключам (личностям) и возвращает два открытых текста в качестве коллизии хэш-функции. Свобода от коллизий гарантирует, что два открытых текста с большой вероятностью отличаются. Во-вторых, если выбирается с равномерной случайностью, является IND-CPA безопасной и допускает утечку лишь части бит из , мы можем использовать остаток хэш-леммы[19], чтобы выжать большую часть оставшейся случайности и использовать её как ключ для симметричной схемы шифрования.

Конструкция 52. Пусть – (SCFR-CPA + AI-CPA) общая схема шифрования; – хэш-функция, защищённая от коллизий; – семейство попарно независимых хэш-фукнций, где ; и – одноразовая IND-CPA симметричная схема шифрования. Строим общую схему шифрования .

  • Генерация параметров: По входу возвращает .
  • Генерация ключа: По входу возвращает .
  • Шифрование: По входу генерирует случайное и и возвращает .
  • Расшифрование: По входу , вычисляет . Если , возвращает , иначе .

Следующая теорема объединяет общий результат. Для экономии места мы оставим доказательство для полной версии статьи.

TemplateLemmaIcon.svg Лемма «Теорема 3.»
Пусть – (AI-CPA + SCFR-CPA) безопасная общая схема шифрования, – CRHF, – попарно независимые хэш-функции и – одноразовая IND-CPA симметричная схема шифрования. Тогда схема на основе конструкции 52 – одновременно AI-CPA и SROB-CPA безопасная.

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

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

  1. Computer Science Department, University of Calgary, E-mail: pmohasse@cpsc.ucalgary.ca

Примечания

  1. Отметьте, что понятия KEM/DEM мы рассматриваем только в контексте гибридных схем шифрования, хотя в общем их применение гораздо шире.
  2. При вычислении хэша от , мы можем дополнить достаточным количеством нулей до требуемого хэш-функцией размера блока. Обратите внимание, что это никаким образом не отразится на эффективности шифрования или размере шифр-текста.

Литература

  1. 1,0 1,1 Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984.
  2. 2,0 2,1 Charles Rackoff and Daniel R. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. pages 433–444, 1992.
  3. 3,0 3,1 Danny Dolev, Cynthia Dwork, and Moni Naor. Non-malleable cryptography, 1998. Manuscript.
  4. 4,0 4,1 4,2 4,3 Mihir Bellare, Alexandra Boldyreva, Anand Desai, and David Pointcheval. Keyprivacy in public-key encryption. pages 566–582, 2001.
  5. 5,0 5,1 5,2 5,3 Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier, and Haixia Shi. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. 21(3):350–391, July 2008.
  6. 6,00 6,01 6,02 6,03 6,04 6,05 6,06 6,07 6,08 6,09 6,10 6,11 6,12 Michel Abdalla, Mihir Bellare, and Gregory Neven. Robust encryption. In TCC pages 480–497, 2010.
  7. Mart´ın Abadi and Phillip Rogaway. Reconciling two views of cryptography (the computational soundness of formal encryption). 20(3):395, July 2007.
  8. Anand Desai. The security of all-or-nothing encryption: Protecting against exhaustive key search. pages 359–375, 2000.
  9. 9,0 9,1 9,2 9,3 Marc Fischlin. Pseudorandom function tribe ensembles based on one-way permutations: Improvements and applications. pages 432–445, 1999.
  10. 10,0 10,1 Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. 33(1):167–226, 2003.
  11. 11,0 11,1 11,2 Xavier Boyen and Brent Waters. Anonymous hierarchical identity-based encryption (without random oracles). pages 290–307, 2006.
  12. Michel Abdalla, Mihir Bellare, and Phillip Rogaway. The oracle Diffie-Hellman assumptions and an analysis of DHIES. pages 143–158, 2001.
  13. Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. pages 213–229, 2001.
  14. Jonathan Katz, Amit Sahai, and Brent Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products. pages 146–162, 2008.
  15. Dennis Hofheinz and Enav Weinreb. Searchable encryption with decryption in the standard model. Cryptology ePrint Archive, Report 2008/423, 2008. http://eprint.iacr.org/.
  16. 16,0 16,1 Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. 31:469–472, 1985.
  17. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. pages 62–73, 1993.
  18. Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. pages 92–111, 1994.
  19. Johan H˚astad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. 28(4):1364–1396, 1999.