Towards Non-Black-Box Lower Bounds in Cryptography

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.

Provided by: Cornell University Topic: Security Date Added: Jan 2011 Format: PDF

Find By Topic