Paper 2017/905

Shorter Ring Signatures from Standard Assumptions

Alonso González

Abstract

Ring signatures, introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), allow to sign a message on behalf of a set of users while guaranteeing authenticity and anonymity. Groth and Kohlweiss (EUROCRYPT 2015) and Libert et al. (EUROCRYPT 2016) constructed schemes with signatures of size logarithmic in the number of users. An even shorter ring signature, of size independent from the number of users, was recently proposed by Malavolta and Schroder (ASIACRYPT 2017). However, all these short signatures are obtained relying on strong and controversial assumptions. Namely, the former schemes are both proven secure in the random oracle model while the later requires non-falsifiable assumptions. The most efficient construction under mild assumptions remains the construction of Chandran et al. (ICALP 2007) with a signature of size $\Theta(\sqrt{n})$, where $n$ is the number of users, and security is based on the Diffie-Hellman assumption in bilinear groups (the SXDH assumption in asymmetric bilinear groups). In this work we construct an asymptotically shorter ring signature from the hardness of the Diffie-Hellman assumption in bilinear groups. Each signature comprises $\Theta(\sqrt[3]{n})$ group elements, signing a message requires computing $\Theta(\sqrt[3]{n})$ exponentiations, and verifying a signature requires $\Theta(n^{2/3})$ pairing operations. To the best of our knowledge, this is the first ring signature based on bilinear groups with $o(\sqrt{n})$ signatures and sublinear verification complexity.

Note: This is a revised version and contains a new construction which is secure under the SXDH assumption (and not the permutation pairing assumption).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Ring SignatureBilinear GroupsSet Membership proof
Contact author(s)
alonso gonzalez @ ens-lyon fr
History
2019-01-17: last of 2 revisions
2017-09-24: received
See all versions
Short URL
https://ia.cr/2017/905
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/905,
      author = {Alonso González},
      title = {Shorter Ring Signatures from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/905},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/905}},
      url = {https://eprint.iacr.org/2017/905}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.