Impossibility of the Provable Security of the Schnorr Signature from the One-More DL Assumption in the Non-programmable Random Oracle Model

摘要

The security of the Schnorr signature was widely discussed. In the random oracle model (ROM), it is provable from the DL assumption, whereas there is a negative circumstantial evidence in the standard model. Fleischhacker, Jager and Schroder showed that the tight security of the Schnorr signature is improvable from a strong cryptographic assumption, such as the One-more DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight and non-restricted Turing reduction.