### 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.