Pseudorandom functions in NC class from the standard LWE assumption. (English) Zbl 1492.94145
Summary: The standard Learning with Errors (LWE) problem is associated with a polynomial modulus, which implies exponential hardness against quantum or classical algorithms. However, most of the existing LWE-based PRF schemes need super-polynomial or even exponential modulus. The very recent works due to S. Kim [Lect. Notes Comput. Sci. 12106, 576–607 (2020; Zbl 1492.94129)] and Q. Lai et al. [“Almost tight security in lattices with polynomial moduli – PRF, IBE, all-but-many LTF, and more”, ibid. 12110, 652–681 (2020; doi:10.1007/978-3-030-45374-9_22)] present PRFs from the standard LWE (i.e., LWE with polynomial modulus) assumptions. However, their PRFs cannot be implemented in NC circuits. With the help of the Döttling-Schröder (DS) paradigm [N. Döttling and D. Schröder [ibid. 9215, 329–350 (2015; Zbl 1375.94092)], Lai et al.’s PRF circuit [loc.cit.] can be compressed to \(NC^{2+\delta}\) with \(\delta > 0\). In this paper, we focus on constructing PRFs with shallower circuit implementations from the standard LWE assumption. To this end, we present three PRF schemes. The first two schemes are constructed from the generalized pseudorandom synthesizer (gSYN) and pseudorandom generators (PRGs) and can be implemented in \(NC^3\) and \(NC^2\) respectively. Meanwhile, the security of the two PRFs is based on the standard LWE assumptions, but only allow bounded queries from the adversary. Then we apply the DS paradigm to our PRFs to obtain the third PRF scheme in circuit class \(NC^{1+\varepsilon}\) with \(\epsilon \in (0,1)\), which not only relies on the standard LWE assumption, but also supports unbounded queries. Compared with the existing PRFs from standard LWE, our third PRF has the shallowest circuit.
References:
| [1] | Ajtai M., Kumar R., Sivakumar D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing (2001). · Zbl 1323.68561 |
| [2] | Alwen J., Krenn S., Pietrzak K., Wichs D.: Learning with rounding, revisited—new reduction, properties and applications. In: Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference, Part I. · Zbl 1310.94123 |
| [3] | Banerjee A.: New constructions of cryptographic pseudorandom functions. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA, USA (2015). http://hdl.handle.net/1853/53916. |
| [4] | Banerjee A., Peikert C.: New and improved key-homomorphic pseudorandom functions. In: Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Part I. · Zbl 1314.94053 |
| [5] | Banerjee A., Peikert C., Rosen A.: Pseudorandom functions and lattices. In: Advances in Cryptology - EUROCRYPT 2012—31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. · Zbl 1297.68071 |
| [6] | Boneh D., Kim S., Montgomery H.W.: Private puncturable prfs from standard lattice assumptions. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International, Part I. · Zbl 1410.94049 |
| [7] | Boneh D., Lewi K., Montgomery H.W., Raghunathan A.: Key homomorphic prfs and their applications. In: Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference, Part I. · Zbl 1310.94129 |
| [8] | Brakerski Z., Tsabary R., Vaikuntanathan V., Wee H.: Private constrained prfs (and more) from LWE. In: Theory of Cryptography—15th International Conference, TCC 2017, Part I (2017). · Zbl 1410.94053 |
| [9] | Brakerski Z., Vaikuntanathan V.: Constrained key-homomorphic prfs from standard lattice assumptions—or: How to secretly embed a circuit in your PRF. In: Theory of Cryptography—12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II. Lecture Notes in Computer Science. · Zbl 1379.94032 |
| [10] | Canetti R., Chen Y.: Constraint-hiding constrained prfs for nc \({}^{\text{1}}\) from LWE. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International. · Zbl 1410.94055 |
| [11] | Dodis Y., Reyzin L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In: Advances in Cryptology—EUROCRYPT (2004). · Zbl 1122.94368 |
| [12] | Döttling N., Schröder D.: Efficient pseudorandom functions via on-the-fly adaptation. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Part I (2015). · Zbl 1375.94092 |
| [13] | Goldreich O., Silvio Micali S.G.: How to construct random functions. J. ACM (1986). · Zbl 0596.65002 |
| [14] | Jager T., Kurek R., Pan J.: Simple and more efficient prfs with tight security from LWE and matrix-ddh. In: Advances in Cryptology—ASIACRYPT 2018—24th International Conference, Part III. · Zbl 1447.94045 |
| [15] | Kim S.: Key-homomorphic pseudorandom functions from LWE with small modulus. In: Advances in Cryptology—EUROCRYPT 2020—39th Annual International, Part II. · Zbl 1492.94129 |
| [16] | Laarhoven, T.; Mosca, M.; van de Pol, J., Finding shortest lattice vectors faster using quantum search, Des. Codes Cryptogr., 77, 375-400 (2015) · Zbl 1356.94069 · doi:10.1007/s10623-015-0067-5 |
| [17] | Lai Q., Liu F., Wang Z.: Almost tight security in lattices with polynomial moduli - prf, ibe, all-but-many ltf, and more. In: Public-Key Cryptography—PKC 2020—23rd. · Zbl 1501.94047 |
| [18] | Montgomery H.: More efficient lattice prfs from keyed pseudorandom synthesizers. In: Progress in Cryptology—INDOCRYPT 2018—19th International Conference on Cryptology in India, New Delhi, India, December 9-12, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11356, pp. 190-211 (2018). · Zbl 1407.94144 |
| [19] | Naor, M.; Reingold, O., Synthesizers and their application to the parallel construction of pseudo-random functions, J. Comput. Syst. Sci., 58, 336-375 (1999) · Zbl 0922.68052 · doi:10.1006/jcss.1998.1618 |
| [20] | Peikert C.: A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science (2016). · Zbl 1391.94788 |
| [21] | Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24 (2005). · Zbl 1192.94106 |
| [22] | Rudich, S.; Wigderson, A., Computational Complexity Theory, IAS / Park City Mathematics Series (2004), New York: AMS Chelsea Publishing, New York |
| [23] | Schnorr, C., A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., 53, 201-224 (1987) · Zbl 0642.10030 · doi:10.1016/0304-3975(87)90064-8 |
| [24] | Shoup, V., A Computational Introduction to Number Theory and Algebra (2006), Cambridge: Cambridge University Press, Cambridge · Zbl 1196.11002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
