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

В криптографии , семантический безопасные криптосистемы являются один , где только ничтожна информация об открытом тексте может быть посильнее извлечена из шифротекста . В частности, любой вероятностный алгоритм с полиномиальным временем (PPTA), которому задан зашифрованный текст определенного сообщения (взятый из любого распределения сообщений) и длина сообщения, не может определить какую-либо частичную информацию о сообщении с вероятностью, не пренебрежимо превышающей все остальные PPTA, которые имеют доступ только к длине сообщения (но не к зашифрованному тексту). Эта концепция является аналогом вычислительной сложности концепции полной секретности Шеннона . Полная секретность означает, что зашифрованный текст не раскрывает никакой информации об открытом тексте, в то время как семантическая безопасность подразумевает, что любую раскрытую информацию невозможно извлечь. ${\ displaystyle m}$

История

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

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

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

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

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

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

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

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

Семантически безопасные алгоритмы шифрования включают Goldwasser-Micali , ElGamal и Paillier . Эти схемы считаются доказуемо безопасными , поскольку их семантическая безопасность может быть сведена к решению некоторой сложной математической задачи (например, решающей проблемы Диффи-Хеллмана или проблемы квадратичной остаточности ). Другие, семантически небезопасные алгоритмы, такие как RSA , можно сделать семантически безопасными (при более строгих предположениях) с помощью схем заполнения случайным шифрованием, таких как оптимальное асимметричное заполнение шифрования (OAEP).

использованная литература