(2026-01) Round-Optimal Pairing-Free Blind Signatures
2026-01-20
We present the first practical, round-optimal blind signatures in pairing-free groups.
We build on the Fischlin paradigm (EUROCRYPT 2007) where a first signature is computed on a commitment to the message and the final signature is a zero-knowledge proof of the first signature. We use the Nyberg-Rueppel signature scheme as the basis (CCS 1993), it is a well-studied scheme with a verification equation that is sufficiently algebraic to allow efficient proofs, that do not need to make non-black box use of a random oracle. Our construction offers flexibility for trade-offs between underlying assumptions and supports issuance of signatures on vectors of attributes making it suitable for use in anonymous credential systems.
As a building block, we show how existing NIZKs can be modified to allow for straight-line extraction. We implement variants of our construction to demonstrate its practicality, varying the choice of elliptic curve and the proof system used to compute the NIZK. With conservative parameters (NIST-P256 and SHA-256) and targeting short proofs, signatures are 1349 bytes long, and on a typical laptop can be generated in under 500ms and verified in under 100ms.