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

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

Аналогично можно определить функцию hard-core. То есть, если x выбирается равномерно случайным образом, то при заданной f(x) любой алгоритм PPT может различать только значение функции hard-core 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 ^-й бит r . Тогда

${\displaystyle 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), где | r | = 2| x |. Выберем функцию длины l(n) = O(log n) st l(n) ≤ n . Пусть

${\displaystyle 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(|x|) . ^[6]

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

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

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

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

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

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

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