Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 12/2021

20-10-2021

Pseudorandom functions in NC class from the standard LWE assumption

Authors: Yiming Li, Shengli Liu, Shuai Han, Dawu Gu

Published in: Designs, Codes and Cryptography | Issue 12/2021

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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 Kim (Eurocrypt 2020) and Lai et al. (PKC 2020) 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 (Crypto 2015), Lai et al.’s PRF circuit 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 are 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+\epsilon }\) 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.
previous article An improved degree evaluation method of NFSR-based cryptosystems
next article Existence of primitive normal pairs with one prescribed trace over finite fields
Appendix
Available only for authorised users
Footnotes
1
\({\widehat{\mathsf {PRF}}}_{\mathsf {gSyn}}\) is constructed from multiple subcomponents \({\widetilde{\mathsf {PRF}}}_{\mathsf {gSyn}}\) with moduli ranging from \(\lambda ^{c}\) to \(2^{\omega (\log \lambda )}\) for some constant c. We stress that the security of \({\widehat{\mathsf {PRF}}}_{\mathsf {gSyn}}\) is only reduced to the security of those \({\widetilde{\mathsf {PRF}}}_{\mathsf {gSyn}}\) with polynomial moduli, which is in turn based on the standard LWE assumption.
 
2
Note that [5] contains a “direct” PRF construction which can be implemented in \(NC^1\) via pre-processing but requires an exponential modulus. Without pre-processing, this PRF is in \(NC^2\) as noted in [15].
 
3
We note that there exists universal hash \(\textsf {UH}:{\mathbb {Z}}_p^{{\bar{u}}}\rightarrow {\mathbb {Z}}_{q}^{{\hat{u}}}\) for arbitrary q, as shown in [17]. Hence it is possible for us to construct \(\mathsf {PRG}_{\mathsf {LWE}}[{\mathbb {Z}}_p^n,{\mathbb {Z}}_q^{{\hat{u}}}]\) for arbitrary q.
 
4
If \(\ell \) is not a power of 2, we can pad \({\mathbf {x}}\in \{0,1\}^{\ell }\) to \({\mathbf {x}}'\in \{0,1\}^{2^d}\) with \(d:=\lceil \log \ell \rceil \) by any padding strategy, and then evaluate the PRF on \({\mathbf {x}}'\). For example, we can set \(x'_i=x_{(i\mod \ell )}\) for \(i\in [0,2^d-1]\) or just set \({\mathbf {x}}'={\mathbf {x}}\Vert 0\cdots 0\).
 
Literature
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).
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.
3.
4.
Banerjee A., Peikert C.: New and improved key-homomorphic pseudorandom functions. In: Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Part I.
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.
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.
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.
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).
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.
10.
Canetti R., Chen Y.: Constraint-hiding constrained prfs for nc\({}^{\text{1}}\) from LWE. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International.
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).
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).
13.
Goldreich O., Silvio Micali S.G.: How to construct random functions. J. ACM (1986).
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.
15.
Kim S.: Key-homomorphic pseudorandom functions from LWE with small modulus. In: Advances in Cryptology—EUROCRYPT 2020—39th Annual International, Part II.
16.
Laarhoven T., Mosca M., van de Pol J.: Finding shortest lattice vectors faster using quantum search. Des. Codes Cryptogr. 77, 375–400 (2015).MathSciNetCrossRef
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.
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).
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).MathSciNetCrossRef
20.
Peikert C.: A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science (2016).
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).
22.
Rudich S., Wigderson A. (eds.): Computational Complexity Theory, IAS / Park City Mathematics Series, vol. 10. AMS Chelsea Publishing, New York (2004).
23.
Schnorr C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201–224 (1987).MathSciNetCrossRef
24.
Shoup V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, Cambridge (2006).MATH
Metadata
Title
Pseudorandom functions in NC class from the standard LWE assumption
Authors
Yiming Li
Shengli Liu
Shuai Han
Dawu Gu
Publication date
20-10-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 12/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00955-8

Other articles of this Issue 12/2021

Designs, Codes and Cryptography 12/2021 Go to the issue

OriginalPaper

An improved degree evaluation method of NFSR-based cryptosystems

OriginalPaper

Bounds for flag codes

OriginalPaper

Binomial permutations over finite fields with even characteristic

OriginalPaper

Binary signed-digit integers and the Stern diatomic sequence

OriginalPaper

On security properties of all-or-nothing transforms

OriginalPaper

Walsh spectrum and nega spectrum of complementary arrays

Premium Partner

    Image Credits