en>ChrisGualtieri: General Fixes using AWB

2013-11-02T19:39:32Z

General Fixes using AWB

New page

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 given ''x'' but is hard to compute given ''f(x)''. In formal terms, there is no [[Bounded-error probabilistic polynomial|probabilistic polynomial-time 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"]. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|34}}

A '''hard-core function''' can be defined similarly.

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–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 <math>x_j</math> denote the ''j''<sup>th</sup> bit of ''x'' and <math>r_j</math> the ''j''<sup>th</sup> bit of ''r''. Then

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

is a hard core predicate of ''g''. Note that <math>b(x,r) = \langle x, r \rangle</math> where <math>\langle \cdot, \cdot \rangle</math> denotes the standard [[Inner product space|inner product]] on the [[vector space]] <math>(\Z/2\Z)^n</math>. 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 an algorithm exists to compute this predicate efficiently, then an algorithm exists to invert ''f'' efficiently. A similar construction yields a hard-core function with ''log (|x|)'' output bits.{{Citation needed|date=January 2011}}

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 <math>O(\log |x|)</math> 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 (JACM), 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>\left \{ b ( f^n ( s ) ) \right \}_n</math>

is a pseudorandom bit sequence.<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]]

Knight shift - Revision history

en>ChrisGualtieri: General Fixes using AWB