Abstract
This paper proposes a simple threshold Public-Key Cryptosystem (PKC) which is secure against adaptive chosen ciphertext attack, under the Decisional Diffie-Hellman (DDH) intractability assumption.
Previously, it was shown how to design non-interactive threshold PKC secure under chosen ciphertext attack, in the random-oracle model and under the DDH intractability assumption [25]. The random-oracle was used both in the proof of security and to eliminate interaction. General completeness results for multi-party computations [6,13] enable in principle converting any single server PKC secure against CCA (e.g., [19,17]) into a threshold one, but the conversions are inefficient and require much interaction among the servers for each ciphertext decrypted. The recent work by Cramer and Shoup [17] on single server PKC secure against adaptive CCA is the starting point for the new proposal.
Supported by DARPA grant DABT63-96-C-0018.
Chapter PDF
Keywords
- Random Oracle
- Choose Ciphertext Attack
- Partial Decryption
- Adaptive Choose Ciphertext Attack
- Faulty Server
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. Beaver, “Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority”, J. Cryptology (1991) 4: 75–122.
D. Beaver and J. Feigenbaum, “Hiding instances in multi-oracle queries”, STACS, 1990.
D. Beaver and S. Haber, “Cryptographic Protocols Provably secure Against Dynamic Adversaries”, Eurocrypt, 1992.
M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, “Relations among notions of security for public-key encryption schemes”, CRYPTO’ 98, 1998, pp. 26–40.
M. Bellare and P. Rogaway, “Optimal Asymmetric Encryption”, Eurocrypt’ 94 (LNCS 950), 92–111, 1995.
M. Ben-Or, S. Goldwasser and A. Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation”, 20th STOC, 1988, pp. 1–10.
M. Blaze, J. Feigenbaum and M. Naor, “A formal treatment of remotely keyed encryption”, Eurocrypt’ 98, 1998, pp. 251–265.
S. Brands, “An efficient on-line electronic cash system based on the representation problem”, CWI TR CS-R9323, 1993.
R. Canetti, “Security and composition of multi-party protocols”, Available at the Theory of Cryptography Library, http://philby.ucsd.edu, 1998.
R. Canetti, U. Feige, O. Goldreich and M. Naor, “Adaptively Secure Computation”, 28th STOC, 1996. Fuller version in MIT-LCS-TR #682, 1996.
R. Canetti and A. Herzberg, “Maintaining security in the presence of transient faults”, CRYPTO’94, 1994.
R. Canetti and S. Goldwasser, “A threshold public-key cryptosystem secure against chosen ciphertext attacks”, Available at the Theory of Cryptography Library, http://philby.ucsd.edu, 1999.
D. Chaum, C. Crepeau, and I. Damgard, “Multi-party Unconditionally Secure Protocols”, 20th STOC, 1998, pp. 11–19.
D. Chaum, E. Everetse and J. van der Graaf, “An improved protocol for demonstrating possession of discrete logarithms and some generalizations”, Eurocrypt’ 87, LNCS 304, 1987, pp. 127–141.
D. Chaum, A. Fiat and M. Naor, “Untraceable electronic cash”, CRYPTO’ 88, LNCS 403, 1988, pp. 319–327.
D. Chaum and T. Pedersen, “Wallet databases with observers”, CRYPTO’ 92, 1992, pp. 89–105.
R. Cramer and V. Shoup, “A paractical public-key cryptosystem provably secure against adaptive chosen ciphertext attack”, CRYPTO’ 98, 1998.
Y. Desmedt and Y. Frankel, “Threshold cryptosystems”, Crypto’ 89 (LNCS 435), 1989, pages 307–315.
D. Dolev, C. Dwork and M. Naor, Non-malleable cryptography, 23rd STOC, 1991.
P. Feldman, “A practical scheme for non-interactive Verifiable Secret Sharing”, 28th FOCS, 1987, pp. 427–437.
A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, CRYPTO’86 (LNCS 263), 186–194, 1986.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin, “Secure Distributed Key Generation for Discrete-Log Based Cryptosystems”, these proceedings.
J. Garay, R. Gennaro, C. Jutla and T. Rabin, “Secure Distributed Storage and Retrieval” Proceedings of 11th International Workshop on Distributed Algorithms (WDAG97) Lecture Notes in Computer Science 1320, pp. 275–289, 1997.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin, “Robust and efficient sharing of RSA functions, CRYPTO’ 96, 1996, pp. 157–172.
R. Gennaro and V. Shoup, “Securing threshold cryptosystems against chosen ciphertext attack”, Eurocrypt’ 98, 1998, pp. 1–16.
O. Goldreich, S. Micali and A. Wigderson, “How to Play any Mental Game”, 19th STOC, 1987, pp. 218–229.
S. Goldwasser, and L. Levin, “Fair Computation of General Functions in Presence of Immoral Majority”, CRYPTO, 1990.
S. Goldwasser and S. Micali, “Probabilistic encryption”, JCSS, Vol. 28, No 2, April 1984, pp. 270–299.
A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, “Proactive Secret Sharing or: How to Cope with Perpetual Leakage”, CRYPTO’ 95, LNCS 963, 1995. pp. 339–352.
F. J. Macwiliams and N. J. A. Sloane, “The Theory of Error Correcting Codes”, North-Holland, 1977.
S. Micali and P. Rogaway, “Secure Computation”, unpublished manuscript, 1992. Preliminary version in CRYPTO 91.
M. Naor, B. Pinkas, and O. Reibgold “Distributed Pseudo-random Functions and KDCs”, these proceedings.
M. Naor and M. Yung, “Public key cryptosystems provably secure against chosen ciphertext attacks”, 22nd STOC, 427–437, 1990.
R. Ostrovsky and M. Yung, “How to withstand mobile virus attacks”. 10th PODC, 1991, pp. 51–59.
T. Pedersen, “A threshold cryptosystem without a trusted party”, Eurocrypt’ 91, 1991, pp. 522–526.
T. Pedersen. Distributed provers with applications to undeniable signatures. Eurocrypt’ 91, 1991.
T. Rabin and M. Ben-Or, “Verifiable Secret Sharing and Multi-party Protocols with Honest Majority”, 21st STOC, 1989, pp. 73–85.
C. Rackoff and D. Simon, “Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack”, CRYPTO’ 91, 1991.
A. Shamir, “How to Share a Secret”, Communications of the ACM, 22:612–613, 1979.
C. Schnorr, “Efficient signature generation by smart cards”, J. Cryptology 4:161–174, 1991.
M. Sudan, “Algorithmic issues in coding theorey”, 17th Conf. on Foundations of Software Technology and Theoretical Computer Science, Kharapur, India, 1997. Available on-line at theory.lcs.mit.edu/∼madhu/
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
Canetti, R., Goldwasser, S. (1999). An Efficient threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack (Extended Abstract). In: Stern, J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_7
Download citation
DOI: https://doi.org/10.1007/3-540-48910-X_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65889-4
Online ISBN: 978-3-540-48910-8
eBook Packages: Springer Book Archive