Raptor: A Practical Lattice-Based (Linkable) Ring Signature

Xingye Lu, Man Ho Au, and Zhenfei Zhang

Abstract

We present Raptor, the first practical lattice-based (linkable) ring signature scheme with implementation. Raptor is as fast as classical solutions; while the size of the signature is roughly $1.3$ KB per user. Prior to our work, all existing lattice-based solutions are analogues of their discrete-log or pairing-based counterparts. We develop a generic construction of (linkable) ring signatures based on the well-known generic construction from Rivest et al., which is not fully compatible with lattices. We show that our generic construction is provably secure in random oracle model. We also give instantiations from both standard lattice, as a proof of concept, and NTRU lattice, as an efficient instantiation. We showed that the latter construction, called Raptor, is almost as efficient as the classical RST ring signatures and thus may be of practical interest.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
ring signatureslattice based cryptographyfalcon signaturecryptographic implementations
Contact author(s)
zhenfei zhang @ hotmail com
xingye lu @ connect polyu hk
History
2019-03-13: last of 3 revisions
See all versions
Short URL
https://ia.cr/2018/857

CC BY

BibTeX

@misc{cryptoeprint:2018/857,
author = {Xingye Lu and Man Ho Au and Zhenfei Zhang},
title = {Raptor: A Practical Lattice-Based (Linkable) Ring Signature},
howpublished = {Cryptology ePrint Archive, Paper 2018/857},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/857}},
url = {https://eprint.iacr.org/2018/857}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.