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

редактировать

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

Содержание

1 История
2 Криптография с симметричным ключом
3 Открыто -ключевое шифрование
4 Ссылки

История

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

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

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

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

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

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

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

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

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

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

Ссылки

^ С. Гольдвассер и С. Микали, Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию, Ежегодный симпозиум 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. Cambridge University Press, 2004.
^С. Гольдвассер и С. Микали, Вероятностное шифрование. Journal of Computer and System Sciences, 28: 270-299, 1984.
^Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы. Чепмен и Холл / CRC. ISBN 978-1584885511.