Charanjit Jutla

Almost Optimal Bounds for Direct Product Threshold Theorem

AUTHORS: Charanjit Jutla

We consider weakly-verifiable puzzles which are challenge-response
puzzles such that the responder may not be able to verify for itself
whether it answered the challenge correctly. We consider $k$-wise
direct product of such puzzles, where now the responder has to solve
$k$ puzzles chosen independently in parallel. Canetti et al have
earlier shown that such direct product puzzles have a hardness which
rises exponentially with $k$. In the threshold case addressed in
Impagliazzo et al, the responder is required to answer correctly a
fraction of challenges above a threshold. The bound on hardness of
this threshold parallel version was shown to be similar to Chernoff
bound, but the constants in the exponent are rather weak. Namely,
Impagliazzo et al show that for a puzzle for which probability of
failure is $\delta$, the probability of failing on less than
$(1-\gamma)\delta k$ out of $k$ puzzles, for any parallel strategy, is
at most $e^{-\gamma2\delta k/40}$.

In this paper, we develop new techniques to bound this probability,
and show that it is arbitrarily close to Chernoff bound. To be
precise, the bound is $e^{-\gamma2(1-\gamma^d) \delta k/2}$, for any
positive integer d. We show that given any responder that solves $k$
parallel puzzles with a good threshold, there is a uniformized
parallel solver who has the same threshold of solving $k$ parallel
puzzles, while being oblivious to the permutation of the puzzles. This
enhances the analysis considerably, and may be of independent


[Jut10]: http://www.eccc.uni-trier.de/report/2009/120/