Жесткий предикат

В криптографии жесткий предикат односторонней функции f — это предикат b (т. е. функция, вывод которой представляет собой один бит), который легко вычислить (как функцию от x ), но трудно вычислить при заданном f. (х) . Формально, не существует вероятностного полиномиального алгоритма (PPT) , который вычисляет b(x) из f(x) с вероятностью, значительно большей половины по сравнению со случайным выбором x . ^{[ 1 ]}^: 34 Другими словами, если x нарисован равномерно случайным образом, то при наличии f(x) любой противник PPT может отличить только жесткий бит b(x) и равномерно случайный бит с незначительным преимуществом по длине x . ^{[ 2 ]}

. аппаратную функцию Аналогично можно определить То есть, если x выбран равномерно случайным образом, то при заданном f(x) любой алгоритм PPT может различать только значение аппаратной функции h(x) и равномерно случайные биты длины |h(x)| с незначительным преимуществом по длине x . ^{[ 3 ]}^{[ 4 ]}

Жесткий предикат отражает «в концентрированном смысле» сложность инвертирования f .

Хотя одностороннюю функцию трудно инвертировать, нет никаких гарантий относительно возможности вычисления частичной информации о прообразе c из изображения f(x) . Например, хотя предполагается, что RSA является односторонней функцией, символ Якоби прообраза можно легко вычислить по символу изображения. ^{[ 1 ]}^: 121

Понятно, что если у взаимно однозначной функции есть жесткий предикат, то она должна быть односторонней. Одед Голдрейх и Леонид Левин (1989) показали, как любую одностороннюю функцию можно тривиально модифицировать, чтобы получить одностороннюю функцию, имеющую определенный предикат. ^{[ 5 ]} Пусть f — односторонняя функция. Определим g(x,r) = (f(x), r) , где длина r такая же, как длина x . Пусть x _j обозначает j ^й бит x и r _j j ^й немного р . Затем

$b(x,r):=\langle x,r\rangle =\bigoplus _{j}x_{j}r_{j}$

является жестким предикатом g . Обратите внимание, что b(x, r) = < x, r > где <·, ·> обозначает стандартное скалярное произведение в векторном пространстве ( Z ₂ ) ^н. Этот предикат является жестким из-за вычислительных проблем; то есть вычислить это несложно, поскольку g(x, r) теоретически несет информацию с потерями. Скорее, если существует алгоритм, который эффективно вычисляет этот предикат, то есть и другой алгоритм, который может эффективно инвертировать f .

Подобная конструкция дает аппаратную функцию с выходными битами O(log |x|) . Предположим, f — сильная односторонняя функция. Определим g(x, r) = (f(x), r), где | р | = 2| х |. Выберите функцию длины l(n) = O(log n) st l(n) ≤ n . Позволять

$b_{i}(x,r)=\bigoplus _{j}x_{j}r_{i+j}.$

Тогда h(x, r) := b ₁ (x, r) b ₂ (x, r) ... b _l(|x|) (x, r) является аппаратной функцией с выходной длиной l(| х|) . ^{[ 6 ]}

Иногда бывает так, что фактический бит входных данных x является аппаратным. Например, каждый бит входных данных функции RSA является жестким предикатом RSA, а блоки из O(log |x|) битов x неотличимы от случайных битовых строк за полиномиальное время (в предположении, что функция RSA трудно перевернуть). ^{[ 7 ]}

Жесткие предикаты дают возможность построить генератор псевдослучайных чисел из любой односторонней перестановки . Если b — жесткий предикат односторонней перестановки f , а s — случайное начальное число, то

$\{b(f^{n}(s))\}_{n}$

— псевдослучайная битовая последовательность, где f ^н означает n-ю итерацию применения f к s , а b — это аппаратный бит, сгенерированный каждым раундом n . ^{[ 1 ]}^: 132

Жесткие предикаты односторонних перестановок с лазейками (известные как предикаты лазеек ) могут использоваться для создания семантически безопасных схем шифрования с открытым ключом. ^{[ 1 ]}^: 129

См. также

Декодирование списка (описывает декодирование списка; ядро конструкции Гольдрейха-Левина жестких предикатов из односторонних функций можно рассматривать как алгоритм декодирования списка кода Адамара ).

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Гольдвассер С. и Белларе М. «Конспекты лекций по криптографии». Архивировано 21 апреля 2012 г. в Wayback Machine . Летний курс по криптографии, Массачусетский технологический институт, 1996–2001 гг.
^ Определение 2.4 в Линделл, Иегуда. «Основы криптографии 89-856» (PDF) . Компьютерные науки, Университет Бар-Илан . Университет Бар-Илан. Архивировано из оригинала (PDF) 19 января 2022 года . Проверено 11 января 2016 г.
^ FoC Гольдрейха, том 1, защита 2.5.5.
^ Определение 3 в Холенштейн, Томас; и др. «Полная классификация билинейных аппаратных функций» (PDF) . Электронная версия IACR . МАКР . Проверено 11 января 2016 г.
^ О. Гольдрейх и Л. А. Левин, Жесткий предикат для всех односторонних функций , STOC 1989, стр. 25–32.
^ FoC Гольдрейха, том 1, Теорема 2.5.6.
^ Дж. Хостад , М. Наслунд, Безопасность всех битов RSA и дискретного журнала (2004) : Журнал ACM, 2004.

Одед Голдрайх, Основы криптографии, том 1: Основные инструменты , Cambridge University Press, 2001.

[GoldwasserBellare-1] Перейти обратно: ^а ^б ^с ^д Гольдвассер С. и Белларе М. «Конспекты лекций по криптографии». Архивировано 21 апреля 2012 г. в Wayback Machine . Летний курс по криптографии, Массачусетский технологический институт, 1996–2001 гг.

[2] Определение 2.4 в Линделл, Иегуда. «Основы криптографии 89-856» (PDF) . Компьютерные науки, Университет Бар-Илан . Университет Бар-Илан. Архивировано из оригинала (PDF) 19 января 2022 года . Проверено 11 января 2016 г.

[3] FoC Гольдрейха, том 1, защита 2.5.5.

[4] Определение 3 в Холенштейн, Томас; и др. «Полная классификация билинейных аппаратных функций» (PDF) . Электронная версия IACR . МАКР . Проверено 11 января 2016 г.

[GoldLevin-5] О. Гольдрейх и Л. А. Левин, Жесткий предикат для всех односторонних функций , STOC 1989, стр. 25–32.

[6] FoC Гольдрейха, том 1, Теорема 2.5.6.

[JohanNaslund-7] Дж. Хостад , М. Наслунд, Безопасность всех битов RSA и дискретного журнала (2004) : Журнал ACM, 2004.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]