Abstract
An optimally resilient distributed multiplication protocol that enjoys the property of non-interactivity is presented. The protocol relies on a standard cryptographic assumption and works over a complete, synchronous, untappable network with a broadcast channel. As long as no disruption occurs, each player uses those channels only once to send messages; thus no interaction is needed among players. The cost is an increase in local computation and communication complexity that is determined by the factor of the threshold.
As an application of the proposed protocol we present a robust threshold version of the Cramer-Shoup cryptosystem, which is the first non-interactive solution with optimal resilience.
Chapter PDF
Similar content being viewed by others
References
D. Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4:75–122, 1991.
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for noncyptographic fault-tolerant distributed computation. In Proceedings of the 20th annual ACM Symposium on the Theory of Computing, pages 1–10, 1988.
D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In B. S. Kaliski Jr., editor, Advances in Cryptology — CRYPTO’ 97, volume 1294 of Lecture Notes in Computer Science, pages 425–439. Springer-Verlag, 1997.
R. Canetti and S. Goldwasser. An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack. In Jacques Stern, editor, Advances in Cryptology — EUROCRYPT’ 99, volume 1592 of Lecture Notes in Computer Science, pages 90–106. Springer-Verlag, 1999.
M. Cerecedo, T. Matsumoto, and H. Imai. Efficient and secure multiparty generation of digital signatures based on discrete logarithms. IEICE Transaction of Fundamentals of electronic Communications and Computer Science, E76-A(4):532–545, April 1993.
D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols. In Proceedings of the 20th annual ACM Symposium on the Theory of Computing, pages 11–19, 1988.
R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations secure against an adaptive adversary. In Jacques Stern, editor, Advances in Cryptology — EUROCRYPT’ 99, volume 1592 of Lecture Notes in Computer Science, pages 311–326. Springer-Verlag, 1999.
R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In W. Fumy, editor, Advances in Cryptology — EUROCRYPT’ 97, volume 1233 of Lecture Notes in Computer Science, pages 103–118. Springer-Verlag, 1997.
R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, Advances in Cryptology — CRYPTO’ 98, volume 1462 of Lecture Notes in Computer Science, pages 13–25. Springer-Verlag, 1998.
Y. G. Desmedt and Y. Frankel. Threshold cryptosystems. In G. Brassard, editor, Advances in Cryptology-CRYPTO’ 89, volume 435 of Lecture Notes in Computer Science, pages 307–315. Springer-Verlag, 1990.
P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science, pages 427–437, 1987.
P. Feldman and S. Micali. Optimal algorithms for byzantine agreement. In Proceedings of the 20th ACM Symposium on the Theory of Computing, pages 148–161, 1988.
A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, Advances in Cryptology — CRYPTO’ 86, volume 263 of Lecture Notes in Computer Science, pages 186–199. Springer-Verlag, 1986.
Y. Frankel, P. D. MacKenzie, and M. Yung. Robust efficient distributed RSA-key generation. In Proceedings of the 30th annual ACM Symposium on Theory of Computing, pages 663–672, New York City, 1998.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In U. Maurer, editor, Advances in Cryptology — EUROCRYPT’ 96, volume 1070 of Lecture Notes in Computer Science, pages 354–371. Springer-Verlag, 1996.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure distributed key generation for discrete-log based cryptosystems. In Jacques Stern, editor, Advances in Cryptology — EUROCRYPT’ 99, volume 1592 of Lecture Notes in Computer Science, pages 295–310. Springer-Verlag, 1999.
R. Gennaro, M. Rabin, and T. Rabin. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In 17th ACM Symposium on Principles of Distributed Computing, 1998.
O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th IEEE Annual Symposium on Foundations of Computer Science, pages 174–187, 1986.
A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing or: How to cope with perpetual leakage. In D. Coppersmith, editor, Advances in Cryptology — CRYPTO’ 95, volume 963 of Lecture Notes in Computer Science, pages 339–352. Springer-Verlag, 1995.
M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 2(27):228–234, 1980.
T. P. Pedersen. A threshold cryptosystem without a trusted party. In D. W. Davies, editor, Advances in Cryptology — EUROCRYPT’ 91, volume 547 of Lecture Notes in Computer Science, pages 522–526. Springer-Verlag, 1991.
T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology-CRYPTO’ 91, volume 576 of Lecture Notes in Computer Science, pages 129–140. Springer-Verlag, 1992.
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the 21st annual ACM Symposium on the Theory of Computing, pages 73–85, 1989.
A. Shamir. How to share a secret. Communications of the ACM, 22:612–613, 1979.
V. Shoup and R. Gennaro. Securing threshold cryptosystems against chosen cipher-text attack. In K. Nyberg, editor, Advances in Cryptology-EUROCRYPT’ 98, Lecture Notes in Computer Science, pages 1–16. Springer-Verlag, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abe, M. (1999). Robust Distributed Multiplication without Interaction. In: Wiener, M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_9
Download citation
DOI: https://doi.org/10.1007/3-540-48405-1_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66347-8
Online ISBN: 978-3-540-48405-9
eBook Packages: Springer Book Archive