Paper 2017/045

Efficient Round-Optimal Blind Signatures in the Standard Model

Essam Ghadafi

Abstract

Blind signatures are at the core of e-cash systems and have numerous other applications. In this work we construct efficient blind and partially blind signature schemes over bilinear groups in the standard model. Our schemes yield short signatures consisting of only a couple of elements from the shorter source group and have very short communication overhead consisting of $1$ group element on the user side and $3$ group elements on the signer side. At $80$-bit security, our schemes yield signatures consisting of only $40$ bytes which is $67\mathrm{\%}$ shorter than the most efficient existing scheme with the same security in the standard model. Verification in our schemes requires only a couple of pairings. Our schemes compare favorably in every efficiency measure to all existing counterparts offering the same security in the standard model. In fact, the efficiency of our signing protocol as well as the signature size compare favorably even to many existing schemes in the random oracle model. For instance, our signatures are shorter than those of Brands' scheme which is at the heart of the U-Prove anonymous credential system used in practice. The unforgeability of our schemes is based on new intractability assumptions of a ``one-more'' type which we show are intractable in the generic group model, whereas their blindness holds w.r.t.~malicious signing keys in the information-theoretic sense. We also give variants of our schemes for a vector of messages.

Note: In the previous version of the paper we were giving the redundant vector $$ as part of the partially blind signature verification key which was causing a problem. We made slight changes to the proof of the partially blind scheme whose unforgeability now reduces to slightly different assumptions from those of the blind schemes.