Семантическая безопасность - Semantic security

В криптография, а семантически безопасный криптосистема это тот, где только незначительная информация о простой текст могут быть извлечены из зашифрованный текст. В частности, любой вероятностный алгоритм с полиномиальным временем (PPTA), которому передается зашифрованный текст определенного сообщения ${\displaystyle m}$ (взято из любого распределения сообщений) и длина сообщения не могут определить какую-либо частичную информацию о сообщении с вероятностью немаловажно выше, чем у всех других PPTA, которые имеют доступ только к длине сообщения (но не к зашифрованному тексту).^[1] Эта концепция является аналогом вычислительной сложности Шеннона идея совершенная секретность. Полная секретность означает, что зашифрованный текст не раскрывает никакой информации об открытом тексте, в то время как семантическая безопасность подразумевает, что любую раскрытую информацию невозможно извлечь.^{[2][3]:378–381}

История

Понятие семантической безопасности было впервые предложено Гольдвассер и Микали в 1982 г.^[1] Однако первоначально предложенное определение не предлагало прямых средств доказательства безопасности практических криптосистем. Впоследствии Голдвассер / Микали продемонстрировали, что семантическая безопасность эквивалентна другому определению безопасности, называемому неразличимость зашифрованного текста при атаке с выбранным открытым текстом.^[4] Это последнее определение более распространено, чем исходное определение семантической безопасности, поскольку оно лучше облегчает доказательство безопасности практических криптосистем.

Криптография с симметричным ключом

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

Криптография с открытым ключом

Для алгоритм шифрования с асимметричным ключом криптосистема, чтобы быть семантически безопасной, она должна быть недопустимой для вычислительно ограниченный злоумышленник, чтобы получить важную информацию о сообщении (открытый текст), когда ему предоставляется только его зашифрованный текст и соответствующий открытый ключ шифрования. Семантическая безопасность рассматривает только случай «пассивного» злоумышленника, то есть того, кто генерирует и наблюдает за шифротекстами, используя открытый ключ и открытые тексты по своему выбору. В отличие от других определений безопасности, семантическая безопасность не рассматривает случай атака по выбранному зашифрованному тексту (CCA), где злоумышленник может запросить расшифровку выбранных зашифрованных текстов, а многие семантически безопасные схемы шифрования явно небезопасны против атаки на выбранный зашифрованный текст. Следовательно, семантическая безопасность теперь считается недостаточным условием для защиты схемы шифрования общего назначения.

Неразличимость при Выбранная атака с открытым текстом (IND-CPA ) обычно определяется следующим экспериментом:^[5]

1. Случайная пара ${\displaystyle (pk,sk)}$ генерируется запуском ${\displaystyle Gen(1^{n})}$.
2. Вероятностному полиномиальному ограниченному во времени противнику дается открытый ключ ${\displaystyle pk}$ , который он может использовать для генерации любого количества зашифрованных текстов (в пределах полинома).
3. Противник генерирует два сообщения одинаковой длины. ${\displaystyle m_{0}}$ и ${\displaystyle m_{1}}$, и передает их оракулу вызова вместе с открытым ключом.
4. Оракул вызова выбирает одно из сообщений, подбрасывая честную монету (выбирая случайный бит ${\displaystyle b\in \{0,1\}}$), шифрует сообщение ${\displaystyle m_{b}}$ под открытым ключом и возвращает полученный сложный зашифрованный текст ${\displaystyle c}$ противнику.

Лежащий в основе криптосистема является IND-CPA (и, таким образом, семантически безопасен при атаке с выбранным открытым текстом), если злоумышленник не может определить, какое из двух сообщений было выбрано оракулом, с вероятностью значительно большей, чем ${\displaystyle 1/2}$ (степень успеха случайного угадывания). Варианты этого определения определяют неразличимость при атака по выбранному зашифрованному тексту и адаптивная атака по выбранному зашифрованному тексту (IND-CCA, IND-CCA2 ).

Поскольку злоумышленник обладает открытым ключом шифрования в приведенной выше игре, семантически безопасная схема шифрования должна по определению быть вероятностный, обладающий компонентом случайность; если бы это было не так, противник мог бы просто вычислить детерминированное шифрование ${\displaystyle m_{0}}$ и ${\displaystyle m_{1}}$ и сравните эти шифрования с возвращенным зашифрованным текстом ${\displaystyle c}$ чтобы успешно угадать выбор оракула.

Семантически безопасные алгоритмы шифрования включают Гольдвассер-Микали, Эль-Гамаль и Paillier. Эти схемы считаются доказуемо безопасный, поскольку их семантическая безопасность может быть сведена к решению некоторой сложной математической задачи (например, Решительный Диффи-Хеллман или Квадратичная проблема остаточности ). Другие, семантически небезопасные алгоритмы, такие как ЮАР, можно сделать семантически безопасным (при более строгих предположениях) за счет использования схем случайного шифрования, таких как Оптимальное заполнение асимметричным шифрованием (OAEP).

Рекомендации

1. С. Гольдвассер и С. Микали, Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию, Ежегодный симпозиум ACM по теории вычислений, 1982.
2. Шеннон, Клод (1949). «Коммуникационная теория секретных систем». Технический журнал Bell System. 28 (4): 656–715. Дои:10.1002 / j.1538-7305.1949.tb00928.x. HDL:10338.dmlcz / 119717.
3. Гольдрайх, Одед. Основы криптографии: Том 2, Основные приложения. Vol. 2. Издательство Кембриджского университета, 2004 г.
4. С. Гольдвассер и С. Микали, Вероятностное шифрование. Журнал компьютерных и системных наук, 28: 270-299, 1984.
5. Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы. Чепмен и Холл / CRC. ISBN  978-1584885511.