Towards Non-Black-Box Lower Bounds in Cryptography

Provided by: Cornell University
Topic: Security
Format: PDF
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.

Find By Topic