Basing PRFs on Constant-Query Weak PRFs: Minimizing Assumptions for Efficient Symmetric Cryptography
Basing PRFs on Constant-Query Weak PRFs: Minimizing Assumptions for Efficient Symmetric Cryptography
复制标题
基于恒定查询弱 PRF 的 PRF：最小化高效对称密码学的假设
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Stefano Tessaro
中科院分区：
文献类型：
--
作者：
U. Maurer;Stefano Tessaro
虽然众所周知，所有基本的私钥密码原语都可以从单向函数构建，但找到这些原语的实际实现所基于的弱假设仍然是一项具有挑战性的任务。为了实现这一目标，本文介绍了一个恒定的查询弱PRF的概念，一个函数与一个秘密的密钥，这是计算上无法区分从一个真正的随机函数时，在一个常数s的已知随机输入，其中s可以小到两个。
我们提供迭代构造（任意输入长度）的PRF从恒定查询弱PRF，甚至提高效率的基础上更强的假设弱PRF（多项式许多评价是允许的）以前的建设。
我们的构造之一直接提供了一种新的操作模式，使用恒定查询弱PRF的IND-CPA对称加密，这基本上是有效的传统的基于PRF的计数器模式加密。此外，我们的构造产生了有效的操作模式，用于加密散列函数（如MD5和SHA-1）以获得迭代的PRF（因此MAC），其仅依赖于基础压缩函数是恒定查询弱PRF的假设，这是在此上下文中考虑过的最弱假设。
Although it is well known that all basic private-key cryptographic primitives can be built from one-way functions, finding weak assumptions from which practical implementations of such primitives exist remains a challenging task. Towards this goal, this paper introduces the notion of a constant-query weak PRF , a function with a secret key which is computationally indistinguishable from a truly random function when evaluated at a constant number s of known random inputs, where s can be as small as two.
We provide iterated constructions of (arbitrary-input-length) PRFs from constant-query weak PRFs that even improve the efficiency of previous constructions based on the stronger assumption of a weak PRF (where polynomially many evaluations are allowed).
One of our constructions directly provides a new mode of operation using a constant-query weak PRF for IND-CPA symmetric encryption which is essentially as efficient as conventional PRF-based counter-mode encryption. Furthermore, our constructions yield efficient modes of operation for keying hash functions (such as MD5 and SHA-1) to obtain iterated PRFs (and hence MACs) which rely solely on the assumption that the underlying compression function is a constant-query weak PRF, which is the weakest assumption ever considered in this context.