Short accountable ring signatures based on DDH. (English) Zbl 1499.94054

Bootle, Jonathan; Cerulli, Andrea; Chaidos, Pyrros; Ghadafi, Essam; Groth, Jens; Petit, Christophe

Pernul, Günther (ed.) et al., Computer security – ESORICS 2015. 20th European symposium on research in computer security, Vienna, Austria, September 21–25, 2015. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 9326, 243-265 (2015).

Summary: Ring signatures and group signatures are prominent cryptographic primitives offering a combination of privacy and authentication. They enable individual users to anonymously sign messages on behalf of a group of users. In ring signatures, the group, i.e. the ring, is chosen in an ad hoc manner by the signer. In group signatures, group membership is controlled by a group manager. Group signatures additionally enforce accountability by providing the group manager with a secret tracing key that can be used to identify the otherwise anonymous signer when needed. Accountable ring signatures, introduced by S. Xu and M. Yung [“Accountable ring signatures: a smart card approach”, in: Smart card research and advanced applications VI. Boston, MA: Springer. 271–286 (2004; https://doi.org/10.1007/1-4020-8147-2_18)], bridge the gap between the two notions. They provide maximal flexibility in choosing the ring, and at the same time maintain accountability by supporting a designated opener that can identify signers when needed.
We revisit accountable ring signatures and offer a formal security model for the primitive. Our model offers strong security definitions incorporating protection against maliciously chosen keys and at the same time flexibility both in the choice of the ring and the opener. We give a generic construction using standard tools. We give a highly efficient instantiation of our generic construction in the random oracle model by meticulously combining Camenisch’s group signature scheme [J. Camenisch, “Efficient and generalized group signatures”, Lect. Notes Comput. Sci. 1233, 465–479 (1997; https://doi.org/10.1007/3-540-69053-0_32)] with a generalization of the one-out-of-many proofs of knowledge by J. Groth and M. Kohlweiss [ibid. 9057, 253–280 (2015; Zbl 1371.94639)]. Our instantiation yields signatures of logarithmic size (in the size of the ring) while relying solely on the well-studied decisional Diffie-Hellman assumption. In the process, we offer a number of optimizations for the recent Groth and Kohlweiss one-out-of-many proofs, which may be useful for other applications.
Accountable ring signatures imply traditional ring and group signatures. We therefore also obtain highly efficient instantiations of those primitives with signatures shorter than all existing ring signatures as well as existing group signatures relying on standard assumptions.
For the entire collection see [Zbl 1492.68028].

MSC:

94A62	Authentication, digital signatures and secret sharing
94A60	Cryptography

Keywords:

accountable ring signatures; group signatures; one-out-of-many zero-knowledge proofs

Citations:

Zbl 1371.94639

References:

[1]	Ateniese, G., Camenisch, J., Hohenberger, S., de Medeiros, B.: Practical group signatures without random oracles. Cryptology ePrint Archive, Report 2005/385 (2005). http://eprint.iacr.org/
[2]	Ateniese, G.; Camenisch, JL; Joye, M.; Tsudik, G.; Bellare, M., A practical and provably secure coalition-resistant group signature scheme, Advances in Cryptology - CRYPTO 2000, 255-270, 2000, Heidelberg: Springer, Heidelberg · Zbl 0995.94544 · doi:10.1007/3-540-44598-6_16
[3]	Boneh, D.; Boyen, X.; Shacham, H.; Franklin, M., Short group signatures, Advances in Cryptology - CRYPTO 2004, 41-55, 2004, Heidelberg: Springer, Heidelberg · Zbl 1104.94044 · doi:10.1007/978-3-540-28628-8_3
[4]	Belenkiy, M.; Chase, M.; Kohlweiss, M.; Lysyanskaya, A.; Canetti, R., P-signatures and noninteractive anonymous credentials, Theory of Cryptography, 356-374, 2008, Heidelberg: Springer, Heidelberg · Zbl 1162.94338 · doi:10.1007/978-3-540-78524-8_20
[5]	Bender, A.; Katz, J.; Morselli, R., Ring signatures: stronger definitions, and constructions without random oracles, J. Cryptology, 22, 1, 114, 2009 · Zbl 1163.94431 · doi:10.1007/s00145-007-9011-9
[6]	Bellare, M.; Micciancio, D.; Warinschi, B.; Biham, E., Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions, Advances in Cryptology - EUROCRPYT 2003, 2003, Heidelberg: Springer, Heidelberg · Zbl 1038.94552
[7]	Bellare, M.; Shi, H.; Zhang, C.; Menezes, A., Foundations of group signatures: the case of dynamic groups, Topics in Cryptology - CT-RSA 2005, 136-153, 2005, Heidelberg: Springer, Heidelberg · Zbl 1079.94013 · doi:10.1007/978-3-540-30574-3_11
[8]	Boyen, X.; Waters, B.; Okamoto, T.; Wang, X., Full-domain subgroup hiding and constant-size group signatures, Public Key Cryptography - PKC 2007, 1-15, 2007, Heidelberg: Springer, Heidelberg · Zbl 1127.94020 · doi:10.1007/978-3-540-71677-8_1
[9]	Camenisch, JL; Fumy, W., Efficient and generalized group signatures, Advances in Cryptology - EUROCRYPT ’97, 465-479, 1997, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-69053-0_32
[10]	Camenisch, JL; Groth, J.; Blundo, C.; Cimato, S., Group signatures: better efficiency and new theoretical aspects, Security in Communication Networks, 120-133, 2005, Heidelberg: Springer, Heidelberg · Zbl 1116.94310 · doi:10.1007/978-3-540-30598-9_9
[11]	Camenisch, J.; Kohlweiss, M.; Soriente, C.; Jarecki, S.; Tsudik, G., An accumulator based on bilinear maps and efficient revocation for anonymous credentials, Public Key Cryptography - PKC 2009, 481-500, 2009, Heidelberg: Springer, Heidelberg · Zbl 1227.94074 · doi:10.1007/978-3-642-00468-1_27
[12]	Camenisch, JL; Lysyanskaya, A.; Yung, M., Dynamic accumulators and application to efficient revocation of anonymous credentials, Advances in Cryptology - CRYPTO 2002, 61-76, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94545 · doi:10.1007/3-540-45708-9_5
[13]	Chase, M.; Lysyanskaya, A.; Dwork, C., On signatures of knowledge, Advances in Cryptology - CRYPTO 2006, 78-96, 2006, Heidelberg: Springer, Heidelberg · Zbl 1129.94043 · doi:10.1007/11818175_5
[14]	Chaum, D.; van Heyst, E.; Davies, DW, Group signatures, Advances in Cryptology - EUROCRYPT ’91, 257-265, 1991, Heidelberg: Springer, Heidelberg · Zbl 0791.68044 · doi:10.1007/3-540-46416-6_22
[15]	Dodis, Y.; Kiayias, A.; Nicolosi, A.; Shoup, V.; Cachin, C.; Camenisch, JL, Anonymous identification in Ad Hoc groups, Advances in Cryptology - EUROCRYPT 2004, 609-626, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94414 · doi:10.1007/978-3-540-24676-3_36
[16]	Fischlin, M.; Shoup, V., Communication-efficient non-interactive proofs of knowledge with online extractors, Advances in Cryptology - CRYPTO 2005, 152-168, 2005, Heidelberg: Springer, Heidelberg · Zbl 1145.94467 · doi:10.1007/11535218_10
[17]	Faust, S.; Kohlweiss, M.; Marson, GA; Venturi, D.; Galbraith, S.; Nandi, M., On the non-malleability of the Fiat-Shamir transform, Progress in Cryptology - INDOCRYPT 2012, 60-79, 2012, Heidelberg: Springer, Heidelberg · Zbl 1295.94063 · doi:10.1007/978-3-642-34931-7_5
[18]	Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology - CRYPTO 1986, 186-194, 1987, Heidelberg: Springer, Heidelberg · Zbl 0636.94012
[19]	Fujisaki, E.; Suzuki, K., Traceable ring signature, IEICE Trans., 91-A, 1, 83, 2008 · doi:10.1093/ietfec/e91-a.1.83
[20]	Franklin, M.; Zhang, H.; Sadeghi, A-R, Unique ring signatures: a practical construction, Financial Cryptography and Data Security, 162-170, 2013, Heidelberg: Springer, Heidelberg · Zbl 1524.94081 · doi:10.1007/978-3-642-39884-1_13
[21]	Groth, J.; Kohlweiss, M.; Oswald, E.; Fischlin, M., One-out-of-many proofs: or how to leak a secret and spend a coin, Advances in Cryptology - EUROCRYPT 2015, 253-280, 2015, Heidelberg: Springer, Heidelberg · Zbl 1371.94639 · doi:10.1007/978-3-662-46803-6_9
[22]	Groth, J.; Kurosawa, K., Fully anonymous group signatures without random oracles, Advances in Cryptology - ASIACRYPT 2007, 164-180, 2007, Heidelberg: Springer, Heidelberg · Zbl 1153.94386 · doi:10.1007/978-3-540-76900-2_10
[23]	Kiayias, A.; Yung, M.; Cramer, R., Group signatures with efficient concurrent join, Advances in Cryptology - EUROCRYPT 2005, 198-214, 2005, Heidelberg: Springer, Heidelberg · Zbl 1137.94373 · doi:10.1007/11426639_12
[24]	Langlois, A.; Ling, S.; Nguyen, K.; Wang, H.; Krawczyk, H., Lattice-based group signature scheme with verifier-local revocation, Public-Key Cryptography - PKC 2014, 345-361, 2014, Heidelberg: Springer, Heidelberg · Zbl 1335.94063 · doi:10.1007/978-3-642-54631-0_20
[25]	Libert, B.; Peters, T.; Yung, M.; Safavi-Naini, R.; Canetti, R., Group signatures with almost-for-free revocation, Advances in Cryptology - CRYPTO 2012, 571-589, 2012, Heidelberg: Springer, Heidelberg · Zbl 1296.94156 · doi:10.1007/978-3-642-32009-5_34
[26]	Liu, JK; Wei, VK; Wong, DS; Wang, H.; Pieprzyk, J.; Varadharajan, V., Linkable spontaneous anonymous group signature for ad hoc groups, Information Security and Privacy, 325-335, 2004, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-27800-9_28
[27]	Nguyen, L.; Menezes, A., Accumulators from bilinear pairings and applications, Topics in Cryptology - CT-RSA 2005, 275-292, 2005, Heidelberg: Springer, Heidelberg · Zbl 1079.94568 · doi:10.1007/978-3-540-30574-3_19
[28]	Nguyen, L.; Safavi-Naini, R.; Lee, PJ, Efficient and provably secure trapdoor-free group signature schemes from bilinear pairings, Advances in Cryptology - ASIACRYPT 2004, 372-386, 2004, Heidelberg: Springer, Heidelberg · Zbl 1094.94530 · doi:10.1007/978-3-540-30539-2_26
[29]	Pedersen, TP; Feigenbaum, J., Non-interactive and information-theoretic secure verifiable secret sharing, Advances in Cryptology - CRYPTO 1991, 129-140, 1992, Heidelberg: Springer, Heidelberg · Zbl 0763.94015
[30]	Rivest, RL; Shamir, A.; Tauman, Y.; Boyd, C., How to leak a secret, Advances in Cryptology - ASIACRYPT 2001, 552-565, 2001, Heidelberg: Springer, Heidelberg · Zbl 1064.94558 · doi:10.1007/3-540-45682-1_32
[31]	Sakai, Y.; Schuldt, JCN; Emura, K.; Hanaoka, G.; Ohta, K.; Fischlin, M.; Buchmann, J.; Manulis, M., On the security of dynamic group signatures: preventing signature hijacking, Public Key Cryptography - PKC 2012, 715-732, 2012, Heidelberg: Springer, Heidelberg · Zbl 1291.94196 · doi:10.1007/978-3-642-30057-8_42
[32]	Xu, S.; Yung, M.; Quisquater, J-J; Paradinas, P.; Deswarte, Y.; El Kalam, AA, Accountable ring signatures: a smart card approach, Smart Card Research and Advanced Applications VI, 271-286, 2004, Boston: Springer, Boston · doi:10.1007/1-4020-8147-2_18