Abstract:

    We explore what kinds of information two parties must
communicate in order to correct errors which occur in a shared secret
string W. Any bits they communicate must leak a significant amount of
information  about W --- that is, from the adversary's point of view,
the entropy of W will drop significantly. Nevertheless, we construct
schemes with which Alice and Bob can prevent an adversary from 
learning any *useful* information about W, in the following sense: 
if the entropy of W is sufficiently high, then there is no function f(W) 
which the adversary can learn from the error-correction information with
significant probability. This leads to several new results:

1. Weak Obfuscation of Proximity Queries:

  An obfuscator for a functionality g generates a scrambled circuit
which allows one to evaluate g on any input, but leaks no additional
information. We show how to (weakly) obfuscate *proximity queries*: we
design a randomized function Obf(w) such that for any w, given Obf(w)
one can verify if a candidate string y is close to w, yet if an
adversary's a priori probability of guessing w was low, Obf(w) reveals
no function of w. This corresponds to constructing noise-tolerant
"perfectly one-way hash functions" (Canetti et al., STOC 1998).

2. Private "Fuzzy Extractors'':

  A fuzzy extractor (Dodis et al., Eurocrypt 2004) takes a nonuniformly 
random, error-prone input W (e.g. a fingerprint or iris scan) 
and produces two outputs, a public string P and a key R, with two
guarantees: R is uniformly random given P, and yet given both P and 
any string Y close to W, one can recover R exactly. Our constructions 
yield fuzzy extractors with an added privacy guarantee: P reveals no 
function of the original input W. This means, in particular, that a 
sensitive sub-string of W will not accidentally be revealed.

3. Noise Tolerance and Key Re-Use in the Bounded Storage Model:

  We give a scheme for key extraction in the bounded storage model 
with noise (Y.-Z. Ding, TCC 2005) which allows one to re-use the same 
initial key to derive many different session keys based on long public 
random strings. This answers the main open question from Ding's work.

Joint work with Yevgeniy Dodis (New York University). To appear at 
STOC 2005.