Pseudorandom functions in $ \textit{TC}^{0} $ and cryptographic limitations to proving lower bounds
Pseudorandom functions in $ \textit{TC}^{0} $ and cryptographic limitations to proving lower bounds
复制标题
$ extit{TC}^{0} $ 中的伪随机函数以及证明下界的密码限制
DOI：
10.1007/s000370100002
复制
发表时间：
2002
影响因子：
1.4
通讯作者：
S. Lucks
中科院分区：
文献类型：
--
作者：
Matthias Krause;S. Lucks
摘要：本文研究了 NC 内部的哪些复杂性类可以包含伪随机函数生成器 (PRFG)。决策下
Diffie-Hellman 假设（常见的密码学假设） $ \textit{TC}^{0} $4 包含 PRFG。没有具有此属性的较低复杂性类
目前已知。另一方面，我们使用有效的降低
绑定参数以表明某些复杂性类不能包含
PRFG。这为以下猜想提供了证据：任何有效的
复杂性类别的下界参数可以变成
一种有效的区分算法，证明此类不能
Abstract.This paper investigates which complexity classes inside NCcan contain pseudorandom function generators (PRFGs). Under the Decisional
Diffie-Hellman assumption (a common cryptographic assumption) $ \textit{TC}^{0} $4 contains PRFGs. No lower complexity classes with this property
are currently known. On the other hand, we use effective lower
bound arguments to show that some complexity classes cannot contain
PRFGs. This provides evidence for the following conjecture: Any effective
lower bound argument for a complexity class can be turned into
an efficient distinguishing algorithm which proves that this class cannot