Answers to some frequently asked questions regarding Foundations of Cryptography

Oded Goldreich

I am starting a new webpage for frequently asked questions regarding the Foundations of Cryptography and/or my book on this topic.

On the randomness assumed in cryptography

In the standard definitions, one assumes access to a perfect source of randomness (i.e., uniform distribution over $n$-bit strings, for any $n$ that is at most polynomial in the security parameter). But in reality it may be infeasible (or even impossible) to get hold of such a perfect source.

Firstly, note that we do not need to assume that the world is truly random (i.e., contains random phenomena), but rather that it contains phenomena that look random to us. (Indeed, this is carrying the computational indistinguishability paradigm to an extreme.)

Second, these phenomena need not be perfectly random (or appear as if they are perfectly random); it suffices that they be (or appear) somewhat random (i.e., weakly random). The gap between perfect randomness and weak randomness is bridged by randomness extraction (which is a research direction that received much attention). See Ronen Shaltiel's excellent survey.

Lastly, let me mention that some relatively recent research addresses the question of what happens if the cryptographic key (assumed to be perfectly random) is only weakly random, or parts of it are leaked. In general, this may deem the scheme insecure, but schemes may be constructed to be robust under such a leakage.

Back to homepage.