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


Семантическая криптостойкость



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

Семантическая криптостойкость. Полное определение семантической 
криптостойкости гарантирует значительно больше, чем свойства в Теореме 3.11. 
Определение допускает, что длина открытого текста зависит от параметра без-
опасности, а также допускает весьма произвольное распределение по открытым 
текстам. (Фактически, мы допускаем только эффективно отбираемые распреде-
ления. Это значит, что существует некоторый вероятностно полиномиально-вре-
менной алгоритм Samp, такой что Samp(1n) выводит сообщения в соответствии с 
распределением.) Определение также учитывает «внешнюю» информацию h(m) 
об открытом тексте, которая может просочиться к противнику другими способа-
ми (например, одно и то же сообщение m используется также для других целей).
ОПРЕДЕЛЕНИЕ 3.12 Система шифрования с закрытым ключом (Enc, 
Dec) является семантически надежной при наличии подслушивающей сторо-
ны, если для каждого ppt алгоритма A существует такой ppt алгоритм Ar, что 
для любого ppt алгоритма Samp и вычислимых полиномиально-временных функ-
ций f и h следующее является пренебрежимо малым:
где первая вероятность вычисляется по равномерному k  {0, 1}n, m, выведен-
ному алгоритмом Samp(1n), произвольному A и произвольному Enc, а вторая 
вероятность вычисляется по m, выведенному Samp(1n), и произвольному Ar . 
Противнику A дан шифртекст Enck (m), а также внешняя информация h(m). 
Он пытается угадать значение f (m). Алгоритм Ar также пытается угадать 
значение f (m), но ему заданы только функция h(m) и длина сообщения m. В 
соответствии с требованиями надежности вероятность того, что A правильно 


70
угадает f (m), должна быть примерно равна вероятности правильной догадки, 
сделанной Ar. Тогда, интуитивно, шифртекст Enck(m) не раскрывает никакой 
дополнительной информации о значении f (m). 
Определение 3.12 основывается на очень сильной и убедительной формули-
ровке гарантий безопасности, которые должна обеспечивать система шифрова-
ния. Однако работать с определением неразличимости (определение 3.8) про-
ще. К счастью, определения являются равносильными:
ТЕОРЕМА 3.13  Система шифрования с закрытым ключом обладает нераз-
личимостью при наличии подслушивающей стороны тогда и только тогда, когда 
она является семантически надежной при наличии подслушивающей стороны.
Забегая вперед, скажем, что подобная равносильность между семантической 
безопасностью и неразличимостью известна для всех определений, представ-
ленных как в данной главе, так и в главе 11. Вследствие этого, мы можем ис-
пользовать определение неразличимости в качестве рабочего, пока мы уверены 
в том, что достигнутые гарантии соответствуют семантической надежности.


Достарыңызбен бөлісу:
1   ...   43   44   45   46   47   48   49   50   ...   249




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

    Басты бет