文章基本信息

标题：On the Possibility of Basing Cryptography on\EXP=\BPP
本地全文：下载
作者：Yanyi Liu ; Rafael Pass
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：ay 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 EXP 6 = BPP. In more detail, let Kt(x) denote the Levin-Kolmogorov Complexity of the string x; that is, Kt(x) = minΠ∈{0,1}∗,t∈N{|Π|+d log te : U(Π, 1t ) = x}, where U is a universal Turing machine, and U(Π, 1t ) denotes the output of the program Π after t steps, and let MKtP denote the language of pairs (x, k) having the property that Kt(x) ≤ k. We demonstrate that: • MKtP /∈ HeurnegBPP (i.e., MKtP is infinitely-often two-sided error mildly average-case hard) iff infinititely-often OWFs exist. • MKtP /∈ AvgnegBPP (i.e., MKtP is infinitely-often errorless mildly average-case hard) iff EXP 6 = BPP. Thus, the only “gap” towards getting (infinitely-often) OWFs from the assumption that EXP 6 = BPP is the seemingly “minor” technical gap between two-sided error and errorless average-case hardness of the MKtP problem. As a corollary of this result, we additionally demonstrate that any reduction from errorless to two-sided error average-case hardness for MKtP implies (uncon?ditionally) that NP 6 = P. 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 NC.
关键词：average case complexity;Kolmogorov complexity;one-way function