[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Taler] Clause blind Schnorr signatures
[Taler] Clause blind Schnorr signatures
Tue, 28 Sep 2021 10:46:47 +0200
I’ve remarked about blind Schnorr several times over the years on the Taler
list, but appears people were interested in implementing blind Schnorr, but did
not know the relevant literature.
tl;dr. There exist bad attacks upon all naive signing protocols employing
interactive nonce creation for Schnorr signatures, like blind Schnorr and
Schnorr multi-signatures. All these attacks work because signers have multiple
signing sessions open simultaneously, which admits finding relationships among
the challenge hashes. All have specific simple but nolonger naive altered
signing protocols that disrupt the simultaneous sessions and have security
proofs in the algebraic group model (AGM), but with additional assumptions in
the blind case.
 Security of Blind Discrete Log Signatures against Interactive Attacks by
Claus Peter Schnorr (2001).
Introduces the ROS problem and proves blind Schnorr signatures are secure if
and only if the ROS problem is intractib.e
 A Generalized Birthday Problem by David Wagner (2002).
Shows an algorithm subexponential in sessions for the ROS problem, which breaks
blind Schnor signatures by  using realistic compute resources. At least
Florian Dold if not others here knew this much of the story.
 On the (in)security of ROS by Fabrice Benhamouda, Tancrede Lepoint,
Julian Loss, Michele Orru, and Mariana Raykova (2020).
Shows an algorithm polynomial in sessions for the ROS problem, which breaks
blind Schnor signatures using negligible compute resources and 256-ish
sessions. I forget if it breaks earlier weaker proposals for fixes to Schnorr
blind signatures like
 On the Security of Two-Round Multi-Signatures by Manu Drijvers, Kasra
Edalatnejad, Bryan Ford, Eike Kiltz, Julian Loss, Gregory Neven, and Igors
Stepanovs (2018). https://eprint.iacr.org/2018/417
Breaks two round trip Schnorr multi-signature proposals across like 13 papers
by numerous authors using  with realistic compute resources.  makes the
compute resources negligible using 256-ish sessions. Three round trip Schnorr
multi-signatures remained secure here.
 Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic
Group Model by Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin (2019).
Introduces a modified ROS problem and proves security of a new Clause blind
Schnorr signing protocol assuming hardness of the one-mode discrete logarithm
(OMDL) and modified ROS problems and working in the algebraic group model
(AGM), a relative of the generic group model (GGM). In brief, you run two
independent sessions for the first round trip during each signing session, but
then the signer randomly aborts one session before the second round trip.
 Two-round trip Schnorr multi-signatures via delinearized witnesses by
Handan Kilinc Alper and Jeffrey Burdges (2020).
 MuSig2: Simple Two-Round Schnorr Multi-Signatures by Jonas Nick and Tim
Ruffing and Yannick Seurin (2020)
We both prove that using two nonces during the first round trip which signers
then delinearize during the second round trip yields a secure multi-signature
protocol, assuming OMDL and working in AGM. There is also the FROST paper
whihc proposes the same signing protocol, but lacks serious security arguments
and proposes dangerously sloppy handling for nonces.
I’m afraid my co-author kinda messed up  in the version accepted by CRYPTO,
so I envision doing another version of  closer to the older copy linked
above. In this, I’d unify  and  so that we have blind multi-signatures.
I’d also show the result for implicit/adaptor certificates, which gives new
crypto for Taler that requires only like 96 bytes per coin, plus denomination
info, as opposed to the 150 bytes for blind Schnorr signing regular Schnorr.
Avoiding, minimizing, or proving intractability of the modified ROS assumption
in  is a major open question, which deserves more careful attention. There
are three recent papers by Balthazar Bauer and Georg Fuchsbauer and others that
maybe relevant to this open problem or even my new Taler crypto proposal, not
sure yet. https://eprint.iacr.org/2021/866 https://eprint.iacr.org/2020/1400
There is nothing wrong with producing a Taler fork that uses only  but not
my new Taler crypto proposal, because much of the work of either is adding the
extra round trip, but maybe just implementing the new Taler crypto proposal is
not too hard either if one omits threshold signing.
|[Prev in Thread]
||[Next in Thread]|
- [Taler] Clause blind Schnorr signatures,
Jeff Burdges <=