Введение в современную криптографию


Неразличимость в присутствии подслушивающей стороны



Pdf көрінісі
бет43/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   39   40   41   42   43   44   45   46   ...   249
Криптография Катц

Неразличимость в присутствии подслушивающей стороны. Теперь мы да-
дим формальное определение, начав с описанного выше эксперимента. Экспери-
мент определен для любой системы шифрования с закрытым ключом Π = (Gen, 
Enc, Dec), любого противника A и любого значения параметра безопасности n:
Эксперимент по неразличимости для противника 
(n):
1. Противнику A даны вводные данные 1n, и он выводит пару сообщений m0, 
m1 при |m0| = |m1|.
2. С помощью алгоритма Gen(1n) генерируется ключ k и выбирается единоо-
бразный бит b ∈ {0, 1}. Вычисляется шифртекст c ← Enck (mb ), который пере-
дается A. Мы рассматриваем c в качестве анализируемого шифртекста.
3. A выводит бит br.
4. Результатом эксперимента является 1, если br = b, иначе 0. Если PrivKeav (n) 
= 1, мы говорим, что A добился успеха. 
Ограничения по длине m0 и m1 отсутствуют, поскольку они равны. (Разумеется, если 
A работает в полиномиальном времени, тогда m0 и m1 имеют полиномиальную длину 
по n.) Если Π является системой фиксированной длины для сообщений длиной A(n), 
тогда в вышеупомянутый эксперимент добавляется требование m0, m1 ∈ {0, 1}A(n).
Подразумевается, что противник может только перехватывать шифртекст, по-
скольку его вводные данные ограничены (единственным) шифртекстом, и про-
тивник не может в дальнейшем взаимодействовать с отправителем или получа-
телем. (Как мы увидим дальше, возможность дополнительного взаимодействия 
делает противника значительно сильнее.)
В соответствии с определением неразличимости, система шифрования является 
криптографически надежной, если ни один ppt противник A не может успешно уга-
дать, какое сообщение зашифровано в вышеупомянутом эксперименте с вероятно-
стью значительно превышающей случайную догадку, верную с вероятностью 1/2:
ОПРЕДЕЛЕНИЕ 3.8  Система шифрования с закрытым ключом Π = (Gen, Enc, 
Dec) обладает неразличимым шифрованием при наличии подслушивающей сторо-
ны, или является криптографически надежной с точки зрения EAV (расширенной 
проверки приложения), если для всех вероятностных полиномиально-временных про-
тивников A существует такая пренебрежимо малая функция negl, что для всех n,
(n) = 1]. ≤ 1/2 + negl(n), 
где вероятность вычисляется по случайности, используемой A, и случайности, 
используемой в эксперименте (для выбора ключа и бита b, а также любая слу-
чайность, используемая алгоритмом Enc).


65
Примечание: если не указано иное, когда мы пишем “f (n) ≤ g(n)”, это означа-
ет, что неравенство верно для всех n.
Должно быть очевидно, что определение 3.8 слабее определения 2.5, которое рав-
носильно совершенной стойкости. Таким образом, любая совершенно криптостой-
кая системы шифрования обладает неразличимым шифрованием при наличии под-
слушивающей стороны. Отсюда следует, что наша цель - показать, что существуют 
системы шифрования, соответствующие вышесказанному, в которых используется 
ключ короче сообщения. Иными словами, мы покажем системы, которые соответ-
ствуют определению 3.8, но не могут соответствовать определению 2.5.


Достарыңызбен бөлісу:
1   ...   39   40   41   42   43   44   45   46   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет