Skip to main content
Erschienen in: Journal of Cryptology 4/2016

01.10.2016

Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions

verfasst von: Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo

Erschienen in: Journal of Cryptology | Ausgabe 4/2016

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper presents efficient structure-preserving signature schemes based on simple assumptions such as decisional linear. We first give two general frameworks for constructing fully secure signature schemes from weaker building blocks such as variations of one-time signatures and random message secure signatures. They can be seen as refinements of the Even–Goldreich–Micali framework, and preserve many desirable properties of the underlying schemes such as constant signature size and structure preservation. We then instantiate them based on simple (i.e., not q-type) assumptions over symmetric and asymmetric bilinear groups. The resulting schemes are structure-preserving and yield constant-size signatures consisting of 11–14 group elements, which compares favorably to existing schemes whose security relies on q-type assumptions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The optimal TOS proposed in this paper was first presented in [3]. We included it here as it saves one group element in a tag compared to the original construction in [2], and reduces the resulting signature size from 17 in [2] to 14.
 
Literatur
1.
Zurück zum Zitat M. Abe, J. Camenisch, M. Dubovitskaya, R. Nishimaki, Universally composable adaptive oblivious transfer (with access control) from standard assumptions, in DIM’13, Proceedings of the 2013 ACM Workshop on Digital Identity Management, Berlin, Germany (ACM, 2013), pp. 1–12 M. Abe, J. Camenisch, M. Dubovitskaya, R. Nishimaki, Universally composable adaptive oblivious transfer (with access control) from standard assumptions, in DIM’13, Proceedings of the 2013 ACM Workshop on Digital Identity Management, Berlin, Germany (ACM, 2013), pp. 1–12
2.
Zurück zum Zitat M. Abe, M. Chase, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Constant-size structure-preserving signatures generic constructions and simple assumptions, in Advances in Cryptology—ASIACRYPT 2012, volume 7658 of LNCS, ed. by X. Wang, K. Sako (Springer, Berlin, 2012), pp. 4–12, M. Abe, M. Chase, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Constant-size structure-preserving signatures generic constructions and simple assumptions, in Advances in Cryptology—ASIACRYPT 2012, volume 7658 of LNCS, ed. by X. Wang, K. Sako (Springer, Berlin, 2012), pp. 4–12,
3.
Zurück zum Zitat M. Abe, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Tagged one-time signatures: tight security and optimal tag size, in Public-Key Cryptology—PKC 2013, volume 7778 of LNCS, ed. by K. Kurosawa, G. Hanaoka (Springer, Berlin, 2013), pp. 312–331 M. Abe, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Tagged one-time signatures: tight security and optimal tag size, in Public-Key Cryptology—PKC 2013, volume 7778 of LNCS, ed. by K. Kurosawa, G. Hanaoka (Springer, Berlin, 2013), pp. 312–331
4.
Zurück zum Zitat M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Structure-preserving signatures and commitments to group elements. J. Cryptol., (2015). doi:10.1007/s00145-014-9196-7 M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Structure-preserving signatures and commitments to group elements. J. Cryptol., (2015). doi:10.​1007/​s00145-014-9196-7
5.
Zurück zum Zitat M. Abe, J. Groth, K. Haralambiev, M. Ohkubo, Optimal structure-preserving signatures in asymmetric bilinear groups, in Advances in Cryptology—CRYPTO ’11. LNCS (Springer, Berlin, 2011) M. Abe, J. Groth, K. Haralambiev, M. Ohkubo, Optimal structure-preserving signatures in asymmetric bilinear groups, in Advances in Cryptology—CRYPTO ’11. LNCS (Springer, Berlin, 2011)
6.
Zurück zum Zitat M. Abe, J. Groth, M. Ohkubo, Separating short structure preserving signatures from non-interactive assumptions, in Advances in Cryptology—ASIACRYPT 2011, volume 7073 of LNCS, ed. by D. H. Lee, X. Wang (Springer, Berlin, 2011), pp. 628–646 M. Abe, J. Groth, M. Ohkubo, Separating short structure preserving signatures from non-interactive assumptions, in Advances in Cryptology—ASIACRYPT 2011, volume 7073 of LNCS, ed. by D. H. Lee, X. Wang (Springer, Berlin, 2011), pp. 628–646
7.
8.
9.
Zurück zum Zitat M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, H. Shacham, Randomizable proofs and delegatable anonymous credentials, in Advances in Cryptology—CRYPTO 2009, volume 5677 of LNCS, ed. by S. Halevi (Springer, Berlin, 2009), pp. 108–125 M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, H. Shacham, Randomizable proofs and delegatable anonymous credentials, in Advances in Cryptology—CRYPTO 2009, volume 5677 of LNCS, ed. by S. Halevi (Springer, Berlin, 2009), pp. 108–125
10.
Zurück zum Zitat M. Bellare, D. Micciancio, B. Warinschi, Foundations of group signatures: Formal definitions, simplified requirements and a construction based on general assumptions, in Advances in Cryptology—EUROCRYPT 2013, volume 2656 of LNCS, ed. by E. Biham (Springer, Berlin, 2003), pp. 614–629 M. Bellare, D. Micciancio, B. Warinschi, Foundations of group signatures: Formal definitions, simplified requirements and a construction based on general assumptions, in Advances in Cryptology—EUROCRYPT 2013, volume 2656 of LNCS, ed. by E. Biham (Springer, Berlin, 2003), pp. 614–629
11.
Zurück zum Zitat M. Bellare, H. Shi, C. Zhang, Foundations of group signatures: the case of dynamic groups, in Topics in Cryptology—CT-RSA 2005, volume 3376 of LNCS, ed. by A. Menezes (Springer, Berlin, 2005), pp. 136–154. Full version available at IACR e-print 2004/077 M. Bellare, H. Shi, C. Zhang, Foundations of group signatures: the case of dynamic groups, in Topics in Cryptology—CT-RSA 2005, volume 3376 of LNCS, ed. by A. Menezes (Springer, Berlin, 2005), pp. 136–154. Full version available at IACR e-print 2004/077
12.
Zurück zum Zitat M. Bellare, S. Shoup, Two-tier signatures, strongly unforgeable signatures, and Fiat–Shamir without random oracles, in Public-Key Cryptology—PKC 2007, volume 4450 of LNCS, ed. by T. Okamoto, X. Wang (Springer, Berlin, 2007), pp. 201–216 M. Bellare, S. Shoup, Two-tier signatures, strongly unforgeable signatures, and Fiat–Shamir without random oracles, in Public-Key Cryptology—PKC 2007, volume 4450 of LNCS, ed. by T. Okamoto, X. Wang (Springer, Berlin, 2007), pp. 201–216
13.
Zurück zum Zitat D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Advances in Cryptology—CRYPTO 2004, volume 3152 of LNCS, ed. by M. Franklin (Springer, Berlin, 2004), pp. 41–55 D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Advances in Cryptology—CRYPTO 2004, volume 3152 of LNCS, ed. by M. Franklin (Springer, Berlin, 2004), pp. 41–55
14.
Zurück zum Zitat D. Boneh, C. Gentry, B. Lynn, H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in Advances in Cryptology—EUROCRYPT 2003, volume 2656 of LNCS, ed. by E. Biham (Springer, Berlin, 2003), pp. 416–432 D. Boneh, C. Gentry, B. Lynn, H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in Advances in Cryptology—EUROCRYPT 2003, volume 2656 of LNCS, ed. by E. Biham (Springer, Berlin, 2003), pp. 416–432
15.
Zurück zum Zitat J. Camenisch, M. Dubovitskaya, K. Haralambiev, Efficient structure-preserving signature scheme from standard assumptions, in Security and Cryptography for Networks—SCN 2012, volume 7485 of LNCS, ed. by I. Visconti, R. De Prisco (Springer, Berlin, 2012), pp. 76–94 J. Camenisch, M. Dubovitskaya, K. Haralambiev, Efficient structure-preserving signature scheme from standard assumptions, in Security and Cryptography for Networks—SCN 2012, volume 7485 of LNCS, ed. by I. Visconti, R. De Prisco (Springer, Berlin, 2012), pp. 76–94
16.
Zurück zum Zitat J. Cathalo, B. Libert, M. Yung, Group encryption: Non-interactive realization in the standard model, in Advances in Cryptology—ASIACRYPT 2009, volume 5912 of LNCS, ed. by M. Matsui (2009), pp. 179–196 J. Cathalo, B. Libert, M. Yung, Group encryption: Non-interactive realization in the standard model, in Advances in Cryptology—ASIACRYPT 2009, volume 5912 of LNCS, ed. by M. Matsui (2009), pp. 179–196
17.
Zurück zum Zitat M. Chase, M. Kohlweiss, A new hash-and-sign approach and structure-preserving signatures from DLIN, in Security and Cryptography for Networks-SCN 2012, volume 7485 of LNCS, ed. by I. Visconti, R. De Prisco (Springer, Berlin, 2012), pp. 131–148 M. Chase, M. Kohlweiss, A new hash-and-sign approach and structure-preserving signatures from DLIN, in Security and Cryptography for Networks-SCN 2012, volume 7485 of LNCS, ed. by I. Visconti, R. De Prisco (Springer, Berlin, 2012), pp. 131–148
18.
Zurück zum Zitat M. Chase, M. Kohlweiss, A. Lysyanskaya, S. Meiklejohn, Malleable proof systems and applications, in Advances in Cryptology—EUROCRYPT 2012, volume 7237 of LNCS, ed. by D. Pointcheval, T. Johansson (Springer, Berlin, 2012), pp. 281–300 M. Chase, M. Kohlweiss, A. Lysyanskaya, S. Meiklejohn, Malleable proof systems and applications, in Advances in Cryptology—EUROCRYPT 2012, volume 7237 of LNCS, ed. by D. Pointcheval, T. Johansson (Springer, Berlin, 2012), pp. 281–300
19.
Zurück zum Zitat J. Chen, H. W. Lim, S. Ling, H. Wang, H. Wee, Shorter identity-based encryption via asymmetric pairings. Des. Codes Cryptogr., 73(3), 911–947 (2014)MathSciNetCrossRefMATH J. Chen, H. W. Lim, S. Ling, H. Wang, H. Wee, Shorter identity-based encryption via asymmetric pairings. Des. Codes Cryptogr., 73(3), 911–947 (2014)MathSciNetCrossRefMATH
21.
Zurück zum Zitat C. Dwork, M. Naor, An efficient existentially unforgeable signature scheme and its applications. J. Cryptol., 11(3), 187–208 (1998)MathSciNetCrossRefMATH C. Dwork, M. Naor, An efficient existentially unforgeable signature scheme and its applications. J. Cryptol., 11(3), 187–208 (1998)MathSciNetCrossRefMATH
23.
Zurück zum Zitat M. Fischlin, Round-optimal composable blind signatures in the common reference model, in Advances in Cryptology—CRYPTO 2006, volume 4117 of LNCS, ed. by C. Dwork (Springer, Berlin, 2006), pp. 60–77 M. Fischlin, Round-optimal composable blind signatures in the common reference model, in Advances in Cryptology—CRYPTO 2006, volume 4117 of LNCS, ed. by C. Dwork (Springer, Berlin, 2006), pp. 60–77
24.
Zurück zum Zitat G. Fuchsbauer, Commuting signatures and verifiable encryption, in Advances in Cryptology—EUROCRYPT 2011, volume 6632 of LNCS, ed. by K. G. Paterson (Springer, Berlin, 2011), pp. 224–245 G. Fuchsbauer, Commuting signatures and verifiable encryption, in Advances in Cryptology—EUROCRYPT 2011, volume 6632 of LNCS, ed. by K. G. Paterson (Springer, Berlin, 2011), pp. 224–245
25.
Zurück zum Zitat G. Fuchsbauer, D. Pointcheval, Anonymous proxy signatures, in Security and Cryptography for Networks—SCN 2008, volume 5229 of LNCS, ed. by R. Ostrovsky, R. De Prisco, I. Visconti (Springer, Berlin, 2008), pp. 201–217 G. Fuchsbauer, D. Pointcheval, Anonymous proxy signatures, in Security and Cryptography for Networks—SCN 2008, volume 5229 of LNCS, ed. by R. Ostrovsky, R. De Prisco, I. Visconti (Springer, Berlin, 2008), pp. 201–217
26.
Zurück zum Zitat G. Fuchsbauer, D. Pointcheval, D. Vergnaud, Transferable constant-size fair e-cash, in Cryptology and Network Security—CANS 2009, volume 5888 of LNCS, ed. by J.A. Garay, A. Miyaji, A. Otsuka (Springer, Berlin, 2009), pp. 226–247 G. Fuchsbauer, D. Pointcheval, D. Vergnaud, Transferable constant-size fair e-cash, in Cryptology and Network Security—CANS 2009, volume 5888 of LNCS, ed. by J.A. Garay, A. Miyaji, A. Otsuka (Springer, Berlin, 2009), pp. 226–247
27.
Zurück zum Zitat G. Fuchsbauer, D. Vergnaud, Fair blind signatures without random oracles, in Progress in Cryptology—AFRICACRYPT 2010, volume 6055 of LNCS, ed.by D. J. Bernstein, T. Lange (Springer, Berlin, 2010), pp. 16–33 G. Fuchsbauer, D. Vergnaud, Fair blind signatures without random oracles, in Progress in Cryptology—AFRICACRYPT 2010, volume 6055 of LNCS, ed.by D. J. Bernstein, T. Lange (Springer, Berlin, 2010), pp. 16–33
28.
29.
Zurück zum Zitat S. Goldwasser, S. Micali, R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2), 281–308 (1988)MathSciNetCrossRefMATH S. Goldwasser, S. Micali, R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2), 281–308 (1988)MathSciNetCrossRefMATH
30.
Zurück zum Zitat M. Green, S. Hohenberger, Universally composable adaptive oblivious transfer, in Advances in Cryptology—ASIACRYPT 2008, volume 5350 of LNCS, ed. by J. Pieprzyk (Springer, Berlin, 2008), pp. 179–197 M. Green, S. Hohenberger, Universally composable adaptive oblivious transfer, in Advances in Cryptology—ASIACRYPT 2008, volume 5350 of LNCS, ed. by J. Pieprzyk (Springer, Berlin, 2008), pp. 179–197
31.
Zurück zum Zitat M. Green, S. Hohenberger, Practical adaptive oblivious transfer from simple assumptions, in Theory of Cryptography—TCC 2011, volume 6597 of LNCS, ed. by Y. Ishai (Springer, Berlin, 2011), pp. 347–363 M. Green, S. Hohenberger, Practical adaptive oblivious transfer from simple assumptions, in Theory of Cryptography—TCC 2011, volume 6597 of LNCS, ed. by Y. Ishai (Springer, Berlin, 2011), pp. 347–363
32.
Zurück zum Zitat J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in Advances in Cryptology—ASIACRYPT 2006, volume 4284 of LNCS, ed. by X. Lai, K. Chen (Springer, Berlin, 2006), pp. 444–459 J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in Advances in Cryptology—ASIACRYPT 2006, volume 4284 of LNCS, ed. by X. Lai, K. Chen (Springer, Berlin, 2006), pp. 444–459
33.
34.
Zurück zum Zitat D. Hofheinz, T. Jager, Tightly secure signatures and public-key encryption, in Advances in Cryptology—CRYPTO 2012, volume 7417 of LNCS, ed. by R. Naini, R. Canetti (Springer, Berlin, 2012), pp. 590–607 D. Hofheinz, T. Jager, Tightly secure signatures and public-key encryption, in Advances in Cryptology—CRYPTO 2012, volume 7417 of LNCS, ed. by R. Naini, R. Canetti (Springer, Berlin, 2012), pp. 590–607
35.
Zurück zum Zitat A. Kiayias, M. Yung, Group signatures with efficient concurrent join, in Advances in Cryptology—EUROCRYPT 2005, volume 3494 of LNCS, ed. by R. Cramer (Springer, Berlin, 2005), pp. 198–214 A. Kiayias, M. Yung, Group signatures with efficient concurrent join, in Advances in Cryptology—EUROCRYPT 2005, volume 3494 of LNCS, ed. by R. Cramer (Springer, Berlin, 2005), pp. 198–214
36.
Zurück zum Zitat B. Libert, T. Peters, M. Yung, Scalable group signatures with revocation, in Advances in Cryptology—EUROCRYPT 2012, volume 7237 of LNCS, ed. by D. Pointcheval, T. Johansson (Springer,Berlin, 2012), pp. 609–627 B. Libert, T. Peters, M. Yung, Scalable group signatures with revocation, in Advances in Cryptology—EUROCRYPT 2012, volume 7237 of LNCS, ed. by D. Pointcheval, T. Johansson (Springer,Berlin, 2012), pp. 609–627
37.
Zurück zum Zitat Y. Lindell, A simpler construction of CCA2-secure public-key encryption under general assumptions. J. Cryptol., 19(3), 359–377 (2006)MathSciNetCrossRefMATH Y. Lindell, A simpler construction of CCA2-secure public-key encryption under general assumptions. J. Cryptol., 19(3), 359–377 (2006)MathSciNetCrossRefMATH
38.
Zurück zum Zitat M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, in Symposium on Theory of Computing(STOC) 1990, ed. by H. Ortiz (ACM, NY, 1990), pp. 427–437 M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, in Symposium on Theory of Computing(STOC) 1990, ed. by H. Ortiz (ACM, NY, 1990), pp. 427–437
39.
Zurück zum Zitat M. Rückert, D. Schröder, Security of verifiably encrypted signatures and a construction without random oracles, in Pairing-Based Cryptography—Pairing 2009, volume 5671 of LNCS, ed. by H. Shacham, B. Waters (Springer, Berlin, 2009), pp. 17–34 M. Rückert, D. Schröder, Security of verifiably encrypted signatures and a construction without random oracles, in Pairing-Based Cryptography—Pairing 2009, volume 5671 of LNCS, ed. by H. Shacham, B. Waters (Springer, Berlin, 2009), pp. 17–34
40.
Zurück zum Zitat A. Sahai, Non-malleable non-interactive zero-knowledge and chosen-ciphertext security, in Foundations of Computer Science(FOCS) 1999 (IEEE Computer Society, Washington, DC, 1999) pp. 543–553 A. Sahai, Non-malleable non-interactive zero-knowledge and chosen-ciphertext security, in Foundations of Computer Science(FOCS) 1999 (IEEE Computer Society, Washington, DC, 1999) pp. 543–553
41.
Zurück zum Zitat A. De Santis, G. Di Crescenzo, R. Ostrovsky, G. Persiano, A. Sahai. Robust non-interactive zero knowledge. in Advances in Cryptology—CRYPTO 2001, volume 2139 of LNCS, ed. by J. Kilian (Springer, Berlin, 2001), pp. 566–598 A. De Santis, G. Di Crescenzo, R. Ostrovsky, G. Persiano, A. Sahai. Robust non-interactive zero knowledge. in Advances in Cryptology—CRYPTO 2001, volume 2139 of LNCS, ed. by J. Kilian (Springer, Berlin, 2001), pp. 566–598
42.
Zurück zum Zitat A. Shamir, Y. Tauman, Improved online/offline signature schemes, in Advances in Cryptology—CRYPTO 2001, volume 2139 of LNCS, ed. by J. Kilian (Springer, Berlin, 2001), pp. 355–367 A. Shamir, Y. Tauman, Improved online/offline signature schemes, in Advances in Cryptology—CRYPTO 2001, volume 2139 of LNCS, ed. by J. Kilian (Springer, Berlin, 2001), pp. 355–367
43.
Zurück zum Zitat V. Shoup, Lower bounds for discrete logarithms and related problems, in Advances in Cryptology—EUROCRYPT 1997, volume 1233 of LNCS, ed. by W. Fumy (Springer, Berlin, 1997), pp. 256–266 V. Shoup, Lower bounds for discrete logarithms and related problems, in Advances in Cryptology—EUROCRYPT 1997, volume 1233 of LNCS, ed. by W. Fumy (Springer, Berlin, 1997), pp. 256–266
44.
Zurück zum Zitat B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in Advances in Cryptology—CRYPTO 2009, volume 5677 of LNCS, ed. by S. Halevi (Springer, Berlin, 2009), pp. 619–636 B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in Advances in Cryptology—CRYPTO 2009, volume 5677 of LNCS, ed. by S. Halevi (Springer, Berlin, 2009), pp. 619–636
Metadaten
Titel
Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions
verfasst von
Masayuki Abe
Melissa Chase
Bernardo David
Markulf Kohlweiss
Ryo Nishimaki
Miyako Ohkubo
Publikationsdatum
01.10.2016
Verlag
Springer US
Erschienen in
Journal of Cryptology / Ausgabe 4/2016
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-015-9211-7

Weitere Artikel der Ausgabe 4/2016

Journal of Cryptology 4/2016 Zur Ausgabe