Abstract
We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the protocol.
Using these new primitives and techniques, we give instantiations of the most compact lattice-based ring and group signatures schemes. The improvement in signature sizes over prior works ranges between \(25\%\) and 2X. Perhaps of even more significance, the size of the user public keys, which need to be stored somewhere publicly accessible in order for ring signatures to be meaningful, is reduced by factors ranging from 7X to 15X. In what could be of independent interest, we also provide noticeably improved proofs for integer relations which, together with one-out-of-many proofs are key components of confidential payment systems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The original formal definition of a one-out-of-many proof from [GK15] is more restricted in that \(A\vec s\) is a commitment to 0 rather than just an evaluation of a one-way function on \(\vec s\). But we do not need to restrict to this definition in this work.
- 2.
Being able to prove quadratic relations, of course also allows one to prove that the \(\ell _2\)-norm of \(\vec s\) is smaller than some bound.
- 3.
This only proves that \(\vec v\) is either a unit vector or a negative unit vector. But this is fine because proving knowledge of \(\vec v,\vec s\) satisfying \(\pm T\vec v=A\vec s\) is equivalent to (1).
- 4.
One might be tempted to put the secret message into the \(\textbf{m}\) part of the commitment, which does not leak even if there is leakage in \(\textbf{s}_2\), but this results in a much less efficient commitment scheme because the dimension of the commitment grows linearly with the dimension of \(\textbf{m}\), whereas \(\textbf{s}_1\) has no effect on the size of the commitment. See Sect. 2.6.
- 5.
If we want to prove that \(\Vert \vec s\Vert \leqslant \beta \), then we could create another commitment to a vector \(\vec s'\in \mathcal {R}_q\) such that \(\Vert \vec s\Vert ^2+\Vert \vec s'\Vert ^2=\beta ^2\) – the existence of such an \(\vec s'\) is guaranteed by the four squares theorem.
- 6.
It is of course possible to reduce the public key size of any scheme by hashing it as \(\textsf{pk}'=H(\textsf{pk})\) for some cryptographic hash function H with the resulting \(\textsf{pk}'\) being as small as 32 bytes. This technique is fine for regular signatures, where one can reveal \(\textsf{pk}\) as part of the signature; but ring signatures will require a zero-knowledge proof that \(\textsf{pk}'=H(\textsf{pk})\), which will make the signatures orders of magnitude larger and slower.
- 7.
If we make p too small, then the signature size will increase because a smaller p requires more “garbage terms” in the zero-knowledge proof to increase soundness. In our parameter settings, we chose a particular compromise between the public key size and signature size, but one could make the public key size even smaller at the expense of a few extra kilobytes in the signature size.
- 8.
Message \(\textbf{m}\) does not need to be included in the opening since it can be deterministically computed from \(\textbf{t}_B\) and \(\textbf{s}_2\).
- 9.
Proving that b is a sign has already been covered in [LNP22, Section 5.1].
- 10.
Alternatively, \(u_i \in \{1,X,X^2,\ldots ,X^{\mathfrak {d}-1}\}\).
References
Attema, T., Fehr, S., Klooß, M.: Fiat-Shamir transformation of multi-round interactive proofs. Cryptology ePrint Archive, Paper 2021/1377 (2021). https://eprint.iacr.org/2021/1377
Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99–108 (1996)
Attema, T., Lyubashevsky, V., Seiler, G.: Practical product proofs for lattice commitments. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 470–499. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_17
Alperin-Sheriff, J., Peikert, C.: Circular and KDM security for identity-based encryption. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 334–352. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_20
Alperin-Sheriff, J., Apon, D.: Dimension-preserving reductions from LWE to LWR. Cryptology ePrint Archive, Report 2016/589 (2016). https://ia.cr/2016/589
Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(1), 625–635 (1993)
Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., Petit, C.: Short accountable ring signatures based on DDH. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) ESORICS 2015. LNCS, vol. 9326, pp. 243–265. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24174-6_13
Buser, M., et al.: A survey on exotic signatures for post-quantum blockchain: challenges & research directions. Cryptology ePrint Archive, Paper 2022/1151 (2022). https://eprint.iacr.org/2022/1151
Beullens, W., Dobson, S., Katsumata, S., Lai, Y.-F., Pintore, F.: Group signatures and more from isogenies and lattices: generic, simple, and efficient. IACR Cryptology ePrint Archive, p. 1366 (2021)
Baum, C., Damgård, I., Lyubashevsky, V., Oechsner, S., Peikert, C.: More efficient commitments from structured lattice assumptions. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 368–385. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_20
Boudgoust, K., Jeudy, C., Roux-Langlois, A., Wen, W.: On the hardness of module-LWE with binary secret. In: Paterson, K.G. (ed.) CT-RSA 2021. LNCS, vol. 12704, pp. 503–526. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-75539-3_21
Beullens, W., Katsumata, S., Pintore, F.: Calamari and Falafl: logarithmic (linkable) ring signatures from isogenies and lattices. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 464–492. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_16
Bootle, J., Lyubashevsky, V., Seiler, G.: Algebraic techniques for short(er) exact lattice-based zero-knowledge proofs. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 176–202. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_7
Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 329–358. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_12
Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_3
Dodis, Y., Goldwasser, S., Tauman Kalai, Y., Peikert, C., Vaikuntanathan, V.: Public-key encryption schemes with auxiliary inputs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 361–381. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_22
Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_2
Ducas, L., Prest, T.: Fast Fourier orthogonalization. In: ISSAC, pp. 191–198 (2016)
Esgin, M.F., Nguyen, N.K., Seiler, G.: Practical exact proofs from lattices: new techniques to exploit fully-splitting rings. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 259–288. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_9
Esgin, M.F., Steinfeld, R., Liu, J.K., Liu, D.: Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 115–146. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_5
Esgin, M.F., Steinfeld, R., Sakzad, A., Liu, J.K., Liu, D.: Short lattice-based one-out-of-many proofs and applications to ring signatures. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 2019. LNCS, vol. 11464, pp. 67–88. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21568-2_4
Esgin, M.F., Steinfeld, R., Zhao, R.K.: Matrict+: more efficient post-quantum private blockchain payments. IACR Cryptology ePrint Archive, p. 545 (2021)
Esgin, M.F., Zhao, R.K., Steinfeld, R., Liu, J.K., Liu, D.: Matrict: efficient, scalable and post-quantum blockchain confidential transactions protocol. In: CCS, pp. 567–584. ACM (2019)
Fouque, P.-A., et al.: Falcon: Fast-Fourier lattice-based compact signatures over NTRU. Technical report (2020). https://falcon-sign.info/falcon.pdf
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12
Groth, J., Kohlweiss, M.: One-out-of-many proofs: or how to leak a secret and spend a coin. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 253–280. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_9
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSign: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36563-X_9
Lu, X., Au, M.H., Zhang, Z.: Raptor: a practical lattice-based (linkable) ring signature. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 2019. LNCS, vol. 11464, pp. 110–130. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21568-2_6
Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_4
Lyubashevsky, V., Nguyen, N.K., Plancon, M.: Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. Cryptology ePrint Archive, Paper 2022/284 (2022). https://eprint.iacr.org/2022/284. To appear at CRYPTO 2022
Lyubashevsky, V., Nguyen, N.K., Plancon, M., Seiler, G.: Shorter lattice-based group signatures via “almost free’’ encryption and other optimizations. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13093, pp. 218–248. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92068-5_8
Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Practical lattice-based zero-knowledge proofs for integer relations. In: CCS, pp. 1051–1070. ACM (2020)
Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Shorter lattice-based zero-knowledge proofs via one-time commitments. In: Garay, J.A. (ed.) PKC 2021. LNCS, vol. 12710, pp. 215–241. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-75245-3_9
Lyubashevsky, V., Nguyen, N.K., Seiler, G.: SMILE: set membership from ideal lattices with applications to ring signatures and confidential transactions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 611–640. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_21
Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 107–124. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_8
Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Crypt. 75(3), 565–599 (2015)
Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_35
Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_43
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC, pp. 427–437 (1990)
Tao, Y., Wang, X., Zhang, R.: Short zero-knowledge proof of knowledge for lattice-based commitment. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 268–283. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_15
Yang, R., Au, M.H., Zhang, Z., Xu, Q., Yu, Z., Whyte, W.: Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 147–175. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_6
Yuen, T.H., Esgin, M.F., Liu, J.K., Au, M.H., Ding, Z.: DualRing: generic construction of ring signatures with efficient instantiations. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 251–281. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_10
Acknowledgements
We would like to thank the anonymous reviewers for useful feedback. This work was conducted when the second author was at IBM Research Europe, and it was supported by the EU H2020 ERC Project 101002845 PLAZA.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 International Association for Cryptologic Research
About this paper
Cite this paper
Lyubashevsky, V., Nguyen, N.K. (2022). BLOOM: Bimodal Lattice One-out-of-Many Proofs and Applications. In: Agrawal, S., Lin, D. (eds) Advances in Cryptology – ASIACRYPT 2022. ASIACRYPT 2022. Lecture Notes in Computer Science, vol 13794. Springer, Cham. https://doi.org/10.1007/978-3-031-22972-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-22972-5_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22971-8
Online ISBN: 978-3-031-22972-5
eBook Packages: Computer ScienceComputer Science (R0)