Кіріспе
Криптографияда, бір жолды функцияның f қатты өзекті предикаты – b предикаты (яғни, шығысы бір бит болатын функция) болып табылады, оны x функциясы ретінде есептеу оңай, бірақ f(x) берілген кезде есептеу қиын. Формальды түрде, x-тің кездейсоқ таңдауы бойынша жартысынан артық ықтималдықпен f(x)-тен b(x)-ты есептейтін полиномиалдық уақыт (PPT) алгоритмі жоқ. Басқаша айтқанда, егер x біркелкі түрде кездейсоқ таңылса, онда f(x) берілген кезде, кез келген PPT қарсыласы қатты өзекті b(x) биті мен біркелкі кездейсоқ битті x ұзындығына қарағанда маргіналды айырмашылықпен ғана ажырата алады. Қатты өзекті функция да осыған ұқсас анықталуы мүмкін. Яғни, егер x біркелкі түрде кездейсоқ таңылса, онда f(x) берілген кезде, кез келген PPT алгоритмі h(x) қатты өзекті функция мәні мен h(x) ұзындығындағы біркелкі кездейсоқ биттерді x ұзындығына қарағанда маргіналды айырмашылықпен ғана ажырата алады. Қатты өзекті предикат f-ті инверттеудің қиындығын «жинақтау мағынасында» көрсетеді. Бір жолды функцияны инверттеу қиын болса да, f(x) кескінінен c преобразы туралы ішінара ақпаратты есептеудің мүмкіндігі туралы кепілдіктер жоқ. Мысалы, RSA бір жолды функция деп болжанғанмен, кескіннің алдын ала бейнесінің Якоби символын кескіннің символынан оңай есептеуге болады. f бір жолды функция болсын. g(x,r) = (f(x), r) деп анықтаңыз, онда r ұзындығы x ұзындығымен бірдей. xj – x-тің j-інші битін, rj – r-дің j-інші битін білдірсін. Содан кейін 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) s. t. l(n) ≤ n болсын. Содан кейін h(x, r) := b1(x, r) b2(x, r) … bl(|x|)(x, r) – шығыс ұзындығы l(|x|) бар қатты өзекті функция. Кейде x-тың нақты биті қатты өзекті болады. Мысалы, RSA функциясына берілетін әрбір бит RSA-ның қатты өзекті предикаты болып табылады және x-тың O(log |x|) биттері полиномиалдық уақытта кездейсоқ бит тізбектерінен ажыратылмайды (RSA функциясын инверттеу қиын деген болжам бойынша). Қатты өзекті предикаттар кез келген бір жолды пермутациядан псевдокезеңді генераторды құрудың жолын береді. Егер b – f бір жолды пермутациясының қатты өзекті предикаты болса, ал s – кездейсоқ тұқым болса, онда fn – f-ті s-ке қолданудың n-інші қайталануын білдіреді, ал 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.