skip to content

Cryptography and Algorithmic Randomness

Friday 6th July 2012 - 10:00 to 10:30
INI Seminar Room 1
In modern cryptography, the random oracle model is widely used as an imaginary framework in which the security of a cryptographic scheme is discussed. In the random oracle model, the cryptographic hash function used in a cryptographic scheme is formulated as a random variable uniformly distributed over all possibility of the function, called the random oracle, and the legitimate users and the adversary against the scheme are modeled so as to get the values of the hash function not by evaluating it in their own but by querying the random oracle. Since the random oracle is an imaginary object, even if the security of a cryptographic scheme is proved in the random oracle model, the random oracle has to be instantiated using a concrete cryptographic hash function such as the SHA hash functions if we want to use the scheme in the real world. However, it is not clear how much the instantiation can maintain the security originally proved in the random oracle model, nor is it clear w hether the random oracle can be instantiated somehow while keeping the original security. In the present talk we investigate this problem using concepts and methods of algorithmic randomness. Our results use the general form of definitions of security notions for cryptographic schemes, and depend neither on specific schemes nor on specific security notions.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons