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

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

История [ править ]

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

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

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

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

Этот раздел требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. ( Сентябрь 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Случайная пара генерируется при запуске . ${\ displaystyle (pk, sk)}$ ${\ displaystyle Gen (1 ^ {n})}$
Вероятностному полиномиальному ограниченному по времени противнику дается открытый ключ , который он может использовать для генерации любого количества зашифрованных текстов (в пределах полиномиальных границ). ${\ displaystyle pk}$
Злоумышленник генерирует два сообщения одинаковой длины и передает их оракулу вызова вместе с открытым ключом. ${\ displaystyle m_ {0}}$ ${\ displaystyle m_ {1}}$
Оракул вызова выбирает одно из сообщений, подбрасывая монетку (выбирая случайный бит ), шифрует сообщение открытым ключом и возвращает полученный сложный зашифрованный текст противнику. ${\ 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 , El Gamal и Paillier . Эти схемы считаются доказуемо безопасными , поскольку их семантическая безопасность может быть сведена к решению некоторой сложной математической задачи (например, решающей проблемы Диффи-Хеллмана или проблемы квадратичной остаточности ). Другие, семантически небезопасные алгоритмы, такие как RSA , можно сделать семантически безопасными (при более строгих предположениях) за счет использования случайных схем заполнения шифрования, таких как оптимальное асимметричное заполнение шифрования (OAEP).

Ссылки [ править ]

^ a b С. Голдвассер и С. Микали , Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию , Ежегодный симпозиум ACM по теории вычислений, 1982.
^ Шеннон, Клод (1949). «Коммуникационная теория секретных систем». Технический журнал Bell System . 28 (4): 656–715. DOI : 10.1002 / j.1538-7305.1949.tb00928.x . hdl : 10338.dmlcz / 119717 .
^ Голдрайх, Одед. Основы криптографии: Том 2, Основные приложения. Vol. 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. DOI : 10.1002 / j.1538-7305.1949.tb00928.x . hdl : 10338.dmlcz / 119717 .

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

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

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

[1]