Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes

ABSTRACT

Communicating over a noisy channel is typically much easier when errors are drawn from a fixed, known distribution than when they are chosen adversarially. This paper looks at how one can use schemes designed for random errors in an adversarial context, at the cost of few additional random bits and without relying on 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 several new results:

• We show that concatenated codes can correct errors up to the Shannon capacity even when the errors are only slightly random --- it is sufficient that they be t-wise independently distributed, for t roughly ω(log n).

• We construct computationally efficient information reconciliation protocols correcting pn adversarial binary Hamming errors with optimal communication complexity 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 allow cooperating parties to correct errors in a shared string. They are important tools in two applications: first, for dealing with noisy secrets in cryptography; second, for synchronizing remote copies of large files. Entropy loss measures how much information is leaked to an eavesdropper listening in on the protocol.

• We improve the randomness complexity (key length) of efficiently decodable capacity-approaching private codes from Θ(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).

REFERENCES

• 1: Charles H. Bennett , Gilles Brassard , Jean-Marc Robert, Privacy amplification by public discussion, SIAM Journal on Computing, v.17 n.2, p.210-229, April 1988 [doi>10.1137/0217014]
• 2: C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41(6):1915--1923, 1995.
• 3: Gilles Brassard , Louis Salvail, Secret-key reconciliation by public discussion, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.410-423, January 1994, Lofthus, Norway
• 4: Graham Cormode , Mike Paterson , Süleyman Cenk Sahinalp , Uzi Vishkin, Communication complexity of document exchange, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.197-206, January 09-11, 2000, San Francisco, California, United States
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: Y. Z. Ding. Error correction in the bounded storage model. In Kilian {20}.
• 7: Y. Z. Ding, P. Gopalan, and R. J. Lipton. Error correction against computationally bounded adversaries. Manuscript. Appeared initially as {23}, 2004.
• 8: Y. Z. Ding, D. Harnik, A. Rosen, and R. Shaltiel. Constant-round oblivious transfer in the bounded storage model. In TCC 2004, pages 446--472, 2004.
• 9: Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. Technical Report 2003/235, Cryptology ePrint archive, http://eprint.iacr.org, 2006. Previous version appeared at EUROCRYPT 2004.
• 10: Yevgeniy Dodis , Adam Smith, Correcting errors without leaking partial information, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060688]
• 11: P. Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory, 37(1):5--12, 1991.
• 12: G. D. Forney. Concatenated Codes. PhD thesis, MIT, 1966.
• 13: V. Guruswami. List decoding with side information. In IEEE Conference on Computational Complexity, pages 300-. IEEE Computer Society, 2003.
• 14: V. Guruswami, J. Håstad, M. Sudan, and D. Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021--1034, 2002.
• 15: Venkatesan Guruswami , Atri Rudra, Explicit capacity-achieving list-decodable codes, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132518]
• 16: Venkatesan Guruswami , Madhu Sudan, List decoding algorithms for certain concatenated codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.181-190, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335327]
• 17: A. Juels and M. Sudan. A fuzzy vault scheme. In IEEE International Symposium on Information Theory, 2002.
• 18: Ari Juels , Martin Wattenberg, A fuzzy commitment scheme, Proceedings of the 6th ACM conference on Computer and communications security, p.28-36, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319714]
• 19: E. Kaplan, M. Naor, and O. Reingold. Derandomized constructions of k-wise (almost) independent permutations. In APPROX-RANDOM, pages 354--365, 2005.
• 20: J. Kilian, editor. First Theory of Cryptography Conference --- TCC 2005, volume 3378 of Lecture Notes in Computer Science. Springer-Verlag, Feb. 10--12 2005.
• 21: Michael Langberg, Private Codes or Succinct Random Codes That Are (Almost) Perfect, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.325-334, October 17-19, 2004 [doi>10.1109/FOCS.2004.51]
• 22: J.-P. M. G. Linnartz and P. Tuyls. New shielding functions to enhance privacy and prevent misuse of biometric templates. In AVBPA, pages 393--402, 2003.
• 23: Richard J. Lipton, A New Approach To Information Theory, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.699-708, February 24-26, 1994
• 24: S. Micali, C. Peikert, M. Sudan, and D. Wilson. Optimal error correction against computationally bounded noise. In Kilian {20}.
• 25: Y. Minsky and A. Trachtenberg. Scalable set reconciliation. In 40th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, Oct. 2002. See also tehcnial report BU-ECE-2002-01.
• 26: Y. Minsky, A. Trachtenberg, and R. Zippel. Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory, 49(9):2213--2218, 2003.
• 27: A. Orlitsky. Worst-case interactive communication i: Two messages are almost optimal. IEEE Transactions on Information Theory, 36(5):1111--1126, 1990.
• 28: A. Orlitsky. Average-case interactive communication. IEEE Transactions on Information Theory, 38(5):1534--1547, 1992.
• 29: Alon Orlitsky, Interactive communication of balanced distributions and of correlated files, SIAM Journal on Discrete Mathematics, v.6 n.4, p.548-564, Nov. 1993 [doi>10.1137/0406043]
• 30: R. Renner and S. Wolf. The exact price for unconditionally secure asymmetric cryptography. In C. Cachin and J. Camenisch, editors, EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 109--125. Springer-Verlag, 2004.
• 31: R. Renner and S. Wolf. Simple and tight bounds for information reconciliation and privacy amplification. In B. Roy, editor, Advances in Cryptology---ASIACRYPT 2005, Lecture Notes in Computer Science, Chennai, India, 4--8 Dec. 2005. Springer-Verlag.
• 32: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
• 33: A. Smith. Scrambling aversarial errors using few random bits. IACR ePrint report 2006/020, available at http://eprint.iacr.org, 2006.
• 34: H. Stichtenoth. Algebraic Function Fields and Codes. Springer, 1993.
• 35: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 36: V. V. Zyablov and M. S. Pinsker. List cascade decoding. Problems of Information Transmission, 17(4):29--34, 1981. (In Russian); pp. 236--240 (in English), 1982.