Введение
В криптографии, твёрдое ядро предиката односторонней функции f является предикатом b (т.е. функцией, выход которой – один бит), который легко вычислить (как функцию от x), но трудно вычислить, зная f(x). В формальном выражении, не существует вероятностного алгоритма полиномиального времени (PPT), который вычисляет b(x) из f(x) с вероятностью значительно большей половины при случайном выборе x. Иными словами, если x выбрано равномерно случайным образом, то, зная f(x), любой PPT-противник может отличать бит твёрдого ядра b(x) от равномерно случайного бита лишь с пренебрежимо малым преимуществом относительно длины x. Функция твёрдого ядра может быть определена аналогично. То есть, если x выбирается равномерно случайным образом, то, зная f(x), любой PPT-алгоритм может отличать значение функции твёрдого ядра h(x) от равномерно случайных битов длины |h(x)| лишь с пренебрежимо малым преимуществом относительно длины x. Предикат твёрдого ядра «в концентрированном смысле» отражает сложность инвертирования f. В то время как одностороннюю функцию трудно инвертировать, нет гарантий относительно возможности вычисления частичной информации об исходном значении c по образу f(x). Например, хотя RSA предполагается односторонней функцией, символ Якоби исходного значения можно легко вычислить по символу Якоби образа. Пусть f – односторонняя функция. Определим g(x, r) = (f(x), r), где длина r равна длине x. Пусть xj обозначает j-й бит x, а rj – j-й бит r. Тогда это является предикатом твёрдого ядра g. Обратите внимание, что b(x, r) = <x, r>, где <·, ·> обозначает стандартное внутреннее произведение на векторном пространстве (Z2)n. Этот предикат является твёрдым ядром из-за вычислительных сложностей; то есть, его не трудно вычислить, потому что g(x, r) – информация, теоретически теряемая. Скорее, если существует алгоритм, эффективно вычисляющий этот предикат, то существует другой алгоритм, эффективно инвертирующий f. Аналогичная конструкция даёт функцию твёрдого ядра с O(log |x|) выходными битами. Предположим, что f – сильная односторонняя функция. Определим g(x, r) = (f(x), r), где |r| = 2|x|. Выберем функцию длины l(n) = O(log n) так, что l(n) ≤ n. Пусть затем h(x, r) := b1(x, r) b2(x, r) … bl(|x|)(x, r) – функция твёрдого ядра с длиной выхода l(|x|). Иногда бывает так, что фактический бит входного x является твёрдым ядром. Например, каждый отдельный бит входных данных функции RSA является предикатом твёрдого ядра RSA, и блоки O(log |x|) битов x неотличимы от случайных битовых строк за полиномиальное время (при условии, что функция RSA трудно инвертировать). Предикаты твёрдого ядра дают способ построить псевдослучайный генератор из любой односторонней перестановки. Если b – предикат твёрдого ядра односторонней перестановки f, а s – случайное начальное значение, то это является псевдослучайной битовой последовательностью, где fn означает n-ю итерацию применения f к s, а b – сгенерированный бит твёрдого ядра на каждом шаге n. Предикаты твёрдого ядра односторонних перестановок с секретным ключом (известные как предикаты с секретным ключом) могут использоваться для построения семантически безопасных схем шифрования с открытым ключом.
While a one way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimage c from the image f(x). For instance, while RSA is conjectured to be a one way function, the Jacobi symbol of the preimage can be easily computed from that of the image. Let f be a one way function. Define g(x,r) = (f(x), r) where the length of r is the same as that of x. Let xj denote the jth bit of x and rj the jth bit of r. Then
is a hard core predicate of g. Note that b(x, r) = <x, r> where <·, ·> denotes the standard inner product on the vector space (Z2)n. This predicate is hard core due to computational issues; that is, it is not hard to compute because g(x, r) is information theoretically lossy. Rather, if there exists an algorithm that computes this predicate efficiently, then there is another algorithm that can invert f efficiently. A similar construction yields a hard core function with O(log |x|) output bits. Suppose f is a strong one way function. Define g(x, r) = (f(x), r) where |r| = 2|x|. Choose a length function l(n) = O(log n) s. t. l(n) ≤ n. Let
Then h(x, r) := b1(x, r) b2(x, r) bl(|x|)(x, r) is a hard core function with output length l(|x|). It is sometimes the case that an actual bit of the input x is hard core. For example, every single bit of inputs to the RSA function is a hard core predicate of RSA and blocks of O(log |x|) bits of x are indistinguishable from random bit strings in polynomial time (under the assumption that the RSA function is hard to invert). Hard core predicates give a way to construct a pseudorandom generator from any one way permutation. If b is a hard core predicate of a one way permutation f, and s is a random seed, then
is a pseudorandom bit sequence, where fn means the n th iteration of applying f on s, and b is the generated hard core bit by each round n.
Hard core predicates of trapdoor one way permutations (known as trapdoor predicates) can be used to construct semantically secure public key encryption schemes.