Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal

Ward Beullens; Vadim Lyubashevsky; Ngoc Khanh Nguyen; Gregor Seiler

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/077

Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal

Ward Beullens

, IBM Research Europe, Zurich

Vadim Lyubashevsky, IBM Research Europe, Zurich

Ngoc Khanh Nguyen

, École Polytechnique Fédérale de Lausanne

Gregor Seiler, IBM Research Europe, Zurich

Abstract

We give a construction of a 2-round blind signature scheme based on the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around $4$ times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around $2$ times shorter than the scheme of Agrawal et al. (CCS 2022) based on their newly-proposed one-more-SIS assumption. We also give a construction of a ``keyed-verification'' blind signature scheme in which the verifier and the signer need to share a secret key. The signature size in this case is only $48$ bytes, but more work needs to be done to explore the efficiency of the protocol which generates the signature.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Blind Signatures Lattice Cryptography
Contact author(s): wbe @ zurich ibm com
vad @ zurich ibm com
khanh nguyen @ epfl ch
grs @ zurich ibm com
History: 2023-01-24: revised; 2023-01-23: received; See all versions
Short URL: https://ia.cr/2023/077
License: CC BY

BibTeX

@misc{cryptoeprint:2023/077,
      author = {Ward Beullens and Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler},
      title = {Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal},
      howpublished = {Cryptology ePrint Archive, Paper 2023/077},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/077}},
      url = {https://eprint.iacr.org/2023/077}
}