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.

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

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.

Better Bounds, especially for gamma -> 1 .

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.