Correcting errors without leaking partial information

Yevgeniy Dodis, Adam Smith

Research output: Contribution to journalConference articlepeer-review


This paper explores 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. Specifically, 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: (a) the design of noise-tolerant "perfectly oneway" hash functions in the sense of Canetti et al. [7], which in turn leads to obfuscation of proximity queries for high entropy secrets W; (b) private fuzzy extractors [11], which allow one to extract uniformly random bits from noisy and nonuniform data W, while also insuring that no sensitive information about W is leaked; and (c) noise tolerance and stateless key re-use in the Bounded Storage Model, resolving the main open problem of Ding [10]. The heart of our constructions is the design of strong randomness extractors with the property that the source W can be recovered from the extracted randomness and any string W′ which is close to W.

Original languageEnglish (US)
Pages (from-to)654-663
Number of pages10
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2005
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005


  • Bounded Storage Model
  • Code Obfuscation
  • Cryptography
  • Entropic Security
  • Error-Correcting Codes
  • Information Reconciliation
  • Randomness Extractors

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Correcting errors without leaking partial information'. Together they form a unique fingerprint.

Cite this