Введение в современную криптографию
Неразличимость в присутствии подслушивающей стороны
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 3.8
| Неразличимость в присутствии подслушивающей стороны. Теперь мы да-
дим формальное определение, начав с описанного выше эксперимента. Экспери- мент определен для любой системы шифрования с закрытым ключом Π = (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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|