[Taler] Clause blind Schnorr signatures

[Jeff Burdges]

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.  


[1]  Security of Blind Discrete Log Signatures against Interactive Attacks by 
Claus Peter Schnorr (2001).  
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.85

Introduces the ROS problem and proves blind Schnorr signatures are secure if 
and only if the ROS problem is intractib.e


[2]  A Generalized Birthday Problem  by  David Wagner (2002).  
https://people.eecs.berkeley.edu/~daw/papers/genbday.html

Shows an algorithm subexponential in sessions for the ROS problem, which breaks 
blind Schnor signatures by [1] using realistic compute resources.  At least 
Florian Dold if not others here knew this much of the story.


[3] On the (in)security of ROS  by  Fabrice Benhamouda, Tancrede Lepoint, 
Julian Loss, Michele Orru, and Mariana Raykova (2020).   
https://eprint.iacr.org/2020/945

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 
https://www.math.uni-frankfurt.de/~dmst/teaching/SS2012/Vorlesung/EBS5.pdf


[4]  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 [2] with realistic compute resources.  [3] makes the 
compute resources negligible using 256-ish sessions.  Three round trip Schnorr 
multi-signatures remained secure here.


[5]  Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic 
Group Model  by  Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin (2019). 
 https://eprint.iacr.org/2019/877

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.


[6]  Two-round trip Schnorr multi-signatures via delinearized witnesses  by  
Handan Kilinc Alper and Jeffrey Burdges (2020). 
https://eprint.iacr.org/2020/1245/20201009:113646
[7]  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 [6] in the version accepted by CRYPTO, 
so I envision doing another version of [6] closer to the older copy linked 
above.  In this, I’d unify [5] and [6] 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 [5] 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  
https://eprint.iacr.org/2020/859 

There is nothing wrong with producing a Taler fork that uses only [5] 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. 

Best,
Jeff