nach oben

Journal of Cryptology

Erschienen in:

01.10.2016

Unconditionally Anonymous Ring and Mesh Signatures

verfasst von: Xavier Boyen

Erschienen in: Journal of Cryptology | Ausgabe 4/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We generalize the ring signature primitive into the more general notion of mesh signature. Ring signatures are anonymous signatures made by someone who wishes to hide in the anonymity of a larger crowd. All that the signer needs to assemble such a virtual crowd is her own private key and the public keys of the other members. The crowd composition is all that the verifier will be able to see. In a sense, a ring signature expresses an anonymous endorsement of a message by a disjunction of signers. Mesh signatures generalize this notion by allowing the combination of “atomic” (i.e., regular) signatures, by one or multiple signers from an arbitrary larger crowd, into virtually any monotone “endorsement formula” with much more expressive power than a simple disjunction. The verifier sees only that the endorsement is valid for the stated formula, not how the formula is satisfied. As a special case, mesh signatures extend the ring signature functionality to certificate chains. This is useful when the anonymity-seeking signer wishes to hide in a crowd comprising uncooperative people who do not even have a published signature verification key on record. We give an efficient linear-size construction based on bilinear maps in the common random string model. Our mesh signatures achieve everlasting perfect anonymity—an imperative for the archetypical whistle-blowing use case of ring signatures—and, as a special case, yield the first unconditionally anonymous ring signatures without random oracles or trusted setup authorities. Non-repudiation is achieved from a mild extension of the SDH assumption, named Poly-SDH, which we introduce and justify meticulously.

Vorheriger Artikel Key Recovery Attacks on Iterated Even–Mansour Encryption Schemes

Nächster Artikel Bug Attacks

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

Recall that, in general, we require \({\mathbb {G}} \simeq \hat{\mathbb {G}}\) with an efficiently computable isomorphism \(\psi : \hat{\mathbb {G}} \rightarrow {\mathbb {G}}\). Assuming that the reverse isomorphism \(\phi ^{-1}\) is also efficiently computable only increases the power given to the adversary, thus making the attack easier. At the extreme, assuming \({\mathbb {G}} = \hat{\mathbb {G}}\) makes the attack even easier because it allows the adversary not only to move elements back and forth between the isomorphic groups, but also to mix them within the same algebraic expressions, which otherwise would not be allowed in the generic-group model. As noted earlier, the three cases exist in actual realizations of bilinear groups. For this proof, we place ourselves in the case where \({\mathbb {G}} \!=\! \hat{\mathbb {G}}\) in order to show the soundness of our hardness assumption in the most adversary-friendly setting, which will imply the weaker results. (This also helps to simplify the notation, by (temporarily) dropping all “hats” from the expressions.)

The facility to use a prescribed value for \(t_i\) in clauses that are “false” is to give the appearance that such clauses are constructed from Boneh–Boyen atomic signatures with given \(t_i\), as if they were “true.” Without this provision, should a clause have the same \(t_i\) as that of a published signature (e.g., a certificate), it would be exposed as “true.”

We note that with the \(B_i\) removed from the public keys, the ring scheme becomes syntactically very close to the ring signature scheme of [21]. If one temporarily ignores the generalization to the full mesh signature model, one way of looking at the ring signature scheme of Sect. 4 is a provably secure version of [21] from a provably sound hardness assumption (in the sense of being provably hard in the generic-group model).

The encodings f( h), etc., of group elements can be thought of providing unique but intrinsically meaningless “handles” for manipulating “opaque” group elements. The handles can be assigned at random, or sequentially in the order of queries, as long as the handles remain independent of any arithmetic representation of the group elements.

There remains the possibility that the signer could reveal the ephemerals voluntarily to revoke her own anonymity, but this falls outside of the purview of Theorem 6: The same outcome can be achieved generically in all ring signatures. To do so, the signer would append to the message being ring-signed, a one-time signature verification key, an encrypted signature of the same under her public key, and a signature of a hash of the decryption key under the one-time key; she could then provably de-anonymize herself by revealing the decryption key.

Notice that, unlike the user keys which have a lot of internal structure (exhibited by the many obvious discrete log relations), the various components of the key “in the sky” are independently distributed and so a signature that will verify under one triple \(({ \hat{A}_{0,k_1}, \hat{B}_{0,k_1}, \hat{B}_{0,k_1}})\) will not verify under another \(({ \hat{A}_{0,k_2}, \hat{B}_{0,k_2}, \hat{B}_{0,k_2}})\). What we need is a signature that will verify for the particular combination of such triples given by the coefficients of \(\pi _0\).

It can also be shown that for \({\tilde{\Upsilon }} = \Upsilon \vee L_0\), the algorithm of Sect. 5.1 always gives \(\pi _0 = Z_0\), and so we have \(y_{0,k} = 0\) for \(k \ne 0\). It follows that the public key “in the sky” only needs one triple \(({ \hat{A}_{0,0}, \hat{B}_{0,0}, \hat{B}_{0,0}})\) instead of \(\lambda + 1 \ge \vartheta + 1\) of them. We omit this optimization from the present proof to avoid further complicating the argument, but since it greatly shortens the CRS we explicitly recommend its use in Sect. 5.5.

M. Abe, M. Ohkubo, K. Suzuki, \(1\) signatures from a variety of keys, in Proceedings of AsiaCrypt 2002. LNCS, vol. 2501 (Springer, 2002), pp. 415–432

G. Ateniese, J. Camenisch, S. Hohenberger, B. de Medeiros, Practical group signatures without random oracles. Cryptology ePrint Archive, Report 2005/385 (2005). http://eprint.iacr.org/

M.H. Au, J.K. Liu, T.H. Yuen, D.S. Wong, ID-based ring signature scheme secure in the standard model, in Proceedings of IWSEC 2006. LNCS, vol. 4266 (2006), pp. 1–16

A. Bender, J. Katz, R. Morselli, Ring signatures: stronger definitions, and constructions without random oracles. J. Cryptol. 22(1):114–138 (2009)

D. Boneh, X. Boyen, Short signatures without random oracles, in Advances in Cryptology—EUROCRYPT 2004. LNCS, vol. 3027 (Springer, 2004), pp. 56–73

D. Boneh, X. Boyen, Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2):149–177 (2008)

D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Advances in Cryptology—CRYPTO 2004. LNCS, vol. 3152 (Springer, 2004), pp. 41–55

D. Boneh, C. Gentry, B. Lynn, H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in Advances in Cryptology—EUROCRYPT 2003. LNCS, vol. 2656 (Springer, 2003), pp. 416–432

D. Boneh, E.-J. Goh, K. Nissim, Evaluating 2-DNF formulas on ciphertexts, in Proceedings of TCC 2005, Lecture Notes in Computer Science (Springer, 2005)

10.

X. Boyen, Mesh signatures: how to leak a secret with unwitting and unwilling participants, in Advances in Cryptology—EUROCRYPT 2007. LNCS, vol. 4515 (Springer-Verlag, 2007), pp. 210–227

11.

X. Boyen, B. Waters, Full-domain subgroup hiding and constant-size group signatures, in Public Key Cryptography—PKC 2007. LNCS, vol. 4450 (Springer, 2007), pp. 1–15

12.

E. Bresson, J. Stern, M. Szydlo, Threshold ring signatures and applications to ad-hoc groups, in Advances in Cryptology—CRYPTO 2002. LNCS, vol. 2442 (2002), pp. 465–480

13.

J. Camenisch, A. Lysyanskaya, Signature schemes with efficient protocols, in Proceedings of SCN 2002. LNCS (Springer, 2002)

14.

J. Camenisch, A. Lysyanskaya, Signature schemes and anonymous credentials from bilinear maps, in Advances in Cryptology—CRYPTO 2004. LNCS, vol. 3152 (Springer, 2004)

15.

N. Chandran, J. Groth, A. Sahai, Ring signatures of sub-linear size without random oracles, in Proceedings of ICALP 2007, vol. 4596 (2007), pp. 423–443.

16.

M. Chase, A. Lysyanskaya, Signatures of knowledge, in Advances in Cryptology—CRYPTO 2006. LNCS, vol. 4117 (Springer, 2006)

17.

D. Chaum, E. van Heyst, Group signatures, in Advances in Cryptology—EUROCRYPT 1991. LNCS, vol. 547 (Springer, 1991), pp. 257–265

18.

J.H. Cheon, Security analysis of the strong Diffie–Hellman problem, in Advances in Cryptology—EUROCRYPT 2006. LNCS, vo. 4004 (Springer, 2006), pp. 1–13

19.

S.S.M. Chow, L.C.K. Hui, S.-M. Yiu. Identity based threshold ring signature, in Proceedings of ICISC 2004. LNCS, vol. 3506 (2004), pp. 218–232

20.

S.S.M. Chow, R.W.C. Lui, L.C.K. Hui, S.-M. Yiu, Identity based ring signature: why, how and what next, in Proceedings of EuroPKI 2005. LNCS, vol. 3545 (2005), pp. 144–161

21.

S.S.M. Chow, V.K.-W. Wei, J.K. Liu, T.H. Yuen, Ring signatures without random oracles, in Proceedings of AsiaCCS 2006 (ACM Press, 2006), pp. 297–302

22.

S.S.M. Chow, S.-M. Yiu, L.C.K. Hui, Efficient identity based ring signature, in Proceedings of ACNS 2005. LNCS, vol. 3531 (2005) pp. 499–512

23.

R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in Advances in Cryptology—CRYPTO 1994. LNCS, vol. 839 (Springer, 1994), pp. 174–187

24.

Y. Dodis, A. Kiayias, A. Nicolosi, V. Shoup, Anonymous identification in ad hoc groups, in Advances in Cryptology—EUROCRYPT 2004. LNCS, vol. 3027 (Springer, 2004), pp. 609–626.

25.

C. Dwork, M. Naor, Zaps and their applications. SIAM J. Comput. 36(6):1513–1543 (2007)

26.

C. Dwork, M. Naor, A. Sahai, Concurrent zero-knowledge or the timing model for designing concurrent protocols. J. ACM 51(6):851–898 (2004)

27.

A.L. Ferrara, M. Green, S. Hohenberger, M.O. Pedersen, Practical short signature batch verification. Cryptology ePrint Archive, Report 2008/015 (2008). http://eprint.iacr.org/

28.

S.D. Galbraith, K.G. Paterson, N.P. Smart, Pairings for cryptographers. Cryptology ePrint Archive, Report 2006/165 (2006). http://eprint.iacr.org/

29.

J. Groth, Fully anonymous group signatures without random oracles, in Proceedings of ASIACRYPT 2007. LNCS, vol. 4833 (2007), pp. 164–180

30.

J. Groth, R. Ostrovsky, A. Sahai, Non-interactive Zaps and new techniques for NIZK, in Advances in Cryptology—CRYPTO 2006. LNCS (Springer, 2006)

31.

J. Herranz, G. Sáez, Forking lemmas for ring signature schemes, in Proceedings of IndoCrypt 2003. LNCS, vol. 2904 (Springer, 2003), pp. 266–279

32.

J. Herranz, G. Sáez, New distributed ring signatures for general families of signing subsets. Cryptology ePrint Archive, Report 2004/377 (2004). http://eprint.iacr.org/

33.

A. Joux, K. Nguyen, Separating decision Diffie–Hellman from computational Diffie–Hellman in cryptographic groups. J. Cryptol., 16(4) (2003)

34.

M. Karchmer, A. Wigderson, On span programs, in Annual Conference on Structure in Complexity Theory (1993)

35.

V. Miller, The Weil pairing, and its efficient calculation. J. Cryptol. 17(4) (2004)

36.

M. Naor, Deniable ring authentication, in Advances in Cryptology—CRYPTO 2002. LNCS, vol. 2442 (Springer, 2002), pp. 481–498

37.

R. Rivest, A. Shamir, Y. Tauman, How to leak a secret, in Proceedings of AsiaCrypt 2001. LNCS, vol. 2248 (Springer, 2001), pp. 552–565

38.

H. Shacham, B. Waters, Efficient ring signatures without random oracles, in Public Key Cryptography—PKC 2007. LNCS, vol. 4450 (Springer, 2007)

39.

V. Shoup, Lower bounds for discrete logarithms and related problems, in Advances in Cryptology—EUROCRYPT 1997. LNCS, vol. 1233 (Springer, 1997)

40.

M. van Dijk, A linear construction of secret sharing schemes. Des. Codes Cryptogr. 12(2):161–201 (1997)

41.

B. Waters, Efficient identity-based encryption without random oracles, in Advances in Cryptology—EUROCRYPT 2005. LNCS, vol. 3494 (Springer, 2005)

42.

V.K. Wei, T.H. Yuen, (Hierarchical identity-based) threshold ring signatures. Cryptology ePrint Archive, Report 2006/193 (2006). http://eprint.iacr.org/

Titel: Unconditionally Anonymous Ring and Mesh Signatures
verfasst von: Xavier Boyen
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-9208-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2016

New Second-Preimage Attacks on Hash Functions

Key Recovery Attacks on Iterated Even–Mansour Encryption Schemes

Bug Attacks

The -curve Construction for Endomorphism-Accelerated Elliptic Curves

Cryptanalysis of Full RIPEMD-128

Toward a Game Theoretic View of Secure Computation