Pseudorandom functions in NC class from the standard LWE assumption
Pseudorandom functions in NC class from the standard LWE assumption
复制标题
DOI：
10.1007/s10623-021-00955-8
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Yiming Li;Shengli Liu;Shuai Han;Dawu Gu
中科院分区：
文献类型：
--
作者：
Yiming Li;Shengli Liu;Shuai Han;Dawu Gu
标准的带误差学习（LWE）问题与多项式模相关，这意味着对量子或经典算法的指数硬度。然而，大多数现有的基于LWE的PRF方案需要超多项式甚至指数模。Kim（Eurocrypt 2020）和Lai等人（PKC 2020）最近的工作从标准LWE（即，多项式模的LWE）假设。然而，它们的PRF不能在NC电路中实现。在Döttling-Schröder（DS）范式（Crypto 2015）的帮助下，Lai等人的脉冲重复频率电路可以压缩到。在本文中，我们专注于从标准的LWE假设构建浅电路实现的PRF。为此，我们提出了三种PRF方案。前两种方案由广义伪随机合成器（gSYN）和伪随机发生器（PRG）构成，分别可以在和中实现。同时，这两个PRF的安全性是基于标准的LWE假设，但只允许来自对手的有界查询。然后，我们应用DS范式我们的PRF电路类，它不仅依赖于标准的LWE假设，但也支持无界查询得到第三个PRF计划。与现有的标准LWE的PRF相比，我们的第三PRF具有最浅的电路。
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 towith. 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 inandrespectively. 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 classwith, 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.