Limits of provable security from standard assumptions
Rafael Pass · 2011
We show that the security of some well-known cryptographic protocols, primitives and as-sumptions (e.g., the Schnorr identification scheme, commitments secure under adaptive selective-decommitment, the “one-more ” discrete logarithm assumption) cannot be based on any standard assumption using a Turing (i.e., black-box) reduction. These results follow from a general result showing that Turing reductions cannot be used to prove security of constant-round sequentially witness-hiding special-sound protocols for unique witness relations, based on standard assump-tions; we emphasize that this result holds even if the protocol makes non-black-box use of the underlying assumption.