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

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 also considered multi-user security of Sch at CRYPTO 2016, whereas Fuchsbauer et al. only considered single-user security. 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.