On the Possibility of Basing Cryptography on EXP != BPP
On the Possibility of Basing Cryptography on EXP != BPP
复制标题
关于基于 EXP != BPP 的密码学的可能性
DOI：
10.1007/978-3-030-84242-0_2
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rafael Pass
中科院分区：
文献类型：
--
作者：
Yanyi Liu;Rafael Pass
Liu和Pass（FOCS'20）最近证明了单向函数（OWF）的存在性与时间有界Kolmogorov复杂性问题的温和平均情况硬度之间的等价性。在这项工作中，我们建立了一个类似的等价关系，但与时间有界柯尔莫哥洛夫复杂性的不同形式--即莱文的柯尔莫哥洛夫复杂性概念--其难度与是否问题密切相关。更详细地说，letKt（x）表示字符串x的Levin-Kolmogorov复杂度;即， K 不 ( X ) = min Π ∈ { 0 , 1 } ∗ , 不 ∈ N { | Π | + ⌈ 日志 不 ⌉ : U ( Π , 1 不 ) = X } 其中U是一个通用图灵机，并且表示第t步迭代的输出，并且表示具有以下性质的对（x，k）的语言。我们证明：（即，是无限经常的双侧错误轻度平均情况困难）当且仅当无限经常存在OWF。(i.e.,是无限-经常错误的轻度平均情况困难），如果。因此，唯一的“差距”，（无限-经常）OWF从假设，即看似“小”的技术差距之间的双边错误和错误的平均情况下的困难的问题。作为一个推论，这一结果，我们还证明，任何减少从无误差到双边误差平均情况下的硬度意味着最后，我们考虑其他替代概念的Kolmogorov复杂性，包括空间有界的Kolmogorov复杂性和条件Kolmogorov复杂性，并显示如何平均情况下的硬度与他们相关的问题的特征对数空间可计算的OWF，或OWF中。
Liu and Pass (FOCS’20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity—namely, Levin’s notion of Kolmogorov Complexity—whose hardness is closely related to the problem of whether. In more detail, letKt(x) denote the Levin-Kolmogorov Complexity of the stringx; that is, K t ( x ) = min Π ∈ { 0 , 1 } ∗ , t ∈ N { | Π | + ⌈ log t ⌉ : U ( Π , 1 t ) = x } , whereUis a universal Turing machine, anddenotes the output of the programaftertsteps, and letdenote the language of pairs (x,k) having the property that. We demonstrate that:(i.e.,is infinitely-oftentwo-sided errormildly average-case hard) iff infinitely-often OWFs exist.(i.e.,is infinitely-oftenerrorlessmildly average-case hard) iff.Thus, the only “gap” towards getting (infinitely-often) OWFs from the assumption thatis the seemingly “minor” technical gap between two-sided error and errorless average-case hardness of theproblem.As a corollary of this result, we additionally demonstrate that any reduction from errorless to two-sided error average-case hardness forimplies (unconditionally) that.We finally consider other alternative notions of Kolmogorov complexity—including space-bounded Kolmogorov complexity and conditional Kolmogorov complexity—and show how average-case hardness of problems related to them characterize log-space computable OWFs, or OWFs in.