论文标题
在单向功能和Kolmogorov的复杂性上
On One-way Functions and Kolmogorov Complexity
论文作者
论文摘要
我们证明，计算理论中两个基本问题的等效性。对于每个多项式$ t（n）\ geq（1+ \ varepsilon）n，\ varepsilon> 0 $，以下是等效的： - 单向函数存在（反过来相当于存在安全的私钥加密方案，数字签名，伪随机生成器，伪随机函数，承诺方案等）； - $ t $ - 时间有限的kolmogorov复杂性，$ k^t $是温和的平均水平（即，存在一个多项式$ p（n）> 0 $，因此没有PPT算法可以计算$ k^t $，以比$ 1- \ frac {1}} $ n $ n $ n $ n $ k^t $。 在此过程中，我们提出了第一个自然且经过深思熟虑的计算问题，这些问题表征了中央私钥原语和密码学方案的可行性。
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial $t(n)\geq (1+\varepsilon)n, \varepsilon>0$, the following are equivalent: - One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); - $t$-time bounded Kolmogorov Complexity, $K^t$, is mildly hard-on-average (i.e., there exists a polynomial $p(n)>0$ such that no PPT algorithm can compute $K^t$, for more than a $1-\frac{1}{p(n)}$ fraction of $n$-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.
