** Reference:**
* Advances in Cryptology - EUROCRYPT 2000.*
Lecture Notes in Computer Science, vol. 1807, Pages 453-469,
Springer-Verlag, 2000.

** Abstract: **
We study the problem of *partial key exposure*. Standard
cryptographic definitions and constructions do not guarantee any
security even if a tiny fraction of the secret key is compromised.
We show how to build cryptographic primitives that remain secure
even when an adversary is able to learn *almost all* of the
secret key.

The key to our approach is a new primitive of independent interest,
which we call an *Exposure-Resilient Function* (ERF) -- a
deterministic function whose output appears random (in a perfect,
statistical or computational sense) even if almost all the bits of
the input are known. ERF's by themselves efficiently solve the partial
key exposure problem in the setting where the secret is simply a random
value, like in private-key cryptography. They can also be viewed as very
secure pseudorandom generators, and have many other applications.

To solve the general partial key exposure problem, we use the
(generalized) notion of an *All-Or-Nothing Transform* (AoNT), an
invertible (randomized) transformation *T* which, nevertheless,
reveals "no information" about *x* even if almost all the bits
of *T(x)* are known. By applying an AoNT to the secret key of
any cryptographic system, we obtain security against partial key exposure.
To date, the only known security analyses of AoNT candidates were made
in the random oracle model.
We show how to construct ERF's and AoNT's with nearly optimal
parameters. Our computational constructions are based on any one-way
function. We also provide several applications and additional
properties concerning these notions.

** Keywords: **
Key exposure, All-or-nothing transforms, Exposure-resilient functions.

** Availability: **
Paper available as Compressed PostScript (105 Kbyte).

Shai Halevi's home page.