The security of all bits using list decoding

If some reasonable computational assumptions hold, a one-way function is easy to compute but hard to invert. In some cases, this security requirement may not be enough: in particular, the definition of one-way function does not say anything about how much information it can leak. A predicate P of the preimage is a hard-core of f if f does not give away any information about P , that is, if there exists a polynomial time reduction from guessing P to inverting f.

For instance, it is known that the least significant bit of the message is a hard-core of the RSA trapdoor permutation. This and similar results may seem anecdotic at first sight, but as it turns out, hard-core bits are closely related to fundamental concepts of cryptography, such as semantically secure encryption or pseudorandom generators.

The relation between list decoding and hard-core predicates of Akavia, Goldwasser and Safra of 2003 has provided a “clean and easy” methodology to prove the hardness of certain predicates. A part from being yet another elegant example of an interaction between coding and complexity theory, their approach results in simpler proofs of classical bit security results. Akavia, Goldwasser and Safra only used the methodology to prove that the O (log log N ) least and most significant bits of the most common cryptographic one-way functions are secure. In this talk we show that the method applies to any bit of the preimage. We thus reprove the security of all bits of RSA or the discrete logarithm in a group of prime order, corresponding to the well-known results of Haastad and Näslund of 2000.

These results are due to joint work with Paz Morillo (Universitat Politècnica de Catalunya) and were presented in Public Key Cryptography 2009.