The Analysis of Schnorr Multi-Signatures and the Application to AI

Artificial intelligence (AI) is having a profound impact on our daily lives. We suggest using digital signatures to protect the user’s identity and achieve data accountability. To address high-risk applications, multi-signatures are expected to play an important role in AI. MuSig2 by Nick et al. is an efficient and secure Schnorr multi-signature scheme. MuSig2 implements signature aggregation and key aggregation, and MuSig2 is reduced to the One-More Discrete Logarithms (OMDL) problem in the random oracle model. This comes at the cost that the signer needs four nonces instead of one nonce for each signature. However, MuSig2 ignores the change of nonces in the forking lemma, which leads to the signer signature requiring too many nonces, and makes the proof of the scheme complicated. In this paper, we reduce the number of nonces from 4 to 2 and simplify the security proof of the MuSig2 scheme in the random oracle model. Then by reducing the security requirement slightly, we achieve the MuSig2 scheme’s security when the nonces are reused. Finally, we utilize the proof technology of MuSig2 to reduce the MSDL (Discrete-Logarithm based Multi-Signature) scheme by Boneh et al. to the OMDL assumption.