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