В криптографии семантически безопасная криптосистема — это система, в которой из зашифрованного текста может быть извлечена лишь незначительная информация об открытом тексте . В частности, любой вероятностный алгоритм с полиномиальным временем (PPTA), которому дан зашифрованный текст определенного сообщения (взятый из любого распределения сообщений) и длина сообщения, не может определить какую-либо частичную информацию о сообщении с вероятностью, не пренебрежимо большей, чем все другие PPTA, которые имеют доступ только к длине сообщения (а не к зашифрованному тексту). [1] Эта концепция является аналогом вычислительной сложности концепции совершенной секретности Шеннона . Совершенная секретность означает, что зашифрованный текст не раскрывает никакой информации об открытом тексте, тогда как семантическая безопасность подразумевает, что любая раскрытая информация не может быть извлечена. [2] [3] : 378–381
Понятие семантической безопасности впервые было выдвинуто Голдвассером и Микали в 1982 году. [1] [4] Однако первоначально предложенное ими определение не предлагало прямых средств для доказательства безопасности практических криптосистем. Впоследствии Голдвассер/Микали продемонстрировали, что семантическая безопасность эквивалентна другому определению безопасности, называемому неразличимостью шифротекста при атаке с выбранным открытым текстом. [5] Последнее определение более распространено, чем первоначальное определение семантической безопасности, поскольку оно лучше облегчает доказательство безопасности практических криптосистем.
В случае криптосистем с симметричным ключом , противник не должен иметь возможности вычислить какую-либо информацию об открытом тексте из его шифротекста. Это можно представить так, как если бы противник имел два открытых текста одинаковой длины и два соответствующих им шифротекста, он не мог бы определить, какой шифротекст принадлежит какому открытому тексту.
Для того чтобы криптосистема с асимметричным ключом была семантически безопасной, для вычислительно ограниченного противника должно быть невыполнимо извлечь существенную информацию о сообщении (открытом тексте), когда заданы только его шифртекст и соответствующий открытый ключ шифрования. Семантическая безопасность рассматривает только случай «пассивного» злоумышленника, т. е. того, кто генерирует и наблюдает зашифрованные тексты, используя открытый ключ и открытые тексты по своему выбору. В отличие от других определений безопасности, семантическая безопасность не рассматривает случай атаки выбранного шифртекста (CCA), когда злоумышленник может запросить расшифровку выбранных шифртекстов, и многие семантически безопасные схемы шифрования явно небезопасны против атаки выбранного шифртекста. Следовательно, семантическая безопасность теперь считается недостаточным условием для защиты схемы шифрования общего назначения.
Неразличимость при атаке с выбранным открытым текстом ( IND-CPA ) обычно определяется следующим экспериментом: [6]
Базовая криптосистема является IND-CPA (и, таким образом, семантически безопасна при атаке с выбранным открытым текстом), если противник не может определить, какое из двух сообщений было выбрано оракулом, с вероятностью, значительно большей, чем (успех случайного угадывания). Варианты этого определения определяют неразличимость при атаке с выбранным шифртекстом и адаптивной атаке с выбранным шифртекстом ( IND-CCA , IND-CCA2 ).
Поскольку в вышеприведенной игре противник обладает открытым ключом шифрования, семантически безопасная схема шифрования по определению должна быть вероятностной , обладающей компонентом случайности ; если бы это было не так, противник мог бы просто вычислить детерминированное шифрование и и сравнить эти шифрованные данные с возвращенным зашифрованным текстом, чтобы успешно угадать выбор оракула.
Семантически безопасные алгоритмы шифрования включают Goldwasser-Micali , ElGamal и Paillier . Эти схемы считаются доказуемо безопасными , поскольку их семантическая безопасность может быть сведена к решению некоторой сложной математической задачи (например, Decisional Diffie-Hellman или Quadratic Residuosity Problem ). Другие, семантически небезопасные алгоритмы, такие как RSA , могут быть сделаны семантически безопасными (при более сильных предположениях) с помощью использования случайных схем шифрования с заполнением, таких как Optimal Asymmetric Encryption Padding (OAEP).
