Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR09-120 | 29th August 2012 23:05

Almost Optimal Bounds for Direct Product Threshold Theorem

RSS-Feed




Revision #2
Authors: Charanjit Jutla
Accepted on: 29th August 2012 23:05
Downloads: 738
Keywords: 


Abstract:

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^{-\gamma^2\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^{-\gamma^2(1-\gamma) \delta k/2}$. 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 interest.



Changes to previous version:

Does not need Stirling's approximation in the proof anymore.


Revision #1 to TR09-120 | 4th January 2010 17:28

Almost Optimal Bounds for Direct Product Threshold Theorem





Revision #1
Authors: Charanjit Jutla
Accepted on: 4th January 2010 17:28
Downloads: 1285
Keywords: 


Abstract:

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^{-\gamma^2\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^{-\gamma^2(1-\gamma) \delta k/2}$. 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 interest.



Changes to previous version:

Better Bounds, especially for gamma -> 1 .


Paper:

TR09-120 | 18th November 2009 05:34

Almost Optimal Bounds for Direct Product Threshold Theorem





TR09-120
Authors: Charanjit Jutla
Publication: 20th November 2009 14:53
Downloads: 1702
Keywords: 


Abstract:

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^{-\gamma^2\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^{-\gamma^2(1-\gamma) \delta k/2}$. 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 interest.



ISSN 1433-8092 | Imprint