Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit SA and SB, respectively, such that with probability 1+ε/2 these bits are equal. Further assume that conditioned on the event SA =n SB no polynomial time bounded algorithm can predict the bit better than with probability 1-δ/2. Is it possible to obtain key agreement from such a primitive? We show that for constant δ and ε the answer is yes if and only if δ > 1-ε/1+ε, both for uniform and non-uniform adversaries.The main computational technique used in this paper is a strengthening of Impagliazzo's hard-core lemma to the uniform case and to a set size parameter which is tight (i.e., twice the original size). This may be of independent interest.

REFERENCES

• 1: R. Ahlswede and I. Csiszár. Common randomness in information theory and cryptography---Part I: secret sharing. IEEE Trans.on Inf.Th.,39(4):1121--1132.1993.
• 2: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 3: W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. on Inf. Theory, IT-22(6):644--654, 1976.
• 4: C. Dwork, M. Naor, and O. Reingold. Immunizing encryption schemes from decryption errors. In C. Cachin and J. Camenisch, ed., EUROCRYPT 2004, volume 3027 of LNCS, pages 342--360, 2004.
• 5: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 6: O. Goldreich, N. Nisan, and A. Wigderson. On Yao's XOR-lemma. ECCC Report TR95-050, 1995.
• 7: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 8: R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.538, October 23-25, 1995
• 9: R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In 30th FOCS, pages 230--235, 1989.
• 10: R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
• 11: Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Sets, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.624, October 17-18, 1999
• 12: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 13: U. Maurer. Secret key agreement by public discussion. IEEE Trans. on Inf. Theory, 39(3):733--742, 1993.
• 14: U. Maurer and S. Wolf. Unconditionally secure key agreement and the intrinsic conditional information. IEEE Trans. on Inf. Theory, 45(2):499--514, 1999.
• 15: R. J. McEliece. A public key cryptosystem based on algebraic coding theory. DSN Progress Report 42-44:114--116, Jet Propulsion Lab, NASA, 1978.
• 16: R. Renner and S. Wolf. New bounds in secret-key agreement: The gap between formation and secrecy extraction. In E. Biham, ed., EUROCRYPT 2003, volume 2656 of LNCS, pages 562--577, 2003.
• 17: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 18: Steven Rudich, The Use of Interaction in Public Cryptosystems (Extended Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.242-251, August 11-15, 1991
• 19: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 20: Luca Trevisan, List-Decoding Using The XOR Lemma, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.126, October 11-14, 2003
• 21: J. von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295--320, 1928.
• 22: Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Theory

Keywords:
cryptography, hard-core sets, key agreement