[Resource Topic] 2005/029: A model and architecture for pseudo-random generation with applications to /dev/random

Welcome to the resource topic for 2005/029

A model and architecture for pseudo-random generation with applications to /dev/random

Authors: Boaz Barak, Shai Halevi


We present a formal model and a simple architecture for robust pseudorandom generation that ensures resilience in the face of an
observer with partial knowledge/control of the generator’s entropy source. Our model and architecture have the following properties:

1 Resilience: The generator’s output looks random to an observer with no knowledge of the internal state. This holds even if that observer has complete control over data that is used to refresh the internal state.

2 Forward security: Past output of the generator looks random to an observer, even if the observer learns the internal state at a later time.

3 Backward security/Break-in recovery: Future output of the generator looks random, even to an observer with knowledge of the current state, provided that the generator is refreshed with data of sufficient entropy.

Architectures such as above were suggested before. This work differs
from previous attempts in that we present a formal model for robust
pseudo-random generation, and provide a formal proof within this model
for the security of our architecture. To our knowledge, this is the
first attempt at a rigorous model for this problem.

Our formal modeling advocates the separation of the entropy extraction phase from the output generation phase. We argue that the former is information-theoretic in nature, and could therefore rely on combinatorial and statistical tools rather than on cryptography. On the other hand, we show that the latter can be implemented using any standard (non-robust) cryptographic PRG.

We also discuss the applicability of our architecture for applications such as /dev/(u)random in Linux and pseudorandom generation on smartcards.

ePrint: https://eprint.iacr.org/2005/029

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .