Limits on the Power of Zero-Knowledge Proofs in Cryptographic Constructions
A central goal of theoretical cryptography is to explore relationships between various cryptographic primitives and, in particular, to show constructions of various \"High-level\" cryptographic objects (encryption schemes, key-agreement protocols, etc.) based on \"Low-level\" cryptographic tools (such as one-way functions). For over 20 years, black-box impossibility results have been used to argue the infeasibility of constructing certain cryptographic primitives (e.g., key agreement) from others (e.g., one-way functions). A widely recognized limitation of such impossibility results, however, is that they say nothing about the usefulness of (known) nonblack-box techniques. This is unsatisfying, as the authors would at least like to rule out constructions using the set of techniques they have at their disposal.