Article

Adaptively secure forward-secure non-interactive threshold cryptosystems

Authors:

Benoît Libert,

Moti YungAuthors Info & Claims

Inscrypt'11: Proceedings of the 7th international conference on Information Security and Cryptology

Pages 1 - 21

https://doi.org/10.1007/978-3-642-34704-7_1

Published: 30 November 2011 Publication History

Abstract

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum of at least (d≤n) servers needs to act upon a message to produce the result (decrypted value or signature), while corrupting less than d servers maintains the scheme's security. For about two decades, extensive study was dedicated to this subject, which created a number of notable results. So far, most practical threshold signatures, where servers act non-interactively, were analyzed in the limited static corruption model (where the adversary chooses which servers will be corrupted at the system's initialization stage). Existing threshold encryption schemes that withstand the strongest combination of adaptive malicious corruptions (allowing the adversary to corrupt servers at any time based on its complete view), and chosen-ciphertext attacks (CCA) all require interaction (in the non-idealized model) and attempts to remedy this problem resulted only in relaxed schemes. The same is true for threshold signatures secure under chosen-message attacks (CMA).

It was open (for about 10 years) whether there are non-interactive threshold schemes providing the highest security (namely, CCA-secure encryption and CMA-secure signature) with scalable shares (i.e., as short as the original key) and adaptive security. This paper first surveys our ICALP 2011 work which answers this question affirmatively by presenting such efficient decryption and signature schemes within a unified algebraic framework. The paper then describes how to design on top of the surveyed system the first "forward-secure non-interactive threshold cryptosystem with adaptive security.

References

[1]

Abdalla, M., Miner, S. K., Namprempre, C.: Forward-Secure Threshold Signature Schemes. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 441-456. Springer, Heidelberg (2001)

[2]

Abdalla, M., Reyzin, L.: A New Forward-Secure Digital Signature Scheme. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 116-129. Springer, Heidelberg (2000)

[3]

Abe, M.: Robust Distributed Multiplication without Interaction. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 130-147. Springer, Heidelberg (1999)

[4]

Abe, M., Fehr, S.: Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 317-334. Springer, Heidelberg (2004)

[5]

Anderson, R.: Two Remarks on Public Key Cryptology. Invited lecture. In: ACM Conference on Computer and Communications Security (1997)

[6]

Almansa, J. F., Damgård, I., Nielsen, J. B.: Simplified Threshold RSA with Adaptive and Proactive Security. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 593-611. Springer, Heidelberg (2006)

[7]

Bellare, M., Miner, S.: A Forward-Secure Digital Signature Scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 431-448. Springer, Heidelberg (1999)

[8]

Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS (1993)

[9]

Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J. L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223-238. Springer, Heidelberg (2004)

[10]

Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical Identity Based Encryption with Constant Size Ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440-456. Springer, Heidelberg (2005)

[11]

Boneh, D., Boyen, X., Halevi, S.: Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 226-243. Springer, Heidelberg (2006)

[12]

Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. SIAM J. of Computing 32(3), 586-615 (2003); Earlier version in Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213-229. Springer, Heidelberg (2001)

[13]

Boneh, D., Franklin, M.: Efficient Generation of Shared RSA Keys. In: Kaliski Jr., B. S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 425-439. Springer, Heidelberg (1997)

[14]

Boyd, C.: Digital Multisignatures. In: Beker, H. J., Piper, F.C. (eds.) Cryptography and Coding, pp. 241-246. Oxford University Press (1989)

[15]

Boyen, X., Mei, Q., Waters, B.: Direct Chosen Ciphertext Security from Identity-Based Techniques. In: ACM CCS 2005 (2005)

[16]

Boyen, X., Shacham, H., Shen, E., Waters, B.: Forward-Secure Signatures with Untrusted Update. In: ACM CCS 2006. ACM Press (2006)

[17]

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM 51(4), 557-594 (2004); Earlier version in STOC 1998 (1998)

[18]

Canetti, R., Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Adaptive Security for Threshold Cryptosystems. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 98-116. Springer, Heidelberg (1999)

[19]

Canetti, R., Goldwasser, S.: An Efficient Threshold Public Key Cryptosystem Secure against Adaptive Chosen Ciphertext Attack. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 90-106. Springer, Heidelberg (1999)

[20]

Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13-25. Springer, Heidelberg (1998)

[21]

Canetti, R., Halevi, S., Katz, J.: A Forward-Secure Public-Key Encryption Scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255-271. Springer, Heidelberg (2003)

[22]

Canetti, R., Halevi, S., Katz, J.: Chosen-Ciphertext Security from Identity-Based Encryption. In: Cachin, C., Camenisch, J. L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207-222. Springer, Heidelberg (2004)

[23]

Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient Multiparty Computations Secure against an Adaptive Adversary. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 311.326. Springer, Heidelberg (1999)

[24]

Daza, V., Herranz, J., Morillo, P., Ràfols, C.: CCA2-Secure Threshold Broadcast Encryption with Shorter Ciphertexts. In: Susilo, W., Liu, J. K., Mu, Y. (eds.) ProvSec 2007. LNCS, vol. 4784, pp. 35.50. Springer, Heidelberg (2007)

[25]

Delerablée, C., Pointcheval, D.: Dynamic Threshold Public-Key Encryption. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 317-334. Springer, Heidelberg (2008)

[26]

Dent, A.-W.: A Note On Game-Hopping Proofs. Cryptology ePrint Archive: Report 2006/260

[27]

Desmedt, Y.: Society and Group Oriented Cryptography: A New Concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120-127. Springer, Heidelberg (1988)

[28]

Desmedt, Y., Frankel, Y.: Threshold Cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307-315. Springer, Heidelberg (1990)

[29]

Dodis, Y., Katz, J.: Chosen-Ciphertext Security of Multiple Encryption. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 188-209. Springer, Heidelberg (2005)

[30]

El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In: Blakely, G. R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10-18. Springer, Heidelberg (1985)

[31]

Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Comput. 17(2), 281-308 (1988)

[32]

Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295-310. Springer, Heidelberg (1999)

[33]

Fouque, P.-A., Pointcheval, D.: Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 351-368. Springer, Heidelberg (2001)

[34]

Frankel, Y., MacKenzie, P., Yung, M.: Adaptively-Secure Distributed Public-Key Systems. In: Nešetřil, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 4-27. Springer, Heidelberg (1999)

[35]

Frankel, Y., MacKenzie, P., Yung, M.: Adaptively-Secure Optimal-Resilience Proactive RSA. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 180-195. Springer, Heidelberg (1999)

[36]

Itkis, G., Reyzin, L.: Forward-Secure Signatures with Optimal Signing and Verifying. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 332-354. Springer, Heidelberg (2001)

[37]

Jarecki, S., Lysyanskaya, A.: Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures (Extended Abstract). In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 221-242. Springer, Heidelberg (2000)

[38]

Katz, J.: A Forward-Secure Public-Key Encryption Scheme. Cryptology ePrint Archive: Report 2002/060 (2002)

[39]

Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581-600. Springer, Heidelberg (2006)

[40]

Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 62-91. Springer, Heidelberg (2010)

[41]

Lewko, A., Waters, B.: New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 455-479. Springer, Heidelberg (2010)

[42]

Libert, B., Yung, M.: Adaptively Secure Non-Interactive Threshold Cryptosystems. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 588-600. Springer, Heidelberg (2011)

[43]

Libert, B., Yung, M.: Non-interactive CCA-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 75-93. Springer, Heidelberg (2012)

[44]

Lysyanskaya, A., Peikert, C.: Adaptive Security in the Threshold Setting: From Cryptosystems to Signature Schemes. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 331-350. Springer, Heidelberg (2001)

[45]

MacKenzie, P.: An Efficient Two-Party Public Key Cryptosystem Secure against Adaptive Chosen Ciphertext Attack. In: Desmedt, Y. G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 47-61. Springer, Heidelberg (2003)

[46]

Malkin, T., Micciancio, D., Miner, S. K.: Efficient Generic Forward-Secure Signatures with an Unbounded Number of Time Periods. In: Knudsen, L. R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 400-417. Springer, Heidelberg (2002)

[47]

Ostrovsky, R., Yung, M.: How to Withstand Mobile Virus Attacks. In: 10th ACM Symp. on Principles of Distributed Computing, PODC 1991 (1991)

[48]

Qin, B., Wu, Q., Zhang, L., Domingo-Ferrer, J.: Threshold Public-Key Encryption with Adaptive Security and Short Ciphertexts. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 62-76. Springer, Heidelberg (2010)

[49]

Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely, G. R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47-53. Springer, Heidelberg (1985)

[50]

Shoup, V., Gennaro, R.: Securing Threshold Cryptosystems against Chosen Ciphertext Attack. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1-16. Springer, Heidelberg (1998)

[51]

Shoup, V.: Practical Threshold Signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 207-220. Springer, Heidelberg (2000)

[52]

Waters, B.: Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619-636. Springer, Heidelberg (2009)

Cited By

Ebina MMita JShikata JWatanabe YEmura KWang Y(2021)Efficient Threshold Public Key Encryption from the Computational Bilinear Diffie-Hellman AssumptionProceedings of the 8th ACM on ASIA Public-Key Cryptography Workshop10.1145/3457338.3458296(23-32)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3457338.3458296
Damgård IJakobsen TNielsen JPagter J(2013)Secure Key Management in the CloudProceedings of the 14th IMA International Conference on Cryptography and Coding - Volume 830810.1007/978-3-642-45239-0_16(270-289)Online publication date: 17-Dec-2013
https://dl.acm.org/doi/10.1007/978-3-642-45239-0_16

Adaptively secure forward-secure non-interactive threshold cryptosystems

Recommendations

Adaptively secure non-interactive threshold cryptosystems
ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum ...
Adaptively secure non-interactive threshold cryptosystems

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum ...
Adaptively Secure Non-interactive CCA-Secure Threshold Cryptosystems: Generic Framework and Constructions
Abstract
In threshold cryptography, private keys are divided into n shares, each one of which is given to a different server in order to avoid single points of failure. In the case of threshold public-key encryption, at least $t \leq n$ servers need to contribute ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Inscrypt'11: Proceedings of the 7th international conference on Information Security and Cryptology

November 2011

392 pages

ISBN:9783642347030

Editors:
Chuan-Kun Wu
Chinese Academy of Sciences, Institute of Information Engineering, Beijing, China
,
Moti Yung
Computer Science Department, Google Inc. and Columbia University, S.W. Mudd Building, New York, China
,
Dongdai Lin
Chinese Academy of Sciences, Institute of Information Engineering, Beijing, China

Sponsors

State Key Laboratory of Information Security: State Key Laboratory of Information Security
Chinese Academy of Sciences
Chinese Association for Cryptologic Research: Chinese Association for Cryptologic Research

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 November 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ebina MMita JShikata JWatanabe YEmura KWang Y(2021)Efficient Threshold Public Key Encryption from the Computational Bilinear Diffie-Hellman AssumptionProceedings of the 8th ACM on ASIA Public-Key Cryptography Workshop10.1145/3457338.3458296(23-32)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3457338.3458296
Damgård IJakobsen TNielsen JPagter J(2013)Secure Key Management in the CloudProceedings of the 14th IMA International Conference on Cryptography and Coding - Volume 830810.1007/978-3-642-45239-0_16(270-289)Online publication date: 17-Dec-2013
https://dl.acm.org/doi/10.1007/978-3-642-45239-0_16

View Options

View options

Media

Figures

Other

Tables

View Table of Contents