Provided by: Cornell University
Date Added: Jan 2011
In the past four decades, many cryptographic tasks have been put under rigorous treatment in an effort to realize these tasks under minimal assumptions. The authors consider average-case strengthening's of the traditional assumption that coNP is not contained in AM. Under these assumptions, they rule out generic and potentially non-black-box constructions of various cryptographic primitives (e.g., one-way permutations, collision-resistant hash-functions, constant-round statistically hiding commitments, and constant-round black-box zero-knowledge proofs for NP) from one-way functions, assuming the security reductions are black-box.