All reports by Author Rafael Pass:

__
TR24-095
| 23rd May 2024
__

Yanyi Liu, Noam Mazor, Rafael Pass#### A Note on Zero-Knowledge for NP and One-Way Functions

Revisions: 1

__
TR24-055
| 12th March 2024
__

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass#### Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

__
TR24-053
| 10th March 2024
__

Noam Mazor, Rafael Pass#### Gap MCSP is not (Levin) NP-complete in Obfustopia

Revisions: 1

__
TR24-051
| 5th March 2024
__

Yanyi Liu, Rafael Pass#### A Direct PRF Construction from Kolmogorov Complexity

__
TR24-003
| 2nd January 2024
__

Noam Mazor, Rafael Pass#### Search-to-Decision Reductions for Kolmogorov Complexity

Revisions: 1

__
TR23-211
| 23rd December 2023
__

Rafael Pass, Oren Renard#### Characterizing the Power of (Persistent) Randomness in Log-space

__
TR23-192
| 28th November 2023
__

Noam Mazor, Rafael Pass#### A Note On the Universality of Black-box MKtP Solvers

Revisions: 1

__
TR23-175
| 15th November 2023
__

Noam Mazor, Rafael Pass#### The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False

__
TR23-152
| 14th October 2023
__

Yanyi Liu, Rafael Pass#### One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

__
TR23-143
| 22nd September 2023
__

Noam Mazor, Rafael Pass#### Counting Unpredictable Bits: A Simple PRG from One-way Functions

Revisions: 3

__
TR23-103
| 12th July 2023
__

Yanyi Liu, Rafael Pass#### On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

Revisions: 1

Yanyi Liu, Noam Mazor, Rafael Pass

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be ... more >>>

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption---the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity.

Roughly speaking, the ...
more >>>

Noam Mazor, Rafael Pass

We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions.

In more detail:

- Assuming the existence of indistinguishability obfuscation, and ...
more >>>

Yanyi Liu, Rafael Pass

While classic result in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.

Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various ... more >>>

Noam Mazor, Rafael Pass

A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

In this work, we ... more >>>

Rafael Pass, Oren Renard

We study the problem of whether \emph{persistent} randomness is helpful for polynomial-time algorithms that only use \emph{logarithmic} space. In more detail, we consider the class $\searchBPLs$, of \emph{search}-problems that are solvable by a polynomial-time Probabilistic Logspace TMs with \emph{2-way} access (i.e., with multiple, as opposed to one-time, access) to a ... more >>>

Noam Mazor, Rafael Pass

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function ... more >>>

Noam Mazor, Rafael Pass

The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ? = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded ... more >>>

Yanyi Liu, Rafael Pass

Consider the recently introduced notion of \emph{probabilistic

time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,

CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.

We show the equivalence of the following:

- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable

distribution $\D$;

- ...
more >>>

Noam Mazor, Rafael Pass

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both ... more >>>

Yanyi Liu, Rafael Pass

Whether one-way functions (OWF) exist is arguably the most important

problem in Cryptography, and beyond. While lots of candidate

constructions of one-way functions are known, and recently also

problems whose average-case hardness characterize the existence of

OWFs have been demonstrated, the question of

whether there exists some \emph{worst-case hard problem} ...
more >>>