Abstract
In this work, we study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other. Such proofs arise in important real-life applications such as those requiring verifiable PRF evaluation and have so far not received significant attention as a standalone problem.
We first introduce a general framework, \(\mathsf {LANES^+}\), for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge \(\textsf{RPoK}\) and the \(\textsf{LANES}\) framework (due to a series of works in Crypto’20, Asiacrypt’20, ACM CCS’20). The latter framework is a powerful lattice-based proof system that can prove exact linear and multiplicative relations. The advantage of \(\mathsf {LANES^+}\) is its ability to realize hybrid proofs more efficiently by exploiting \(\textsf{RPoK}\) for the high-dimensional part of the secret witness while leaving a low-dimensional secret witness part for the exact proof that is proven at a significantly lower cost via \(\textsf{LANES}\). Thanks to the flexibility of \(\mathsf {LANES^+}\), other exact proof systems can also be supported.
We apply our \(\mathsf {LANES^+}\) framework to construct substantially shorter proofs of rounding, which is a central tool for verifiable deterministic lattice-based cryptography. Based on our rounding proof, we then design an efficient long-term verifiable random function (VRF), named \(\textsf{LaV}\). \(\textsf{LaV}\) leads to the shortest VRF outputs among the proposals of standard (i.e., long-term and stateless) VRFs based on quantum-safe assumptions. Of independent interest, we also present generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Even the optimized proof of 1024-dimensional LWE samples with ternary secret and error (i.e., \(\textbf{s},\textbf{e}\in \{-1,0,1\}^{1024}\)) in [47] is at 33 KB. The magnitude of rounding error coefficients needs to be bigger for a VRF to circumvent algebraic attacks.
- 2.
The polynomials need to obey certain restrictions depending on the structure of the underlying ring \(\mathcal {R}_{q,d}\), which is explained formally in Sect. 2.4.
- 3.
Note that in this case, we need to hide \(\textbf{w}:=\textbf{Ay}\). Otherwise, everyone could compute \(\textbf{t} - \textbf{w} = \textbf{Bm}\), which leaks information on the secret \(\textbf{m}\).
- 4.
We note here that for \(l<d\), the proved relations actually hold over \(\mathbb {F}_{q^{d/l}}\). However, with a shortness proof of the form \(P_i(x)=\prod _{j\in [\beta ]} (x-j)\) for some \(\beta <q\in \mathbb {Z}^+\), the proved relation is restricted to \(\mathbb {Z}_q\subseteq \mathbb {F}_{q^{d/l}}\). This is explained further in [24, App. A]. We have such a shortness proof for all of our applications in this work, and therefore, our description is focused on \(\mathbb {Z}_q\).
- 5.
We note here that one does not necessarily need to consider positive ranges \([0,T-1]\). It is straightforward to “shift” the range to support a more general range [a, b] with \(a\le b \in \mathbb {Z}\). For example, proving knowledge of \({\overrightarrow{m}}\in [a,b]^N\) with \(\textbf{A}{\overrightarrow{m}} = {\overrightarrow{u}}\) is equivalent to proving knowledge of \({\overrightarrow{m}}'\in [0,b-a]^N\) such that \(\textbf{A}{\overrightarrow{m}}' = {\overrightarrow{u}}' \) for \({\overrightarrow{u}}':={\overrightarrow{u}} - \textbf{A}{\overrightarrow{a}}^N \) and \({\overrightarrow{a}}^N:= (a,\ldots ,a)\in \mathbb {Z}^N\). Hence, the important part is the width, T, of the range.
References
Albrecht, M.R., Cid, C., Faugère, J., Fitzpatrick, R., Perret, L.: Algebraic algorithms for LWE problems. ACM Commun. Comput. Algebra 49(2), 62 (2015)
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015). https://bitbucket.org/malb/lwe-estimator/src/master/
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
Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 28–47. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04852-9_2
Banerjee, A., Peikert, C.: New and improved key-homomorphic pseudorandom functions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 353–370. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_20
Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42
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
Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: ACM CCS, pp. 390–399. ACM (2006)
Ben-Sasson, E., et al.: Zerocash: Decentralized anonymous payments from bitcoin. In: IEEE Symposium on Security and Privacy, pp. 459–474. IEEE Computer Society (2014)
Bitansky, N.: Verifiable random functions from non-interactive witness-indistinguishable proofs. J. Cryptol. 33(2), 459–493 (2020)
Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23
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
Buser, M., et al.: Post-quantum verifiable random function from symmetric primitives in pos blockchain. IACR Cryptology ePrint Archive, Paper 2021/302 (2021)
Camenisch, J., Hohenberger, S., Kohlweiss, M., Lysyanskaya, A., Meyerovich, M.: How to win the clonewars: efficient periodic n-times anonymous authentication. In: ACM CCS, pp. 201–210. ACM (2006)
Camenisch, J., Lehmann, A.: (Un)linkable pseudonyms for governmental databases. In: ACM CCS, pp. 1467–1479. ACM (2015)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC, pp. 494–503. ACM (2002)
Chen, J., Micali, S.: Algorand: a secure and efficient distributed ledger. Theor. Comput. Sci. 777, 155–183 (2019)
Chiesa, A., Green, M., Liu, J., Miao, P., Miers, I., Mishra, P.: Decentralized anonymous micropayments. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 609–642. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_21
Coull, S., Green, M., Hohenberger, S.: Controlling access to an oblivious database using stateful anonymous credentials. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 501–520. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00468-1_28
del Pino, R., Lyubashevsky, V., Seiler, G.: Lattice-based group signatures and zero-knowledge proofs of automorphism stability. In: ACM CCS, pp. 574–591. ACM (2018)
Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: CRYSTALS-Dilithium: digital signatures from module lattices. In: CHES, vol. 2018, January 2018
Escala, A., Groth, J.: Fine-tuning Groth-Sahai proofs. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 630–649. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_36
Esgin, M.F., et al.: Practical post-quantum few-time verifiable random function with applications to Algorand. In: Borisov, N., Diaz, C. (eds.) FC 2021. LNCS, vol. 12675, pp. 560–578. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-662-64331-0_29
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, D., Ruj, S.: Efficient hybrid exact/relaxed lattice proofs and applications to rounding and VRFs. Cryptology ePrint Archive, Paper 2022/141 (2022). https://eprint.iacr.org/2022/141
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. In: IEEE Symposium on Security and Privacy (S &P), pp. 1281–1298. IEEE (2022). (Full version at ia.cr/2021/545)
Esgin, M.F., Zhao, R.K., Steinfeld, R., Liu, J.K., Liu, D.: MatRiCT: efficient, scalable and post-quantum blockchain confidential transactions protocol. In: ACM CCS, pp. 567–584. ACM (2019)
Fujisaki, E., Suzuki, K.: Traceable ring signature. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 181–200. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_13
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling Byzantine Agreements for cryptocurrencies. In: SOSP, pp. 51–68. ACM (2017)
Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L., Vasant, S., Ziv, A.: NSEC5: provably preventing DNSSEC zone enumeration. In: NDSS. The Internet Society (2015)
Goyal, R., Hohenberger, S., Koppula, V., Waters, B.: A generic approach to constructing and proving verifiable random functions. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 537–566. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_18
Green, M., Miers, I.: Bolt: anonymous payment channels for decentralized currencies. In: ACM CCS, pp. 473–489. ACM (2017)
Hohenberger, S., Myers, S.A., Pass, R., Shelat, A.: ANONIZE: a large-scale anonymous survey system. In: IEEE Symposium on Security and Privacy, pp. 375–389. IEEE Computer Society (2014)
Jarecki, S., Kiayias, A., Krawczyk, H.: Round-optimal password-protected secret sharing and T-PAKE in the password-only model. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 233–253. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_13
Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357–388. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_12
Kilian, J.: Uses of Randomness in Algorithms and Protocols. MIT Press (1990)
Kim, D., Lee, D., Seo, J., Song, Y.: Toward practical lattice-based proof of knowledge from Hint-MLWE. Cryptology ePrint Archive, Paper 2023/623 (2023). https://eprint.iacr.org/2023/623
Lawlor, S., Lewi, K.: Deploying key transparency at WhatsApp. https://engineering.fb.com/2023/04/13/security/whatsapp-key-transparency/. Accessed 16 May 2023
Libert, B., Ling, S., Nguyen, K., Wang, H.: Zero-knowledge arguments for lattice-based PRFs and applications to e-cash. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 304–335. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_11
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
Lyubashevsky, V., Nguyen, N.K., Plançon, M.: Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology, CRYPTO 2022. LNCS, vol. 13508, pp. 71–101. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_3
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: ACM 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
Lyubashevsky, V., Seiler, G.: Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 204–224. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_8
Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: FOCS, pp. 120–130. IEEE Computer Society (1999)
Nguyen, N.K.: Private communication (2022)
Papadopoulos, D., et al.: Making NSEC5 practical for DNSSEC. Cryptology ePrint Archive, Report 2017/099 (2017). https://eprint.iacr.org/2017/099
Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_2
Yamada, S.: Asymptotically compact adaptively secure lattice ibes and verifiable random functions via generalized partitioning techniques. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 161–193. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_6
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
Acknowledgements
This research was supported in part by ARC Discovery Project grants DP180102199 and DP220101234.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Esgin, M.F., Steinfeld, R., Liu, D., Ruj, S. (2023). Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14085. Springer, Cham. https://doi.org/10.1007/978-3-031-38554-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-38554-4_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38553-7
Online ISBN: 978-3-031-38554-4
eBook Packages: Computer ScienceComputer Science (R0)