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