Неразличимость зашифрованного текста

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Неразличимость зашифрованного текста» - новости · газеты · книги · ученый · JSTOR ( сентябрь 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

Криптосистема считается безопасным с точки зрения неразличимости , если не противник, учитывая шифрование сообщени случайным образом выбранного из пространства сообщений два элемента , определенного противником, не может определить выбор сообщение с вероятностью значительно лучше , чем у случайного угадывания ( ¹ ⁄ ₂ ). Если какой - либо злоумышленник может добиться успеха в различении выбранного шифротекста с вероятностью значительно больше , чем ¹ / ₂ , то этот противник считается иметь «преимущество» в различении шифротекста, а схема несчитается безопасным с точки зрения неразличимости. Это определение включает в себя представление о том, что в безопасной схеме злоумышленник не должен узнавать никакой информации, видя зашифрованный текст. Следовательно, противник должен иметь возможность действовать не лучше, чем если бы он угадал случайным образом.

Формальные определения [ править ]

Безопасность с точки зрения неразличимости имеет множество определений в зависимости от предположений о возможностях злоумышленника. Обычно ее представляют как игру , в которой криптосистема считается безопасной, если ни один противник не может выиграть игру со значительно большей вероятностью, чем противник, который должен угадать случайным образом. Наиболее распространенными определениями, используемыми в криптографии, являются неразличимость при атаке по выбранному открытому тексту (сокращенно IND-CPA), неразличимость при (неадаптивной) атаке по выбранному зашифрованному тексту (IND-CCA1) и неразличимость при атаке с использованием адаптивного выбранного шифротекста.(IND-CCA2). Безопасность в соответствии с любым из последних определений подразумевает безопасность в соответствии с предыдущими: схема, которая является безопасным IND-CCA1, также безопасна IND-CPA, а схема, которая является безопасной IND-CCA2, является безопасной как IND-CCA1, так и IND-CPA. Таким образом, IND-CCA2 - самое сильное из трех определений безопасности.

Неразличимость при атаке по выбранному открытому тексту (IND-CPA) [ редактировать ]

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

Претендент генерирует пару ключей PK , SK на основе некоторого параметра безопасности k (например, размера ключа в битах) и публикует PK противнику. Претендент сохраняет SK .
Злоумышленник может выполнять полиномиально ограниченное количество шифрований или других операций.
В конце концов, противник отправляет претенденту два выбранных открытых текста . ${\ displaystyle \ scriptstyle M_ {0}, M_ {1}}$
Претендент выбирает бит Ь {0, 1} равномерно случайным образом , и посылает вызов шифротекст C = E (PK, ) спиной к противнику. ${\ Displaystyle \ scriptstyle \ in}$ ${\ displaystyle \ scriptstyle M_ {b}}$
Злоумышленник может выполнить любое количество дополнительных вычислений или шифрования. Наконец, он выводит предположение для значения b .

Криптосистема неотличима при выбранной атаке открытого текста, если каждый вероятностный злоумышленник с полиномиальным временем имеет лишь незначительное « преимущество » над случайным угадыванием. Считается, что противник имеет незначительное «преимущество», если он выигрывает указанную выше игру с вероятностью , где - незначительная функция в параметре безопасности k , то есть для каждой (ненулевой) полиномиальной функции существует такая, что для всех . ${\ Displaystyle \ scriptstyle \ left ({\ frac {1} {2}} \ right) \, + \, \ epsilon (k)}$ ${\ displaystyle \ scriptstyle \ epsilon (k)}$ ${\ displaystyle \ scriptstyle poly ()}$ ${\ displaystyle \ scriptstyle k_ {0}}$ ${\ displaystyle \ scriptstyle | \ epsilon (k) | \; <\; \ left | {\ frac {1} {poly (k)}} \ right |}$ ${\ Displaystyle \ scriptstyle к \;> \; k_ {0}}$

Несмотря на то, что противник знает , и PK, вероятностный характер Е означает , что шифрование будет только один из многих действительных шифртекстов, и , следовательно , шифрование , и сравнения полученных шифртекстов с провокационным шифртекстом не дает какое-либо не ничтожное преимущества в противник. ${\ displaystyle \ scriptstyle M_ {0}}$ ${\ displaystyle \ scriptstyle M_ {1}}$ ${\ displaystyle \ scriptstyle M_ {b}}$ ${\ displaystyle \ scriptstyle M_ {0}}$ ${\ displaystyle \ scriptstyle M_ {1}}$

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

Симметричная игра IND-CPA, формализованная [ править ]

Состязательный процесс выполнения атаки с использованием выбранного открытого текста обычно описывается в форме криптографической игры . Для проверки симметричного IND-CPA определена описанная выше игра. ^[1] Позвольте быть функцией генерации ключа, быть функцией шифрования и быть функцией дешифрования. Позвольте быть симметричной схемой шифрования. Игра определяется как: ${\ Displaystyle {\ mathcal {K}}}$ ${\ displaystyle {\ mathcal {E}}}$ ${\ Displaystyle {\ mathcal {D}}}$ ${\ displaystyle {\ mathcal {S}} {\ mathcal {E}} = ({\ mathcal {K}}, {\ mathcal {E}}, {\ mathcal {D}})}$ ${\ displaystyle Guess}$

Сколько раз злоумышленник выбирает два незашифрованных сообщения по своему выбору и передает их LR- оракулу, который возвращает зашифрованный текст, зашифровывающий одно из сообщений. Преимущество противника определяется его вероятностью угадать значение b, значение, выбранное случайным образом в начале игры, которое определяет сообщение, зашифрованное в LR- оракуле. Таким образом, его преимущество определяется как: ^[1]

Неразличимость при атаке по выбранному зашифрованному тексту / адаптивной атаке по выбранному зашифрованному тексту (IND-CCA1, IND-CCA2) [ редактировать ]

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

Претендент генерирует пару ключей PK , SK на основе некоторого параметра безопасности k (например, размера ключа в битах) и публикует PK противнику. Претендент сохраняет SK .
Злоумышленник может выполнить любое количество шифрований, вызовов оракула дешифрования на основе произвольных зашифрованных текстов или других операций.
В конце концов, противник отправляет претенденту два выбранных открытых текста . ${\ Displaystyle \ scriptstyle M_ {0}, \, M_ {1}}$
Претендент выбирает бит b ∈ {0, 1} равномерно и случайным образом и отправляет "контрольный" зашифрованный текст C = E (PK, ) обратно противнику. ${\ displaystyle \ scriptstyle M_ {b}}$
Злоумышленник может выполнить любое количество дополнительных вычислений или шифрования.
1. В неадаптивном случае (IND-CCA1) злоумышленник может больше не обращаться к оракулу дешифрования.
2. В адаптивном случае (IND-CCA2) злоумышленник может делать дальнейшие вызовы оракулу дешифрования, но не может отправлять шифрованный текст C вызова .
Наконец, злоумышленник выдает предположение для значения b .

Схема является IND-CCA1 / IND-CCA2 безопасной, если ни один противник не имеет существенного преимущества в выигрыше в указанной выше игре.

Невозможно отличить от случайного шума [ править ]

Иногда нам нужны схемы шифрования, в которых строка зашифрованного текста неотличима от случайной строки злоумышленником. ^[2]

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

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

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

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

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

Эквивалентность и последствия [ править ]

Неразличимость - важное свойство для сохранения конфиденциальности зашифрованных сообщений. Однако в некоторых случаях было обнаружено, что свойство неразличимости подразумевает другие, очевидно не связанные свойства безопасности. Иногда эти выводы идут в обоих направлениях, делая два определения эквивалентными; например, известно, что свойство неразличимости при адаптивной атаке по выбранному зашифрованному тексту (IND-CCA2) эквивалентно свойству неподатливостипри том же сценарии атаки (NM-CCA2). Эта эквивалентность не очевидна сразу, поскольку неизменяемость - это свойство, имеющее отношение к целостности сообщения, а не к конфиденциальности. В других случаях было продемонстрировано, что неотличимость может быть объединена с некоторыми другими определениями, чтобы подразумевать еще другие полезные определения, и наоборот. Следующий список суммирует несколько известных последствий, но отнюдь не является полным.

Обозначение означает, что свойство A подразумевает свойство B. означает, что свойства A и B эквивалентны . означает, что свойство A не обязательно подразумевает свойство B. $\scriptstyle A\;\Rightarrow \;B$ $\scriptstyle A\;\Leftrightarrow \;B$ $\scriptstyle A\;\not \Rightarrow \;B$

Семантическая безопасность IND-CPA под CPA. $\scriptstyle \Leftrightarrow$
NM-CPA ( неподатливость при атаке с выбранным открытым текстом) IND-CPA. $\scriptstyle \Rightarrow$
NM-CPA ( неподатливость при атаке с выбранным открытым текстом) IND-CCA2. $\scriptstyle \not \Rightarrow$
НМ-CCA2 ( не-податливость при адаптивном выбранном шифротексте) ИНД-CCA2. $\scriptstyle \Leftrightarrow$

См. Также [ править ]

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

Ссылки [ править ]

^ a b Белларе, Михир; Рогавей, Филипп (11 мая 2005 г.). «Введение в современную криптографию, Глава 5: Симметричное шифрование» (PDF) . п. 93 . Проверено 6 апреля 2020 .
^ Чакраборти, Дебруп; Родригес-Энрикес., Франсиско (2008). Четин Кая Коч (ред.). Криптографическая инженерия . п. 340. ISBN 9780387718170.
^ iang (2006-05-20). «Не отличить от случайного» . Проверено 6 августа 2014 . CS1 maint: discouraged parameter (link)
^ Бернштейн, Дэниел Дж .; Гамбург, Майк; Краснова, Анна; Ланге, Таня (28 августа 2013 г.). «Эллигатор: точки эллиптической кривой, неотличимые от однородных случайных строк» (PDF) . Проверено 23 января 2015 . CS1 maint: discouraged parameter (link)
Перейти ↑ Möller, Bodo (2004). «Схема шифрования с открытым ключом с псевдослучайными зашифрованными текстами». Компьютерная безопасность - ESORICS 2004 . Конспект лекций по информатике. 3193 . С. 335–351. DOI : 10.1007 / 978-3-540-30108-0_21 . ISBN 978-3-540-22987-2.
^ Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений . ISBN 9780191620805.
^ Rogaway, Филипп (2004-02-01). «Симметричное шифрование на основе nonce» (PDF) . С. 5–6 . Проверено 7 августа 2014 . CS1 maint: discouraged parameter (link)

Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Чепмен и Холл / CRC Press . ISBN 978-1584885511.

[:0-1] Белларе, Михир; Рогавей, Филипп (11 мая 2005 г.). «Введение в современную криптографию, Глава 5: Симметричное шифрование» (PDF) . п. 93 . Проверено 6 апреля 2020 .

[2] Чакраборти, Дебруп; Родригес-Энрикес., Франсиско (2008). Четин Кая Коч (ред.). Криптографическая инженерия . п. 340. ISBN 9780387718170.

[3] (2006-05-20). «Не отличить от случайного» . Проверено 6 августа 2014 . CS1 maint: discouraged parameter (link)

[4] Бернштейн, Дэниел Дж .; Гамбург, Майк; Краснова, Анна; Ланге, Таня (28 августа 2013 г.). «Эллигатор: точки эллиптической кривой, неотличимые от однородных случайных строк» (PDF) . Проверено 23 января 2015 . CS1 maint: discouraged parameter (link)

[5] Перейти ↑ Möller, Bodo (2004). «Схема шифрования с открытым ключом с псевдослучайными зашифрованными текстами». Компьютерная безопасность - ESORICS 2004 . Конспект лекций по информатике. 3193 . С. 335–351. DOI : 10.1007 / 978-3-540-30108-0_21 . ISBN 978-3-540-22987-2.

[6] Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений . ISBN 9780191620805.

[7] Rogaway, Филипп (2004-02-01). «Симметричное шифрование на основе nonce» (PDF) . С. 5–6 . Проверено 7 августа 2014 . CS1 maint: discouraged parameter (link)