Simple and More Efficient PRFs with Tight Security from LWE and Matrix-DDH
Simple and More Efficient PRFs with Tight Security from LWE and Matrix-DDH
复制标题
DOI：
10.1007/978-3-030-03332-3_18
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Tibor Jager;Rafael Kurek;Jiaxin Pan
中科院分区：
文献类型：
--
作者：
Tibor Jager;Rafael Kurek;Jiaxin Pan
我们构造了仅有对数安全损失和短密钥的高效且紧安全的伪随机函数。这产生了非常简单和有效的著名建筑的变体，包括Naor-Reingold(FOCS 1997)和Lewko-Waters(ACM CCS 2009)。最重要的是，结合Banerjee，Peikert和Rosen(Eurocrypt 2012)的构造，我们从一个模比原构造小得多的弱LWE假设中得到了目前最有效的基于LWE的PRF。与之前唯一具有此性质的构造相比，由于Dötting和Schröder(密码2015)，我们使用类似大小的模，但仅使用底层PRF的单个实例，而不是并行实例，其中是安全参数。像Dötting和Schröder一样，我们的安全证明几乎是后置的，因为对手发出的查询数量及其优势必须是先验知道的。从技术上讲，我们引入了全前缀通用散列函数(APUHF)，这是(几乎)通用的散列函数，即使考虑输出的任何前缀也是如此。我们给出了简单而非常有效的APUHFs的构造，并展示了它们如何与Boneh等人(ACM CCS 2010)的增强级联相结合来获得我们的结果。在这一过程中，我们发展了一种新的、更直接的方法来证明基于增强级联的PRF的安全性。
We construct efficient and tightly secure pseudorandom functions (PRFs) with only logarithmic security loss and short secret keys. This yields very simple and efficient variants of well-known constructions, including those of Naor-Reingold (FOCS 1997) and Lewko-Waters (ACM CCS 2009). Most importantly, in combination with the construction of Banerjee, Peikert and Rosen (EUROCRYPT 2012) we obtain the currently most efficient LWE-based PRF from a weak LWE-assumption with a much smaller modulus than the original construction. In comparison to the only previous construction with this property, which is due to Döttling and Schröder (CRYPTO 2015), we use a modulus of similar size, but only a single instance of the underlying PRF, instead of parallel instances, where is the security parameter. Like Döttling and Schröder, our security proof is only almost back-box, due to the fact that the number of queries made by the adversary and its advantage must be known a-priori. Technically, we introduce all-prefix universal hash functions (APUHFs), which are hash functions that are (almost-) universal, even if any prefix of the output is considered. We give simple and very efficient constructions of APUHFs, and show how they can be combined with the augmented cascade of Boneh et al.(ACM CCS 2010) to obtain our results. Along the way, we develop a new and more direct way to prove security of PRFs based on the augmented cascade.