Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors
Tóm tắt
An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.
Tài liệu tham khảo
T. Acar, L. Nguyen, Revocation for delegatable anonymous credentials, in PKC 2011. LNCS, vol. 6571 (Springer, 2011), pp. 423–440
C. Aguilar-Melchor, S. Bettaieb, X. Boyen, L. Fousse, P. Gaborit, Adapting Lyubashevsky’s signature schemes to the ring signature setting, in AFRICACRYPT 2013. LNCS, vol. 7918 (Springer, 2013), pp. 1–25
M. Ajtai, Generating hard instances of lattice problems (extended abstract), in STOC 1996 (ACM, 1996), pp. 99–108
G. Ateniese, J. Camenisch, M. Joye, G. Tsudik, A practical and provably secure coalition-resistant group signature scheme, in CRYPTO 2000. LNCS, vol. 1880 (Springer, 2000), pp. 255–270
M. H. Au, Q. Wu, W. Susilo, Y. Mu, Compact E-cash from bounded accumulator, in CT-RSA 2007. LNCS, vol. 4377 (Springer, 2007), pp. 178–195
N. Baric, B. Pfitzmann, Collision-free accumulators and fail-stop signature schemes without trees, in EUROCRYPT 1997. LNCS, vol. 1233 (Springer, 1997), pp. 480–494
M. Bellare, D. Micciancio, B. Warinschi, Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions, in EUROCRYPT 2003. LNCS, vol. 2656 (Springer, 2003), pp. 614–629
E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, M. Virza, Zerocash: decentralized anonymous payments from bitcoin, in IEEE S &P 2014 (IEEE, 2014), pp. 459–474
J. Benaloh, M. de Mare, One-way accumulators: a decentralized alternative to digital signatures, in EUROCRYPT 1993. LNCS, vol. 765 (Springer, 1993), pp. 274–285
A. Bender, J. Katz, R. Morselli. Ring signatures: stronger definitions, and constructions without random oracles. J. Cryptol. 22(1), 114–138 (2009)
F. Benhamouda, J. Camenisch, S. Krenn, V. Lyubashevsky, G. Neven, Better zero-knowledge proofs for lattice encryption and their application to group signatures, in ASIACRYPT 2014. LNCS, vol. 8873 (Springer, 2014), pp. 551–572
D. Bernhard, M. Fischlin, B. Warinschi, Adaptive proofs of knowledge in the random oracle model, in PKC 2015. LNCS, vol. 9020 (Springer, 2015), pp. 629–649
D. Boneh, X. Boyen, Short signatures without random oracles, in EUROCRYPT 2004. LNCS, vol. 3027 (Springer, 2004), pp. 223–238
D. Boneh, H. Corrigan-Gibbs, Bivariate polynomials modulo composites and their applications, in ASIACRYPT 2014, Part I. LNCS, vol. 8873 (Springer, 2014), pp. 42–62
D. Boneh, S. Eskandarian, B. Fisch, Post-quantum EPID signatures from symmetric primitives. IACR Cryptology ePrint Archive, 2018:261, 2018. To appear at CT-RSA 2019
J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi, J. Groth, C. Petit, Short accountable ring signatures based on DDH, in ESORICS 2015. LNCS, vol. 9326 (Springer, 2015)
X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in PKC 2010. LNCS, vol. 6056 (Springer, 2010), pp. 499–517
Z. Brakerski, Y. T. Kalai, A framework for efficient signatures, ring signatures and identity based encryption in the standard model, in IACR Cryptology ePrint Archive, 2010:86, 2010
E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung, Design validations for discrete logarithm based signature schemes, in PKC 2000. LNCS, vol. 1751 (Springer, 2000), pp. 276–292
J. Camenisch, M. Kohlweiss, C. Soriente, An accumulator based on bilinear maps and efficient revocation for anonymous credentials, in PKC 2009. LNCS, vol. 5443 (Springer, 2009), pp. 481–500
J. Camenisch, A. Lysyanskaya, Dynamic accumulators and application to efficient revocation of anonymous credentials, in CRYPTO 2002. LNCS, vol. 2442 (Springer, 2002), pp. 61–76
J. Camenisch, G. Neven, M. Rückert, Fully anonymous attribute tokens from lattices, in SCN 2012. LNCS, vol. 7485 (Springer, 2012), pp. 57–75
S. Canard, A. Gouget, Multiple denominations in E-cash with compact transaction data, in FC 2010. LNCS, vol. 6052 (Springer, 2010), pp. 82–97
D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, Bonsai trees, or how to delegate a lattice basis, in EUROCRYPT 2010. LNCS, vol. 6110 (Springer, 2010), pp. 523–552
D. Catalano, D. Fiore, Vector commitments and their applications, in PKC 2013. LNCS, vol. 7778 (Springer, 2013), pp. 55–72
N. Chandran, J. Groth, A. Sahai, Ring signatures of sub-linear size without random oracles, in ICALP 2007. LNCS, vol. 4596 (Springer, 2007), pp. 423–434
D. Chaum, E. van Heyst. Group signatures, in EUROCRYPT 1991. LNCS, vol. 547 (Springer, 1991), pp. 257–265
S. Cheng, K. Nguyen, H. Wang, Policy-based signature scheme from lattices. Des. Codes Cryptogr. 81(1), 43–74 (2016)
R. del Pino, V. Lyubashevsky, G. Seiler, Lattice-based group signatures and zero-knowledge proofs of automorphism stability, in CCS 2018 (ACM, 2018), pp. 574–591
D. Derler, C. Hanser, D. Slamanig, Revisiting cryptographic accumulators, additional properties and relations to other primitives, in CT-RSA 2015. LNCS, vol. 9048 (Springer, 2015), pp. 127–144
D. Derler, S. Ramacher, D. Slamanig, Post-quantum zero-knowledge proofs for accumulators with applications to ring signatures from symmetric-key primitives, in PQCrypto 2018. LNCS, vol. 10786 (Springer, 2018), pp. 419–440
Y. Dodis, A. Kiayias, A. Nicolosi, V. Shoup, Anonymous identification in ad hoc groups, in EUROCRYPT 2004. LNCS, vol. 3027 (Springer, 2004), pp. 609–626
M. F. Ezerman, H. T. Lee, S. Ling, K. Nguyen, H. Wang, A provably secure group signature scheme from code-based assumptions, in ASIACRYPT 2015, Part I. LNCS, vol. 9452 (Springer, 2015), pp. 260–285
P.-A. Fouque, D. Pointcheval, Threshold cryptosystems secure against chosen-ciphertext attacks, in ASIACRYPT 2001. LNCS, vol. 2248 (Springer, 2001), pp. 351–368
C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC 2008 (ACM, 2008), pp. 197–206
O. Goldreich, S. Goldwasser, S. Halevi, Collision-free hashing from lattice problems, in Studies in Complexity and Cryptography. LNCS, vol. 6650 (Springer, 2011), pp. 30–39
S. D. Gordon, J. Katz, V. Vaikuntanathan, A group signature scheme from lattice assumptions, in ASIACRYPT 2010. LNCS, vol. 6477 (Springer, 2010), pp. 395–412
J. Groth, Evaluating security of voting schemes in the universal composability framework, in ACNS 2004. LNCS, vol. 3089 (Springer, 2004), pp. 46–60
J. Groth, Short pairing-based non-interactive zero-knowledge arguments, in ASIACRYPT 2010. LNCS, vol. 6477 (Springer, 2010), pp. 321–340
J. Groth, M. Kohlweiss, One-out-of-many proofs: or how to leak a secret and spend a coin, in EUROCRYPT 2015. LNCS, vol. 9057 (Springer, 2015), pp. 253–280
A. Jain, S. Krenn, K. Pietrzak, A. Tentes, Commitments and efficient zero-knowledge proofs from learning parity with noise, in ASIACRYPT 2012. LNCS, vol. 7658 (Springer, 2012), pp. 663–680
M. P. Jhanwar, R. Safavi-Naini, Compact accumulator using lattices. IACR Cryptology ePrint Archive: Report 2014/1015, February (2015)
A. E. Kaafarani, S. Katsumata, R. Solomon, Anonymous reputation systems achieving full dynamicity from lattices, in Financial Cryptography and Data Security 2018 (2018)
J. Katz, V. Kolesnikov, X. Wang, Improved non-interactive zero knowledge with applications to post-quantum signatures, in CCS 2018 (ACM, 2018), pp. 525–537
A. Kawachi, K. Tanaka, K. Xagawa, Multi-bit cryptosystems based on lattice problems, in PKC 2007. LNCS, vol. 4450 (Springer, 2007), pp. 315–329
A. Kawachi, K. Tanaka, K. Xagawa, Concurrently secure identification schemes based on the worst-case hardness of lattice problems, in ASIACRYPT 2008. LNCS, vol. 5350 (Springer, 2008), pp. 372–389
F. Laguillaumie, A. Langlois, B. Libert, D. Stehlé, Lattice-based group signatures with logarithmic signature size, in ASIACRYPT 2013. LNCS, vol. 8270 (Springer, 2013), pp. 41–61
A. Langlois, S. Ling, K. Nguyen, H. Wang, Lattice-based group signature scheme with verifier-local revocation, in PKC 2014. LNCS, vol. 8383 (Springer, 2014), pp. 345–361
J. Li, N. Li, R. Xue, Universal accumulators with efficient nonmembership proofs, in ACNS 2007. LNCS, vol. 4521 (Springer, 2007), pp. 253–269
B. Libert, S. Ling, F. Mouhartem, K. Nguyen, H. Wang, Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions, in ASIACRYPT 2016. LNCS, vol. 10032 (Springer, 2016), pp. 373–403
B. Libert, S. Ling, F. Mouhartem, K. Nguyen, H. Wang, Adaptive oblivious transfer with access control from lattice assumptions, in ASIACRYPT 2017. LNCS, vol. 10624 (Springer, 2017), pp. 533–563
B. Libert, S. Ling, K. Nguyen, H. Wang. Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors, in EUROCRYPT 2016. LNCS, vol. 9666 (Springer, 2016), pp. 1–31
B. Libert, S. Ling, K. Nguyen, H. Wang. Zero-knowledge arguments for lattice-based prfs and applications to e-cash, in ASIACRYPT 2017. LNCS, vol. 10626 (Springer, 2017), pp. 304–335
B. Libert, S. Ling, K. Nguyen, H. Wang, Lattice-based zero-knowledge arguments for integer relations, in CRYPTO 2018. LNCS, vol. 10992 (Springer, 2018), pp. 700–732
S. Ling, K. Nguyen, D. Stehlé, H. Wang, Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications, in PKC 2013. LNCS, vol. 7778 (Springer, 2013), pp. 107–124
S. Ling, K. Nguyen, H. Wang, Group signatures from lattices: simpler, tighter, shorter, ring-based, in PKC 2015. LNCS, vol. 9020 (Springer, 2015), pp. 427–449
S. Ling, K. Nguyen, H. Wang, Y. Xu, Lattice-based group signatures: achieving full dynamicity (and deniability) with ease. Theor. Comput. Sci. 783, 71–94 (2019)
H. Lipmaa, Secure accumulators from Euclidean rings without trusted setup, in ACNS 2012. LNCS, vol. 7341 (Springer, 2012), pp. 224–240
V. Lyubashevsky, Lattice-based identification schemes secure under active attacks, in PKC 2008. LNCS, vol. 4939 (Springer, 2008), pp. 162–179
V. Lyubashevsky, Lattice signatures without trapdoors, in EUROCRYPT 2012. LNCS, vol. 7237 (Springer, 2012), pp. 738–755
R.C. Merkle, A certified digital signature, in CRYPTO 1989. LNCS, vol. 435 (Springer, 1989), pp. 218–238
D. Micciancio, P. Mol, Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions, in CRYPTO 2011. LNCS, vol. 6841 (Springer, 2011), pp. 465–484
D. Micciancio, C. Peikert, Hardness of SIS and LWE with small parameters, in CRYPTO 2013, Part I. LNCS, vol. 8042 (Springer, 2013), pp. 21–39
D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)
I. Miers, C. Garman, M. Green, A. D. Rubin, Zerocoin: anonymous distributed E-cash from bitcoin, in IEEE S &P 2013 (IEEE, 2013), pp. 397–411
M. Naor, On cryptographic assumptions and challenges, in CRYPTO 2003. LNCS, vol. 2729 (Springer, 2003), pp. 96–109
M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, in STOC 1990 (ACM, 1990), pp. 427–437
K. Nguyen, H. Tang, H. Wang, N. Zeng, New code-based privacy-preserving cryptographic constructions, in ASIACRYPT 2019. LNCS, vol. 11922 (Springer, 2019), pp. 25–55
L. Nguyen, Accumulators from bilinear pairings and applications, in CT-RSA 2005. LNCS, vol. 3376 (Springer, 2005), pp. 275–292
P. Q. Nguyen, J. Zhang, Z. Zhang, Simpler efficient group signatures from lattices, in PKC 2015. LNCS, vol. 9020 (Springer, 2015), pp. 401–426
C. Papamanthou, E. Shi, R. Tamassia, K. Yi, Streaming authenticated data structures, in EUROCRYPT 2013. LNCS, vol. 7881 (Springer, 2013), pp. 353–370
C. Papamanthou, R. Tamassia, N. Triandopoulos, Authenticated hash tables, in ACM-CCS 2008 (ACM, 2008), pp. 437–448
C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, in STOC 2009 (ACM, 2009), pp. 333–342
C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in CRYPTO 2008. LNCS, vol. 5157 (Springer, 2008), pp. 554–571
M. Prabhakaran, R. Xue, Statistically hiding sets, in CT-RSA 2009. LNCS, vol. 5473 (Springer, 2009), pp. 100–116
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in STOC 2005 (ACM, 2005), pp. 84–93
R. L. Rivest, A. Shamir, Y. Tauman, How to leak a secret, in ASIACRYPT 2001. LNCS, vol. 2248 (Springer, 2001), pp. 552–565
A. Sahai, Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security, in FOCS 1999 (1999), pp. 543–553
J. Stern, A new paradigm for public key identification. IEEE Trans. Inf. Theory 42(6), 1757–1768 (1996)
G. Tsudik, S. Xu, Accumulating composites and improved group signing, in ASIACRYPT 2003. LNCS, vol. 2894 (Springer, 2003), pp. 269–286
R. Xue, N. Li, J. Li, Algebraic construction for zero-knowledge sets. J. Comput. Sci. Technol. 23(2), 166–175 (2008)