Editing Hard-core predicate

In [[cryptography]], a '''hard-core predicate''' of a [[one-way function]] ''f'' is a [[Predicate (mathematics)|predicate]] ''b'' (i.e., a function whose output is a single bit) which is easy to compute (as a function of ''x'') but is hard to compute given ''f(x)''.  In formal terms, there is no [[Bounded-error probabilistic polynomial|probabilistic polynomial-time (PPT) algorithm]] that computes ''b(x)'' from ''f(x)'' with probability [[negligible function (cryptography)|significantly greater]] than one half over random choice of ''x''.<ref name=GoldwasserBellare>[[Shafi Goldwasser|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Webarchive|url=https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html |date=2012-04-21 }}. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|34}} In other words, if ''x'' is drawn uniformly at random, then given ''f(x)'', any PPT adversary can only distinguish the hard-core bit ''b(x)'' and a uniformly random bit with negligible [[Advantage (cryptography)|advantage]] over the length of ''x''.<ref>Definition 2.4 in {{cite web|last1=Lindell|first1=Yehuda|title=Foundations of Cryptography 89-856|url=http://u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf|website=Computer Science, Bar Ilan University|publisher=Bar Ilan University|accessdate=11 January 2016|archive-date=19 January 2022|archive-url=https://web.archive.org/web/20220119043828/https://u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf|url-status=dead}}</ref>

A '''hard-core function''' can be defined similarly. That is, if ''x'' is chosen uniformly at random, then given ''f(x)'', any PPT algorithm can only distinguish the hard-core function value ''h(x)'' and uniformly random bits of length ''|h(x)|'' with negligible advantage over the length of ''x''.<ref>Goldreich's FoC, vol 1, def 2.5.5.</ref><ref>Definition 3 in {{cite web|last1=Holenstein|first1=Thomas|title=Complete Classification of Bilinear Hard-Core Functions|url=https://www.iacr.org/archive/crypto2004/31520072/HMS_final_1.pdf|website=IACR eprint|publisher=IACR|accessdate=11 January 2016|display-authors=etal}}</ref>

A hard-core predicate captures "in a concentrated sense" the hardness of inverting ''f''.

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 (algorithm)|RSA]] is conjectured to be a one-way function, the [[Jacobi symbol]] of the preimage can be easily computed from that of the image.<ref name=GoldwasserBellare />{{rp|121}}

It is clear that if a [[injective function|one-to-one function]] has a hard-core predicate, then it must be one way.  [[Oded Goldreich]] and [[Leonid Levin]] (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate.<ref name=GoldLevin>O. Goldreich and L.A. Levin, [http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.95.2079&rep=rep1&type=pdf A Hard-Core Predicate for all One-Way Functions], STOC 1989, pp25&ndash;32.</ref>  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 ''x<sub>j</sub>'' denote the ''j''<sup>th</sup> bit of ''x'' and  ''r<sub>j</sub>'' the ''j''<sup>th</sup> bit of ''r''. Then

<math> b(x,r) := \langle x, r\rangle = \bigoplus_j x_j r_j </math>

is a hard core predicate of ''g''. Note that ''b(x, r)'' =  <''x, r''> where <·, ·> denotes the standard [[Inner product space|inner product]] on the [[vector space]] ('''Z'''<sub>2</sub>)<sup>''n''</sup>.  This predicate is hard-core due to computational issues; that is, it is not hard to compute because ''g(x, r)'' is [[information theory|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

<math> b_i(x, r) = \bigoplus_j x_j r_{i+j}. </math>

Then ''h(x, r)'' := ''b<sub>1</sub>(x, r) b<sub>2</sub>(x, r) ... b<sub>l(|x|)</sub>(x, r)'' is a hard-core function with output length ''l(|x|)''.<ref>Goldreich's FoC, vol 1, Theorem 2.5.6.</ref>

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).<ref name=JohanNaslund>[[Johan Håstad|J. Håstad]], M. Naslund, [http://www.csc.kth.se/tcs/tfrutv99/rsabit.pdf The Security of all RSA and Discrete Log Bits (2004)]: Journal of the ACM, 2004.</ref>

Hard-core predicates give a way to construct a [[CSPRNG|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

<math> \{ b(f^n(s))\}_n</math>

is a pseudorandom bit sequence, where ''f<sup>n</sup>'' means the n-th iteration of applying ''f'' on ''s'', and ''b'' is the generated hard-core bit by each round ''n''.<ref name=GoldwasserBellare />{{rp|132}}

Hard-core predicates of trapdoor one-way permutations (known as '''trapdoor predicates''') can be used to construct [[semantic security|semantically secure]] public-key encryption schemes.<ref name=GoldwasserBellare />{{rp|129}}

==See also==
* [[List-decoding]] (describes list decoding; the core of the Goldreich-Levin construction of hard-core predicates from one-way functions can be viewed as an algorithm for list-decoding the [[Hadamard code]]).

==References==
{{reflist}}
* Oded Goldreich, ''Foundations of Cryptography vol 1: Basic Tools'', Cambridge University Press, 2001.

{{DEFAULTSORT:Hard-Core Predicate}}
[[Category:Pseudorandomness]]
[[Category:Theory of cryptography]]