# The security of all bits using list decoding

Carla RàfolsIf 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.