New proofs of (new) Direct Product Theorems.

摘要

In this Dissertation we give an alternate proof of the well known Direct Product Theorem which in contrast to the previous proofs, achieves optimal values for the related parameters. We also obtain a stronger version of the Direct Product Theorem which is motivated by some interesting applications in Cryptography.;Direct Product Theorems are formal statements of the intuition: "if solving one instance of a problem is hard, then solving multiple instances is even harder". For example, a Direct Product Theorem with respect to bounded size circuits computing a function is a statement of the form: "if a function f is hard to compute on average for small size circuits, then fk(x1, ..., x k) =def f(x1), ..., f(xk) is even harder on average for certain smaller size circuits". The proof of the such a statement is by contradiction, that is, we start with a circuit which computes fk on some non-negligible fraction of the inputs and then use this circuit to construct another circuit which computes f on almost all inputs. By viewing such a constructive proof as decoding certain error-correcting code, it was independently observed by Trevisan [Tre03] and Impagliazzo [Imp02] that constructing a single circuit is not possible in general. Instead, we can only hope to construct a list of circuits such that one of them computes f on almost all inputs. This makes the list size an important parameter of the Theorem which can be minimized. In a sequence of results [IJK06] and [IJKW08], we achieve optimal value of the list size which is a substantial improvement compared to previous proofs of the Theorem. In particular, this new version can be applied to uniform models of computation (e.g. randomized algorithms) whereas all previous versions applied only to nonuniform models (e.g. circuits). This proof is presented in Chapter III.;Consider the following stronger and a more general version of the previous Direct Product Theorem statement: "if a problem is hard to solve on average, then solving more than the expected fraction of problem instances from a pool of multiple independently chosen instances becomes even harder". Such statements are useful in cryptographic settings where the goal is to amplify the gap between the ability of legitimate users to solve a type of problem and that of attackers. We call such statements "Chernoff-type Direct Product Theorems" and prove such a statement for a very general setting in [IJK07]. This is presented in Chapter V.