Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 4/2020

09-06-2020

Adaptively Secure Non-interactive CCA-Secure Threshold Cryptosystems: Generic Framework and Constructions

Authors: Benoît Libert, Moti Yung

Published in: Journal of Cryptology | Issue 4/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 \le n\) servers need to contribute to the decryption process. A threshold primitive is said robust if no coalition of t malicious servers can prevent remaining honest servers from successfully completing private key operations. Non-interactive schemes, considered the most practical ones, allow servers to contribute to decryption without interactions. So far, most non-interactive threshold cryptosystems were only proved secure against static corruptions. In the adaptive corruption scenario (where the adversary can corrupt servers at any time, based on its complete view), all existing robust threshold encryption schemes that also resist chosen-ciphertext attacks till recently require interaction in the decryption phase. A very specific method (in composite order groups) for getting rid of interaction was recently suggested, leaving the question of more generic frameworks and constructions with better security and, in particular, better flexibility (i.e., compatibility with distributed key generation). This paper advances the state of the art and describes a general construction of adaptively secure robust non-interactive threshold cryptosystems with chosen-ciphertext security. We define the novel notion of all-but-one perfectly sound threshold hash proof systems that can be seen as (threshold) hash proof systems with publicly verifiable and simulation-sound proofs. We show that this notion generically implies threshold cryptosystems combining the aforementioned properties. Then, we provide efficient instantiations under well-studied assumptions in bilinear groups (e.g., in such groups of prime order). These instantiations have a tighter security proof in the single-challenge setting and are indeed compatible with distributed key generation protocols.
next article Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
We assume that tags are non-zero. This can be enforced by having \(\mathsf {Prove}\) and \(\mathsf {Verify}\) output \(\perp \) when \(\mathsf {tag}= 0\).
 
Literature
1.
M. Abdalla, F. Ben Hamouda, D. Pointcheval, Disjunctions for hash proof systems: new constructions and applications, in Eurocrypt ’15, LNCS, vol. 9057 (Springer, 2015), pp. 69–100
2.
M. Abe, Robust distributed multiplication with out interaction, in Crypto’99. LNCS, vol. 1666 (1999), pp. 130–147
3.
M. Abe, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Tagged one-time signatures: tight security and optimal tag size, in K. Kurosawa, G. Hanaoka, editors, PKC 2013 (Springer, 2013)
4.
M. Abe, Y. Cui, H. Imai, E. Kiltz, Efficient hybrid encryption from ID-based encryption. Des. Codes Cryptogr. 54(3), 205–240 (2010)MathSciNetCrossRef
5.
M. Abe, S. Fehr, Adaptively secure feldman VSS and applications to universally-composable threshold cryptography, in Crypto’04. LNCS, vol. 3152 (2004), pp. 317–334
6.
M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Structure-preserving signatures and commitments to group elements, in T. Rabin, editor, Crypto 2010 (Springer, 2010)
7.
J.  Almansa, I. Damgård, J.-B. Nielsen, Simplified threshold RSA with adaptive and proactive security, in Eurocrypt’06. LNCS, vol. 4004 (2006), pp. 593–611
8.
M. Bellare, A. Boldyreva, S. Micali, Public-key encryption in a multi-user setting: security proofs and improvements, Eurocrypt ’00. LNCS, vol. 1807 (Springer, 2000), pp. 259–274
9.
M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in ACM CCS (1993), pp. 62–73
10.
O. Blazy, G. Fuchsbauer, M. Izabachène, A. Jambert, H. Sibert, D. Vergnaud, Batch Groth–Sahai, in Applied Cryptography and Network Security (ACNS’10). LNCS, vol. 6123 (2010), pp. 218–235
11.
D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in Eurocrypt’04. LNCS, vol. 3027 (2004), pp. 223–238
12.
D. Boneh, X. Boyen, S. Halevi, Chosen ciphertext secure public key threshold encryption without random oracles, in CT-RSA’06. LNCS, vol. 3860 (2006), pp. 226–243
13.
D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Crypto’04. LNCS, vol. 3152 (2004), pp. 41–55
14.
D. Boneh, M. Franklin, Identity-based encryption from the weil pairing. SIAM J. Comput. 32(3), 586–615 (2003). Earlier version in Crypto’01
15.
D. Boneh, E.-J. Goh, K. Nissim, Evaluating 2-DNF formulas on ciphertexts, in Theory of cryptography conference—TCC 2005. LNCS, vol. 3378 (Springer, 2005), pp. 325–341
16.
C. Boyd, Digital multisignatures, in H. J. Beker, F. C. Piper (editors) Cryptography and coding (Oxford University Press, 1989), pp. 241–246.
17.
X. Boyen, Q. Mei, B. Waters, Direct chosen ciphertext security from identity-based techniques, in ACM CCS’05 (2005), pp. 320–329
18.
J. Camenisch, N. Chandran, V. Shoup, A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks, in Eurocrypt’09. LNCS, vol. 5479 (2009), pp. 351–368
19.
J. Camenisch, K. Haralambiev, M. Kohlweiss, J. Lapon, V. Naessens, Structure preserving CCA secure encryption and applications, in Asiacrypt 2011. LNCS, vol. 7073 (2011), pp. 89–106
20.
R. Canetti, R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Adaptive security for threshold cryptosystems, in Crypto’99. LNCS, vol. 1666 (1999), pp. 98–115
21.
R. Canetti, S. Goldwasser, An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack, in Eurocrypt’99. LNCS, vol. 1592 (1999), pp. 90–106
22.
R. Canetti, S. Halevi, J. Katz, Chosen-ciphertext security from identity-based encryption, in Eurocrypt’04. LNCS, vol. 3027 (2004), pp. 207–222
23.
R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, T. Rabin, Efficient multi-party computations secure against an adaptive adversary, in Eurocrypt’99. LNCS, vol. 1592 (1999), pp. 311–326
24.
R. Cramer, I. Damgård, Y. Ishai, Share conversion, pseudorandom secret-sharing and applications to secure computation, in TCC’05. LNCS, vol. 3378 (2005), pp. 342–362
25.
R. Cramer, V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in Crypto’98. LNCS, vol. 1462 (1998), pp. 13–25
26.
R. Cramer, V. Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, in Eurocrypt’02. LNCS, vol. 2332 (2002), pp. 45–64
27.
I. Damgård, Towards practical public key systems secure against chosen ciphertext attacks, in Crypto’91. LNCS, vol. 576 (1991), pp. 445–456
28.
Y. Dodis, N. Fazio, Public key trace and revoke scheme secure against adaptive chosen ciphertext attack, in PKC’03. LNCS, vol. 293, 2567 (2003), pp. 100–115
29.
Y. Desmedt, Society and group oriented cryptography: a new concept, in Crypto’87. LNCS, vol. 293 (1987), pp. 120–127
30.
Y. Desmedt, Y. Frankel, Threshold cryptosystems, in Crypto’89. LNCS, vol. 435 (1989), pp. 307–315
31.
Y. Dodis, J. Katz, Chosen-ciphertext security of multiple encryption, in TCC’05. LNCS, vol. 3378 (2005), pp. 188–209
32.
P.-A. Fouque, D. Pointcheval, Threshold cryptosystems secure against chosen-ciphertext attacks, in Asiacrypt’01. LNCS, vol. 2248 (2001), pp. 351–368
33.
Y. Frankel, P. MacKenzie, M. Yung, Adaptively-secure distributed public-key systems, in ESA’99. LNCS, vol. 1643 (1999), pp. 4–27
34.
Y. Frankel, P. MacKenzie, M. Yung, Adaptively-secure optimal-resilience proactive RSA, in Asiacrypt’99. LNCS, vol. 1716 (1999), pp. 180–194
35.
D. Freeman, Converting pairing-based cryptosystems from composite-order groups to prime-order groups, in Eurocrypt’10. LNCS, vol. 6110 (2010), pp. 44–61
36.
J. Groth, R. Ostrovsky, A. Sahai, Perfect non-interactive zero knowledge for NP, in Eurocrypt’06, volume 4004 of Lecture Notes in Computer Science (Springer, 2006), pp. 339–358
37.
J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in Asiacrypt 2006. LNCS, vol. 4284 (2006), pp. 444–459
38.
J. Groth, Fully anonymous group signatures without random oracles, in Asiacrypt 2007. LNCS, vol. 4833 (Springer, 2007), pp. 164–180
39.
J. Groth, A. Sahai, Efficient non-interactive proof systems for bilinear groups, in Eurocrypt’08. LNCS, vol. 4965 (2008), pp. 415–432
40.
J.  Håstad, R. Impagliazzo, L. Levin, M.  Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRef
41.
D. Hofheinz, T. Jager, Tightly secure signatures and public-key encryption, in Crypto ’12. LNCS, vol. 7417 (Springer, 2012), pp. 590–607
42.
D. Hofheinz, E. Kiltz, The group of signed quadratic residues and applications, in Crypto’09. LNCS, vol. 5677 (2009), pp. 637–653
43.
S. Jarecki, A. Lysyanskaya, Adaptively secure threshold cryptography: introducing concurrency, removing erasures, in Eurocrypt’00. LNCS, vol. 1807 (2000), pp. 221–242
44.
C. Jutla, A. Roy, Relatively-sound NIZKs and password-based key-exchange, in PKC 2012. LNCS, vol. 7293 (2012), pp. 485–503
45.
C. Jutla, A. Roy, Shorter quasi-adaptive NIZK proofs for linear subspaces, in Asiacrypt 2013. LNCS, vol. 8269 (2013), pp. 1–20
46.
C. Jutla, A. Roy, Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces, Crypto ’14. LNCS, vol. 8617 (Springer, 2014), pp. 295–312
47.
E. Kachisa, E. Schaefer, M. Scott, Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field, in Pairing. LNCS, vol. 5209 (2008), pp. 126–135
48.
J. Katz, V. Vaikuntanathan, Round-optimal password-based authenticated key exchange, in TCC’11. LNCS, vol. 6597 (2011), pp. 293–310
49.
E. Kiltz, Chosen-ciphertext security from tag-based encryption, in TCC’06. LNCS, vol. 3876 (2006), pp. 581–600
50.
E. Kiltz, K. Pietrzak, M. Stam, M. Yung, A new randomness extraction paradigm for hybrid encryption, in Eurocrypt’09. LNCS, vol. 5479 (2009), pp. 590–609
51.
E. Kiltz, H. Wee, Quasi-adaptive NIZK for linear subspaces revisited, in Eurocrypt 2015. LNCS, vol. 9057 (2015), pp. 101–128
52.
T. Kim, R. Barbulescu, Extended tower number field sieve: a new complexity for the medium prime case, in Crypto 2016. LNCS, vol. 9814 (2016), pp. 543–571
53.
A. Lewko, B. Waters, New techniques for dual system encryption and fully secure HIBE with short ciphertexts, in TCC 2010. LNCS, vol. 5978 (2010), pp. 455–479
54.
B. Libert, T. Peters, M. Joye, M. Yung, Non-malleability from malleability: simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures, in Eurocrypt 2014. LNCS, vol. 8441 (2014), pp. 514–532
55.
B. Libert, T. Peters, C. Qian, Structure-preserving chosen-ciphertext security with shorter verifiable ciphertexts, PKC 2017. LNCS, vol. 10174 (2017), pp. 247–276
56.
B. Libert, M. Yung, Adaptively secure non-interactive threshold cryptosystems, in ICALP 2011. LNCS, vol. 6756 (2011), pp. 588–600
57.
P. MacKenzie, An efficient two-party public key cryptosystem secure against adaptive chosen ciphertext attack, in PKC’03. LNCS, vol. 2567 (2003), pp. 47–61
58.
P. MacKenzie, M. Reiter, K. Yang, Alternatives to non-malleability: definitions, constructions, and applications, in TCC’04. LNCS, vol. 2951 (Springer, 2004), pp. 171–190
59.
T. Malkin, I. Teranishi, Y. Vahlis, M. Yung, Signatures resilient to continual leakage on memory and computation, in TCC’11. LNCS, vol. 6597 (2011), pp. 89–106
60.
M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, in STOC’90 (ACM Press, 1990)
61.
R. Ostrovsky, M. Yung, How to withstand mobile virus attacks, in \(10^{th}\)ACM Symposium on Principles of Distributed Computing (PODC’91) (1991)
62.
T. Rabin, A simplified approach to threshold and proactive RSA, in Crypto’98. LNCS, vol. 1462 (1998), pp. 89–104
63.
C. Rackoff, D. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, in Crypto’91. LNCS, vol. 576 (1991), pp. 433–444
64.
A. Sahai, Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security, in FOCS’99 (1999), pp. 543–553
65.
M. Scott, Authenticated ID-based key exchange and remote log-in with simple token and PIN number. Cryptology ePrint Archive: Report 2002/164
66.
A. Shamir, Identity-based cryptosystems and signature schemes, in Crypto’84. LNCS, vol. 196 (1984), pp. 47–53
67.
V. Shoup, R. Gennaro, Securing threshold cryptosystems against chosen ciphertext attack. J. Cryptol. 15(2), 75–96 (2002). Earlier version in Eurocrypt’98. LNCS, vol. 1403 (1998), pp. 1–16
68.
Z.  Wang, H.  Qian, Z. Li, Adaptively secure threshold signature scheme in the standard model. Informatica 20(4), 591–612 (2009)MathSciNetCrossRef
69.
B. Waters, Efficient identity-based encryption without random oracles, in Eurocrypt’05. LNCS, vol. 3494 (2005)
70.
B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in Crypto’09. LNCS, vol. 5677 (2009), pp. 619–636
71.
H. Wee, Efficient chosen-ciphertext security via extractable hash proofs, in Crypto’10. LNCS, vol. 6223 (2010), pp. 314–332
72.
H. Wee, Threshold and revocation cryptosystems via extractable hash proofs, in Eurocrypt’11. LNCS, vol. 6632 (2011), pp. 589–609
Metadata
Title
Adaptively Secure Non-interactive CCA-Secure Threshold Cryptosystems: Generic Framework and Constructions
Authors
Benoît Libert
Moti Yung
Publication date
09-06-2020
Publisher
Springer US
Published in
Journal of Cryptology / Issue 4/2020
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-020-09350-3

Other articles of this Issue 4/2020

Journal of Cryptology 4/2020 Go to the issue

OriginalPaper

Efficient Verifiable Delay Functions

OriginalPaper

Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors

OriginalPaper

Continuously Non-malleable Codes in the Split-State Model

OriginalPaper

-Secure Multiparty Computation without an Honest Majority and the Best of Both Worlds

OriginalPaper

A Formal Security Analysis of the Signal Messaging Protocol

OriginalPaper

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer

Premium Partner

    Image Credits