Paper 2006/020

Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes

Adam Smith

Abstract

When communicating over a noisy channel, it is typically much easier to deal with random, independent errors with a known distribution than with adversarial errors. This paper looks at how one can use schemes designed for random errors in an adversarial context, at the cost of relatively few additional random bits and without using unproven computational assumptions. The basic approach is to permute the positions of a bit string using a permutation drawn from a $t$-wise independent family, where $t=o(n)$. This leads to two new results: 1. We construct *computationally efficient* information reconciliation protocols correcting $pn$ adversarial binary Hamming errors with optimal communication and entropy loss $n(h(p)+o(1))$ bits, where $n$ is the length of the strings and $h()$ is the binary entropy function. Information reconciliation protocols are important tools for dealing with noisy secrets in cryptography; they are also used to synchronize remote copies of large files. 2. We improve the randomness complexity (key length) of efficiently decodable capacity-approaching "private codes" from $\Theta(n\log n)$ to $n+o(n)$. We also present a simplified proof of an existential result on private codes due to Langberg (FOCS '04).

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Information reconciliationfuzzy cryptographyerror-correcting codesprivate codesinformation theoryderandomizationcombinatorial cryptography
Contact author(s)
adam smith @ weizmann ac il
History
2006-01-23: revised
2006-01-17: received
See all versions
Short URL
https://ia.cr/2006/020
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/020,
      author = {Adam Smith},
      title = {Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/020},
      year = {2006},
      url = {https://eprint.iacr.org/2006/020}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.