Rerandomizable threshold blind signatures

This paper formalizes the concept of threshold blind signatures (TBS) that bridges together properties of the two well-known signature flavors, blind signatures and threshold signatures. Using TBS users can obtain signatures through interaction with t-out-of-n signers without disclosing the corresponding message to any of them. Our construction is the first TBS scheme that achieves security in the standard model and enjoys the property of being rerandomizable. The security of our construction holds according to most recent security definitions for blind signatures by Schröder and Unruh (PKC 2012) that are extended in this work to the threshold setting. Rerandomizable TBS schemes enable constructions of distributed e-voting and e-cash systems. We highlight how TBS can be used to construct the first e-voting scheme that simultaneously achieves privacy, soundness, public verifiability in the presence of distributed registration authorities, following the general approach by Koenig, Dubuis, and Haenni (Electronic Voting 2010), where existence of TBS schemes was assumed but no construction given. As a second application, we discuss how TBS can be used to distribute the currency issuer role amongst multiple parties in a decentralized e-cash system proposed by Miers et al.(IEEE S&P 2013).