On Multi-user Security of Schnorr Signature in Algebraic Group Model

Abstract

The security of Schnorr signature Sch has been widely discussed so far. Recently, Fuchsbauer, Plouviez and Seurin gave a tight reduction that proves EUF-CMA of Sch in the random oracle (ROM) with the algebraic group model (AGM) from the discrete logarithm (DL) assumption at EUROCRYPT 2020. Kiltz, Masny and Pan considered multi-user security of Sch at CRYPTO
2016, whereas Fuchsbauer et al. considered the single-user security only. More precisely, Kiltz et al. constructed a tight reduction from EUF-CMA to MU-EUF-CMA. Combining these two results will likely enable us to construct a tight reduction that proves MU-EUF-CMA security of Sch in AGM+ROM from DL assumption.

Against such an intuition, we show an impossibility on proving MU-EUF-CMA of Sch in AGM+ROM only by combining them in this paper. To estimate our impossibility result, we also discuss why the result by Fuchsbauer et al. cannot be applied to MU-EUF-CMA setting. Our result therefore suggests that we are required to develop a new proof technique beyond the algebraic reduction or to find a new form of public keys other than that considered in our impossibility, in order to show MU-EUF-CMA of Sch in AGM+ROM.