Cryptology ePrint Archive: Report 2020/1245

Two-round trip Schnorr multi-signatures via delinearized witnesses

Handan Kilinc Alper and Jeffrey Burdges

Abstract: We introduce a new m-entwined ROS problem that tweaks a random inhomogeneities in an overdetermined solvable system of linear equations (ROS) problem in a scalar field using an associated group. We prove hardness of the 2-entwined ROS-like problem in AGM plus ROM, assuming DLOG hardness in the associated group.

Assuming AGM plus ROM plus KOSK and OMDL, we then prove security for a two-round trip Schnorr multi-signature protocol DWMS that creates its witness aka nonce by delinearizing two pre-witnesses supplied by each signer.

At present, DWMS and MuSig-DN are the only known provably secure two-round Schnorr multi-signatures, or equivalently threshold Schnorr signatures.

Category / Keywords: public-key cryptography / digital signatures, multi-signatures, Schnorr signatures,

Date: received 8 Oct 2020

Contact author: burdges at gnunet org

Available format(s): PDF | BibTeX Citation

Version: 20201009:113646 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]