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

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

История

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

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

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

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

Примеры

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

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

${ Displaystyle { rm {Enc}} (х) = (е (г), х oplus b (r))}$

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

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

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

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

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

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

Смотрите также

внешняя ссылка

Шафи Гольдвассер и Сильвио Микали, Вероятностное шифрование, Специальный выпуск журнала Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.
Freestyle, рандомизированная версия ChaCha для защиты от офлайн-брутфорса и атак по словарю [1].

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

[1]