Abstract
Semantic security against chosen-ciphertext attacks (IND-CCA) is widely believed as the correct security level for public-key encryption scheme. On the other hand, it is often dangerous to give to only one people the power of decryption. Therefore, threshold cryptosystems aimed at distributing the decryption ability. However, only two efficient such schemes have been proposed so far for achieving IND-CCA. Both are El Gamal-like schemes and thus are based on the same intractability assumption, namely the Decisional Diffie-Hellman problem.
In this article we rehabilitate the twin-encryption paradigm proposed by Naor and Yung to present generic conversions from a large family of (threshold) IND-CPA scheme into a (threshold) IND-CCA one in the random oracle model. An efficient instantiation is also proposed, which is based on the Paillier cryptosystem. This new construction provides the first example of threshold cryptosystem secure against chosen-ciphertext attacks based on the factorization problem. Moreover, this construction provides a scheme where the “homomorphic properties” of the original scheme still hold. This is rather cumbersome because homomorphic cryptosystems are known to be malleable and therefore not to be CCA secure. However, we do not build a “homomorphic cryptosystem”, but just keep the homomorphic properties.
Chapter PDF
Similar content being viewed by others
References
O. Baudron, P.A. Fouque, D. Pointcheval, G. Poupard, and J. Stern. Practical Multi-Candidate Election System. In PODC’ 01. ACM, 2001.
O. Baudron, D. Pointcheval, and J. Stern. Extended Notions of Security for Multicast Public Key Cryptosystems. In Proc. of the 27th ICALP, LNCS 1853, pages 499–511. Springer-Verlag, Berlin, 2000.
M. Bellare, A. Boldyreva, and S. Micali. Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements. In Eurocrypt’ 2000, LNCS 1807, pages 259–274. Springer-Verlag, Berlin, 2000.
M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among Notions of Security for Public-Key Encryption Schemes. In Crypto’ 98, LNCS 1462, pages 26–45. Springer-Verlag, Berlin, 1998.
M. Bellare, M. Fischlin, S. Goldwasser, and S. Micali. Identification Protocols Secure against Reset Attacks. In Eurocrypt’ 2001, LNCS 2045, pages 495–511. Springer-Verlag, Berlin, 2001.
M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols. In Proc. of the 1st CCS, pages 62–73. ACM Press, New York, 1993.
M. Bellare and P. Rogaway. Optimal Asymmetric Encryption — How to Encrypt with RSA. In Eurocrypt’ 94, LNCS 950, pages 92–111. Springer-Verlag, Berlin, 1995.
M. Blum, P. Feldman, and S. Micali. Non-Interactive Zero-Knowledge and its Applications. In Proc. of the 20th STOC, pages 103–112. ACM Press, New York, 1988.
M. Blum, P. Feldman, and S. Micali. Proving Security against Chosen-Ciphertext Attacks. In Crypto’ 88, LNCS 403, pages 256–268. Springer-Verlag, Berlin, 1989.
D. Boneh and M. Franklin. Efficient Generation of Shared RSA Keys. In Crypto’ 97, LNCS 1294, pages 425–439. Springer-Verlag, Berlin, 1997.
R. Canetti, I. Damgård, S. Dziembowski, Y. Ishai, and T. Malkin. On Adaptive vs. Non-adaptive Security of Multiparty Protocols. In Eurocrypt’ 2001, LNCS 2045, pages 262–279. Springer-Verlag, Berlin, 2001.
R. Canetti and S. Goldwasser. An Efficient Threshold PKC Secure Against Adaptive CCA. In Eurocrypt’ 99, LNCS 1592, pages 90–106. Springer-Verlag, Berlin, 1999.
D. Catalano, R. Gennaro, N. Howgrave-Graham, and P. Q. Nguyen. Paillier’s Cryptosystem Revisited. In ACM CCS’ 2001, ACM Press, 2001.
R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In Crypto’ 98, LNCS 1462, pages 13–25. Springer-Verlag, Berlin, 1998.
I. Damgård and M. Jurik. A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In PKC’ 2001, LNCS 1992, pages 119–137. Springer-Verlag, Berlin, 2001.
D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. SIAM Journal on Computing, 30(2):391–437, 2000.
T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT-31(4):469–472, July 1985.
A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions of Identification and Signature Problems. In Crypto’ 86, LNCS 263, pages 186–194. Springer-Verlag, Berlin, 1987.
P. A. Fouque, G. Poupard, and J. Stern. Sharing Decryption in the Context of Voting or Lotteries. In Financial Cryptography’ 2000, LNCS. Springer-Verlag, Berlin, 2000.
P. A. Fouque and J. Stern. Fully Distributed Threshold RSA under Standard Assumptions. In Asiacrypt’ 2001, LNCS, Springer-Verlag, Berlin, 2001.
P. A. Fouque and J. Stern. One Round Threshold Discrete-Log Key Generation without Private Channels. In PKC’ 2001, LNCS 1992, pages 300–316. Springer-Verlag, Berlin, 2001.
Y. Frankel, P. Gemmel, Ph. MacKenzie, and M. Yung. Optimal-Resilience Proactive Public-Key Cryptosystems. In Proc. of the 38th FOCS, pages 384–393. IEEE, New York, 1997.
Y. Frankel, P. Gemmell, and M. Yung. Witness Based Cryptographic Program Checking and Robust Function Sharing. In Proc. of the 28th STOC, pages 499–508. ACM Press, New York, 1996.
Y. Frankel, P. MacKenzie, and M. Yung. Robust Efficient Distributed RSA Key Generation. In Proc. of the 30th STOC, pages 663–672. ACM Press, New York, 1998.
E. Fujisaki and T. Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Crypto’ 99, LNCS 1666, pages 537–554. Springer-Verlag, Berlin, 1999.
E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. IEICE Transaction of Fundamentals of Electronic Communications and Computer Science, E83-A(1):24–32, January 2000.
E. Fujisaki, T. Okamoto, D. Pointcheval, and J. Stern. RSA-OAEP is Secure under the RSA Assumption. In Crypto’ 2001, LNCS. Springer-Verlag, Berlin, 2001.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust and Efficient Sharing of RSA Functions. In Crypto’ 96, LNCS 1109, pages 157–172. Springer-Verlag, Berlin, 1996.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust Threshold DSS Signatures. In Eurocrypt’ 96, LNCS 1070, pages 425–438. Springer-Verlag, Berlin, 1996.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In Eurocrypt’ 99, LNCS 1592, pages 295–310. Springer-Verlag, Berlin, 1999.
S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28:270–299, 1984.
C.H. Lim and P.J. Lee. Another Method for Attaining Security Against Adaptively Chosen Ciphertext Attacks. In Crypto’ 93, LNCS 773, pages 287–296. Springer-Verlag, Berlin, 1994.
M. Naor and M. Yung. Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In Proc. of the 22nd STOC, pages 427–437. ACM Press, New York, 1990.
T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In CT — RSA’ 2001, LNCS 2020, pages 159–175. Springer-Verlag, Berlin, 2001.
P. Paillier. Public-Key Cryptosystems Based on Discrete Logarithms Residues. In Eurocrypt’ 99, LNCS 1592, pages 223–238. Springer-Verlag, Berlin, 1999.
P. Paillier and D. Pointcheval. Efficient Public-Key Cryptosystems Provably Secure against Active Adversaries. In Asiacrypt’ 99, LNCS 1716, pages 165–179. Springer-Verlag, Berlin, 1999.
T. Pedersen. A Threshold Cryptosystem without a Trusted Party. In Eurocrypt’ 91, LNCS 547, pages 522–526. Springer-Verlag, Berlin, 1992.
D. Pointcheval. Chosen-Ciphertext Security for any One-Way Cryptosystem. In PKC’ 2000, LNCS 1751, pages 129–146. Springer-Verlag, Berlin, 2000.
D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3):361–396, 2000.
T. Rabin. A Simplified Approach to Threshold and Proactive RSA. In Crypto’ 98, LNCS 1462, pages 89–104. Springer-Verlag, Berlin, 1998.
C. Racko. and D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In Crypto’ 91, LNCS 576, pages 433–444. Springer-Verlag, Berlin, 1992.
A. Sahai. Non-Malleable Non-Interactive Zero-Knowledge and Chosen-Ciphertext Security. In FOCS’ 99, LNCS 2139. IEEE, 1999.
A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung. How to Share a Function Securely. In Proc. of the 26th STOC, pages 522–523. ACM Press, New York, 1994.
C. P. Schnorr. Efficient Identification and Signatures for Smart Cards. In Crypto’ 89, LNCS 435, pages 235–251. Springer-Verlag, Berlin, 1990.
C. P. Schnorr and M. Jakobsson. Security of Signed ElGamal Encryption. In Asiacrypt’ 2000, LNCS 1976, pages 458–469. Springer-Verlag, Berlin, 2000.
A. Shamir. How to Share a Secret. Communications of the ACM, 22:612–613, November 1979.
V. Shoup. Practical Threshold Signatures. In Eurocrypt’ 2000, LNCS 1807, pages 207–220. Springer-Verlag, Berlin, 2000.
V. Shoup and R. Gennaro. Securing Threshold Cryptosystems against Chosen Ciphertext Attack. In Eurocrypt’ 98, LNCS 1403, pages 1–16. Springer-Verlag, Berlin, 1998.
Y. Tsiounis and M. Yung. On the Security of El Gamal based Encryption. In PKC’ 98, LNCS. Springer-Verlag, Berlin, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fouque, PA., Pointcheval, D. (2001). Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks. In: Boyd, C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45682-1_21
Download citation
DOI: https://doi.org/10.1007/3-540-45682-1_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42987-6
Online ISBN: 978-3-540-45682-7
eBook Packages: Springer Book Archive