Algorithmes et complexité
mardi 29 janvier 2019, 11h00, Salle 1007
Balthazar Bauer (ENS) An application of communication complexity to cryptography

The hash function are very important primitives in cryptology. To use it, we need to trust the designer. To solve this problem, we can combine several hash functions independently built. But we have to suppose that the designers could communicate. That's why we can reduce the security properties to communication complexity problems. After a presentation of these reductions, we will look in details the communication problems linked to these properties, our knowledge, new results about them. And at the end the open problems that challenge us will be presented.