Вероятностное шифрование

Вероятностное шифрование — это использование случайности в алгоритме шифрования , поэтому при шифровании одного и того же сообщения несколько раз оно, как правило, дает разные зашифрованные тексты . Термин «вероятностное шифрование» обычно используется в отношении с открытым ключом алгоритмов шифрования ; однако различные алгоритмы шифрования с симметричным ключом достигают аналогичного свойства (например, блочные шифры при использовании в режиме цепочки, например CBC ), а также потоковые шифры, такие как Freestyle. ^[1] которые по своей сути случайны. Чтобы быть семантически безопасным , то есть скрывать даже частичную информацию об открытом тексте , алгоритм шифрования должен быть вероятностным .

История

Первая доказуемо безопасная вероятностная схема шифрования с открытым ключом была предложена Шафи Голдвассером и Сильвио Микали , она основывалась на сложности задачи квадратичной невязки и имела коэффициент расширения сообщения, равный размеру открытого ключа. К более эффективным алгоритмам вероятностного шифрования относятся Elgamal , Paillier и различные конструкции по модели случайного оракула , включая OAEP.

Безопасность

Вероятностное шифрование особенно важно при использовании криптографии с открытым ключом . Предположим, что злоумышленник наблюдает за зашифрованным текстом и подозревает, что открытый текст представляет собой либо «ДА», либо «НЕТ», или догадывается, что открытый текст может быть «АТАКА НА КАЛЕ». Когда используется детерминированный алгоритм шифрования , злоумышленник может просто попытаться зашифровать каждое из своих предположений открытым ключом получателя и сравнить каждый результат с целевым зашифрованным текстом. Чтобы противостоять этой атаке, схемы шифрования с открытым ключом должны включать элемент случайности, гарантирующий, что каждый открытый текст отображается в один из большого количества возможных зашифрованных текстов.

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

Примеры

Пример вероятностного шифрования с использованием любой перестановки лазейки:

x - однобитовый открытый текст
f - перестановка люка (детерминированный алгоритм шифрования)
b - жесткий основной f предикат
r - случайная строка

${\rm {Enc}}(x)=(f(r),x\oplus b(r))$

${\rm {Dec}}(y,z)=b(f^{-1}(y))\oplus z$

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

Пример вероятностного шифрования в модели случайного оракула:

х - открытый текст
f - перестановка люка (детерминированный алгоритм шифрования)
h — случайный оракул (обычно реализуется с использованием публично указанной хэш-функции )
r - случайная строка

${\rm {Enc}}(x)=(f(r),x\oplus h(r))$

${\rm {Dec}}(y,z)=h(f^{-1}(y))\oplus z$

См. также

Ссылки

^ Путупарамбил, Арун Бабу; Томас, Джитин Хосе (01 декабря 2019 г.). «Фристайл, рандомизированная версия ChaCha для защиты от грубой силы и атак по словарю в автономном режиме». Журнал информационной безопасности и приложений . 49 : 102396. arXiv : 1802.03201 . дои : 10.1016/j.jisa.2019.102396 . ISSN 2214-2126 .

Внешние ссылки

Шафи Гольдвассер и Сильвио Микали, Вероятностное шифрование , специальный выпуск журнала компьютерных и системных наук, Vol. 28, № 2, страницы 270–299, апрель 1984 г.
Freestyle — рандомизированная версия ChaCha для защиты от перебора и атак по словарю в автономном режиме [1] .

[1] Путупарамбил, Арун Бабу; Томас, Джитин Хосе (01 декабря 2019 г.). «Фристайл, рандомизированная версия ChaCha для защиты от грубой силы и атак по словарю в автономном режиме». Журнал информационной безопасности и приложений . 49 : 102396. arXiv : 1802.03201 . дои : 10.1016/j.jisa.2019.102396 . ISSN 2214-2126 .

[1]