Вероятностное шифрование — это использование случайности в алгоритме шифрования , так что при шифровании одного и того же сообщения несколько раз, как правило, будут получены разные шифротексты . Термин «вероятностное шифрование» обычно используется в отношении алгоритмов шифрования с открытым ключом ; однако различные алгоритмы шифрования с симметричным ключом достигают аналогичного свойства (например, блочные шифры при использовании в режиме цепочки, таком как CBC ), и потоковые шифры, такие как Freestyle [1], которые по своей сути случайны. Чтобы быть семантически безопасным , то есть скрывать даже частичную информацию об открытом тексте , алгоритм шифрования должен быть вероятностным .
Первая доказуемо безопасная вероятностная схема шифрования с открытым ключом была предложена Шафи Голдвассером и Сильвио Микали , основанная на сложности проблемы квадратичного остатка и имевшая коэффициент расширения сообщения, равный размеру открытого ключа. Более эффективные вероятностные алгоритмы шифрования включают Elgamal , Paillier и различные конструкции в рамках модели случайного оракула , включая OAEP.
Вероятностное шифрование особенно важно при использовании криптографии с открытым ключом . Предположим, что противник наблюдает зашифрованный текст и подозревает, что открытый текст - это либо "ДА", либо "НЕТ", или имеет предчувствие, что открытый текст может быть "АТТАКА В КАЛЕ". При использовании детерминированного алгоритма шифрования противник может просто попытаться зашифровать каждую из своих догадок под открытым ключом получателя и сравнить каждый результат с целевым зашифрованным текстом. Для борьбы с этой атакой схемы шифрования с открытым ключом должны включать элемент случайности, гарантируя, что каждый открытый текст сопоставляется с одним из большого числа возможных зашифрованных текстов.
Интуитивный подход к преобразованию детерминированной схемы шифрования в вероятностную заключается в простом заполнении открытого текста случайной строкой перед шифрованием с помощью детерминированного алгоритма . Наоборот, расшифровка включает применение детерминированного алгоритма и игнорирование случайного заполнения. Однако ранние схемы, применявшие этот наивный подход, были взломаны из-за ограничений в некоторых детерминированных схемах шифрования. Такие методы, как оптимальное асимметричное заполнение шифрования (OAEP), интегрируют случайное заполнение способом, который является безопасным с использованием любой перестановки с лазейкой .
Пример вероятностного шифрования с использованием любой перестановки с секретом:
Это неэффективно, поскольку шифруется только один бит. Другими словами, коэффициент расширения сообщения равен размеру открытого ключа.
Пример вероятностного шифрования в модели случайного оракула:
