Pairing-Free Blind Signatures from Standard Assumptions in the ROM

Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first practical construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under the strong RSA assumption and DDH (in pairingfree groups). For our construction, we provide a NIZK-friendly signature based on strong RSA, and efficiently instantiate a variant of Fischlin's generic framework (CRYPTO'06). Our Blind Signature scheme has signatures of size 4.28 KB and communication cost 10.98 KB. On the way, we develop techniques that might be of independent interest. In particular, we provide efficient relaxed range-proofs for large ranges with subversion zero-knowledge and compact commitments to elements of arbitrary groups. 4 The framework of Fischlin [42] yields round-optimal blind signatures with trusted setup generically, but efficient instantiations rely either on pairings [18,4,66] or lattices [37,7]. 5 Note that due to impossibility results for round optimal blind signatures [68,43,75], the reliance on random oracles can likely not be removed efficiently. 6 In the context of signatures, an all-but-one reduction allows to puncture the verification key in such a way that all-but-one message m * can be signed and given a signature on m * , a hard problem can be solved. We refer to [72] for more details. This work 4.28 KB 10.98 KB RSA, Groups sRSA, DDH We provide signature size, communication size, the algebraic setting, and the underlying assumptions for known round-optimal blind signatures in the ROM secure under non-interactive assumptions. We stress that our work relies on assumptions in prime-order groups without pairing. ( †): Communication of [18] scales linearly with the message size, and is given here for 256 bit messages. ( † †): [54] offers tradeoffs between signature and communication sizes. Reference Sig. size Comm. size #Rounds Assumption Blind RSA and variants [28, 69, 8] 768 B 384 B 2 One-more RSA Chairattana-Apirom et al. [25] ‡ 8.66 KB 8.08 KB 5 RSA This work 4.28 KB 10.98 KB 2 sRSA, DDH We provide signature size, communication size, number of rounds and the underlying assumption of known blind signatures in the RSA setting. ( ‡): [25] is not round-optimal and at most an a-priori fixed number of signatures can be issued, here 2 30 . Also, the signer is required to keep a state and communication scales logarithmically in the number sessions in size but linearly in computation.