Efficient Oblivious Proofs of Correct Exponentiation

Abstract

We study the notion of meta-proofs, which, as the name indicates, are proofs about proofs. We employ the notion of meta-proofs to produce a highly efficient oblivous proof of correct exponentiation. It is minimum-knowledge independently of whether the input is valid or not, a property that does not hold for many other protocols (that are zero-knowledge only for valid inputs.) This has direct security implications to multiparty protocols, where the protocols we demonstrate — one interactive and one non-interactive — can be employed to obtain protocol robustness at a low cost. As a result of potential independent interest, we show how to turn any standard discrete log signature scheme into a scheme for proving equality of discrete logarithms. We demonstrate our method using the Schnorr signature scheme.