How to exchange (secret) keys

ABSTRACT

A protocol is presented whereby two adversaries may exchange secrets, though neither trusts the other. The secrets are the prime factors of their publicly announced composite numbers. The two adversaries can exchange their secrets bit by bit, but each fears the other will cheat by sending “junk”bits. To solve this problem we show how each of the two can prove, for each bit delivered, that the bit is good. Applications are suggested to such electronic business transactions as the signing of contracts and the sending of certified electronic mail.

REFERENCES

• 1: L. Adleman, K. Manders, G. Miller, "On Taking Roots in Finite Fields," 18th Annual IEEE Symposium on Foundations of Comp. Sci. (1977), 175-177.
• 2: D. Angluin, "Lecture Notes on the Complexity of some Problems in Number Theory," Yale U., Dept. of Computer Science, Tech. Report 243 (August 1982), 71 pp.
• 3: Eric Bach, Fast algorithms under the extended riemann hypothesis: A concrete estimate, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.290-295, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802203]
• 4: E. R. Berlekamp, "Factoring Polynomials over Large Finite Fields," Math. of Comp., Vol. 24 (1970), 713-735.
• 5: M. Blum and M. O. Rabin, "Mail Certification by Randomization," to appear.
• 6: W. Diffie and M. E. Hellman, "Privacy and Authentication: An Introduction to Cryptography," Proc. IEEE, Vol.67, No. 3 (March 1979), 397-427.
• 7: S. Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts," Tech. Report #233, The Technion, Israel (Feb. 1982), 11 pp.
• 8: G. Kolata, "Cryptographers Gather to Discuss Research," Science, vol. 214, no. 6 (Nov 1981), 646-647.
• 9: W. J. LeVeque, "Fundamentals of Number Theory," Addison-Wesley Pub., 1977.
• 10: G. L. Miller, "Riemann's Hypothesis and a Test for Primality," J. Comput. and System Sci., Vol. 13 (1976), 300-317.
• 11: I. Peterson, "Whom Do You Trust," Science News, vol 120, No 13 (Sept 1981), 205-206.
• 12: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 13: M. O. Rabin, "How to Exchange Secrets by Oblivious Transfer," Harvard Center for Research in Computer Technology, manuscript (1981).
• 14: M. O. Rabin, "Transaction Protection by Beacons," Harvard Center for Research in Computer Technology, TR-29-81 (1981).
• 15: M. O. Rabin, "Probabilistic Algorithm for Testing Primality," J. Number Theory, Vol. 12 (1980), 128-138.
• 16: 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]
• 17: Daniel Shanks, Solved and unsolved problems in number theory, Chelsea Publishing Co., Inc., New York, 1985
• 18: R. Solovay and V. Strassen, "A Fast Monte-Carlo Test for Primality," SIAM J. Comput. Vol. 6 (1977), 84-85.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Security, Theory