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).Category / Keywords: cryptographic protocols / Information reconciliation, fuzzy cryptography, error-correcting codes, private codes, information theory, derandomization, combinatorial cryptography Date: received 17 Jan 2006, last revised 23 Jan 2006 Contact author: adam smith at weizmann ac il Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20060123:135618 (All versions of this report) Discussion forum: Show discussion | Start new discussion