## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du séminaire du Mardi 5 Mai 2009

*The security of all bits using list decoding*

## par Carla Ràfols

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.