Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
复制标题
来自有时间限制的柯尔莫哥洛夫复杂度的亚线性时间平均情况硬度的密码学
DOI：
10.1145/3406325.3451121
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Pass, Rafael
中科院分区：
文献类型：
--
作者：
Liu, Yanyi;Pass, Rafael
设MKtP[S]是满足Kt(X)≤S(|x|)的串x的集合，其中Kt(X)表示所描述的真值表的t-有界Kolmogorov复杂性。我们的主要定理表明，对于一个适当的温和平均情形困难的概念，对于每一个ε>；0，多项式(N)≥(1+ε)n，以及每一个“好”类的超多项式函数，下列条件是等价的：(I)某些函数T∈的存在使得存在t-困难的单向函数(具有非一致安全性)；(Ii)某些函数T∈的存在使得MKtP[T−1]对于次线性时间非一致算法是温和平均情形困难的(对于某些0<具有运行时δ；δ<；1)。例如，次指数难解的存在性(分别为准多项式硬)OWF相当于MKtP[Polylogn]的温和平均硬度(分别为MKtP[2O(√Logn)])次线性时间非均匀算法。我们还注意到，如果我们想要推导出T-Hard OWF，其中安全是W.r.t.一致T-时间概率攻击者(即，一致安全的OWF)，它足以假设MKTP的次线性时间硬性。一致概率次线性时间攻击者。我们通过证明令人惊讶地接近无条件推导(一致安全的)OWF的下界来补充这一结果：MKtP[Polylogn]是最坏情况下的难W.r.t。一致概率次线性时间算法，并且MKtP[n−logn]对于ALLO(t(N)/n3)时间确定性算法是中等平均情况下的困难。
Let MKtP[s] be the set of stringsxsuch thatKt(x) ≤s(|x|), whereKt(x) denotes thet-bounded Kolmogorov complexity of the truthtable described byx. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every ε>0, polynomialt(n) ≥ (1+ε)n, and every “nice” classFof super-polynomial functions, the following are equivalent: (i) the existence of some functionT∈Fsuch thatT-hard one-way functions (OWF) exists (with non-uniform security); (ii) the existence of some functionT∈Fsuch that MKtP[T−1] is mildly average-case hard with respect to sublinear-time non-uniform algorithms (with running-timenδfor some 0<δ<1). For instance, existence of subexponentially-hard (resp. quasi-poly-nomially-hard) OWFs is equivalent to mild average-case hardness of MKtP[polylogn] (resp. MKtP[2O(√logn))]) w.r.t. sublinear-time non-uniform algorithms. We additionally note that if we want to deduceT-hard OWFs where security holds w.r.t. uniformT-time probabilistic attackers (i.e., uniformly-secure OWFs), it suffices to assume sublinear time hardness of MKtP w.r.t. uniform probabilistic sublinear-time attackers. We complement this result by proving lower bounds that come surprisingly close to what is required to unconditionally deduce the existence of (uniformly-secure) OWFs: MKtP[polylogn] is worst-case hard w.r.t. uniform probabilistic sublinear-time algorithms, and MKtP[n−logn] is mildly average-case hard for allO(t(n)/n3)-time deterministic algorithms.
登录
查看更多内容
关于派系的逼近性及相关最大化问题
DOI：
--
发表时间：
2003
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
A. Srinivasan
通讯作者：
A. Srinivasan
放大电路针对多项式时间的下限及其应用
DOI：
--
发表时间：
2013
期刊：
2012 IEEE 27th Conference on Computational Complexity
影响因子：
--
作者：
R. Lipton;Ryan Williams
通讯作者：
Ryan Williams
超越自然证据：硬度放大率和局部性
影响因子：
2.5
作者：
Chen L
通讯作者：
Chen L
DOI：
--
发表时间：
2020
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
M. Müller;J. Pich
通讯作者：
J. Pich
柯尔莫哥洛夫复杂性中的随机性和难处理性
DOI：
--
发表时间：
2019
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
I. Oliveira
通讯作者：
I. Oliveira