Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 7.4
| Трудные предикаты
По определению, односторонняя функция сложна для инвертирования. Иначе говоря: с учетом y = f (x) значение x невозможно вычислить в его полном объеме по любому полиномиально-временному алгоритму (кроме как, при пренебрежи- мо малой вероятности; мы это здесь игнорируем). Может сложиться впечатление, что ничего о x невозможно определить из f (x) в течение полиномиального време- ни. Это не обязательно так. На самом деле для f (x) возможна «утечка» немалого объема информации о x , даже если f является односторонней функцией. Для три- виального примера пусть g - односторонняя функция f (x1, x2) (x1, g(x2)), где |x1| = |x2|. Легко показать, что f является односторонней функцией (это останется в качестве упражнения), даже если она показывает половину своего входа. Для наших приложений нам нужно будет определить конкретную часть инфор- мации о x, которую «скрывает» f (x). Это служит причиной появления понятия трудных предикатов. Трудный предикат hc: {0, 1}* → {0, 1} функции f имеет свойство, которое hc(x) трудно вычислить с вероятностью существенно выше, чем 1/2 с учетом f (x). (Поскольку hc является булевой функцией, всегда возможно вычислить hc(x) с вероятностью 1/2 при случайном прогнозе). Формально: ОПРЕДЕЛЕНИЕ 7.4 Функция hc:{0, 1}*→{0, 1} является трудным пре- дикатом функции f, если hc можно вычислить в течение полиномиального вре- мени, и для любого вероятностного полиномиально-временного алгоритма A существует пренебрежимо малая функция negl , такая что где вероятность берется по равномерному выбору x in {0, 1}n и случайному выбору A. Мы подчеркиваем, что hc(x) является эффективно вычисляемой с учетом x (поскольку функция hc может быть рассчитана в течение полиномиального вре- мени); определение требует, чтобы hc(x) было сложно вычислить с учетом f (x). Приведенное выше определение не требует, чтобы функция f была односторон- ней; если f - перестановка, то она, однако, не может быть трудным предикатом, если она не является односторонней (см. упражнение 7.13). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|