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

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

История

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

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

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

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

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

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

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

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

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

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

Ссылки

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

[goldwasser-micali_1982-1] Перейти обратно: ^а ^б С. Гольдвассер и С. Микали , Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию , Ежегодный симпозиум ACM по теории вычислений, 1982.

[shannon-2] Шеннон, Клод (1949). «Теория связи секретных систем». Технический журнал Bell System . 28 (4): 656–715. дои : 10.1002/j.1538-7305.1949.tb00928.x . hdl : 10338.dmlcz/119717 .

[Goldreich-3] Гольдрейх, Одед. Основы криптографии: Том 2, Основные приложения. Том. 2. Издательство Кембриджского университета, 2004.

[goldwasser-micali_1984-4] С. Гольдвассер и С. Микали , Вероятностное шифрование . Журнал компьютерных и системных наук, 28:270-299, 1984.

[5] Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Чепмен и Холл/CRC. ISBN 978-1584885511 .

[1]

[2]

[3]

[4]

[5]