How to simultaneously exchange secrets by general assumptions

ABSTRACT

The simultaneous secret exchange protocol is the key tool for contract signing protocols and certified mail protocols. This paper proposes efficient simultaneous secret exchange protocols (or gradual secret releasing protocols) that are based on general assumptions such as the existence of one-way permutations and one-way functions, while the existing efficient simultaneous secret exchange protocols are based on more constrained assumptions such as specific number theoretic problems and the existence of oblivious transfer primitives (or trap-door one-way permutations). Moreover, while the existing simultaneous secret exchange protocols have an additional requirement that the underlying commit (encryption) function is “ideal”, the above-mentioned “general assumptions” are provably sufficient for our schemes. Therefore, our protocols are provably secure under the general assumptions. In addition, our protocols are at least as efficient as the existing practical protocols, when efficient one-way permutations and one-way functions are used.

REFERENCES

• BCDG: Ernest F. Brickell , David Chaum , Ivan Damgård , Jeroen van de Graaf, Gradual and Verifiable Release of a Secret, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.156-166, August 16-20, 1987
• BGMR: M. Ben-Or, O. Goldreich, S. Micali, and R. Rivcst, "A Fair Protocol for Signing Contracts," IEEE Tran. on IT, Vol. 36, Number 1, pp.40-46 (1990)
• Blu: Manuel Blum, How to exchange (secret) keys, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.440-447, December 1983 [doi>10.1145/800061.808775]
• Cle: Richard Cleve, Controlled gradual disclosure schemes for random bits and their applications, Proceedings on Advances in cryptology, p.573-588, July 1989, Santa Barbara, California, United States
• Dam: I. Damg~rd, "Practical and Provably Secure Exchange of Digital Signatures (Extended Abstract)," to appear in Proc. of EURO- CRYPT'93
• EGL: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• FFS: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• GrL: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• GwL: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• GMW: O. Goldreich, S. Micali, and A. Wigderson, "Proof that Yield Nothing but their Validity and a Methodilogy of Cryptographic Protocol Design," Proc. of FOCS'86 (1986)
• Has: J. Håstad, Pseudo-random generators under uniform assumptions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.395-404, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100270]
• ILL: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• LMR: M. Luby, S. Micali, and C. Rackoff, "How to Simultaneously Exchange Secret Bit by Flipping a Symmetrically-Biased Coin," Proc. of FOCS'83, pp.23-30 (1983)
• Nao: Moni Naor, Bit commitment using pseudo-randomness (extended abstract), Proceedings on Advances in cryptology, p.128-136, July 1989, Santa Barbara, California, United States
• Rab: M. Rabin, "How to Exchange Secrets by Oblivious Transfer," Tech. Menlo, TR-81, Aiken Comp. Lab., Harvard University (1981)
• Yao: A. Yao, "How to Generate and Exchange Secrets," Proc. of FOCS'86, pp.162-167 (1986)

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Theory, Verification