Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Black-box reductions:
TR00-039 | 25th April 2000
Yevgeniy Dodis

Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping

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
Dan Gutfreund, Salil Vadhan

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

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