Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BLACK-BOX REDUCTIONS:
Reports tagged with Black-box reductions:
TR00-039 | 25th April 2000
Yevgeniy Dodis

Collective Coin-Flipping is a classical problem where n
computationally unbounded processors are trying to generate a random
bit in a setting where only a single broadcast channel is available
for communication. The protocol is said to be b(n)-resilient if any
adversary that can corrupt up to b(n) players, still cannot ... more >>>

TR07-038 | 23rd April 2007
Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

#### Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

TR08-007 | 6th February 2008

#### Limitations of Hardness vs. Randomness under Uniform Reductions

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS 98, JCSS 01) and Trevisan and Vadhan (CCC 02, CC 07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

TR11-016 | 7th February 2011
Sergei Artemenko, Ronen Shaltiel

#### Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Revisions: 1

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>

TR19-025 | 28th February 2019
Shuichi Hirahara, Osamu Watanabe

#### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Revisions: 1

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

TR20-050 | 18th April 2020
Shuichi Hirahara

#### Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing ... more >>>

TR20-094 | 24th June 2020
Ronen Shaltiel

#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>

TR20-095 | 24th June 2020
Mikito Nanashima

#### On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions

Revisions: 1

A black-box (BB) reduction is a central proof technique in theoretical computer science. However, the limitations on BB reductions have been revealed for several decades, and the series of previous work gives strong evidence that we should avoid a nonadaptive BB reduction to base cryptography on NP-hardness (e.g., Akavia et ... more >>>

ISSN 1433-8092 | Imprint