Short Lattice Signatures in the Standard Model with Efficient Tag Generation

Kaisei Kajita, Kazuto Ogawa, Koji Nuida, Tsuyoshi Takagi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


We propose new short signature schemes under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction in [Ducas and Micciancio, CRYPTO 2014], we demonstrate efficient lattice-based signatures with improved tag generation. We firstly construct a scheme under mild security condition that is existentially unforgeable against random message attack with auxiliary information. We then convert the mildly secure scheme to a fully secure scheme by applying a trapdoor commitment scheme. Our schemes enable the generation of tags from messages and the collision of multiple tags, which improves reduction loss. Our schemes have short signature sizes of O(1) and achieves tighter reduction loss than that of Ducas et al.’s scheme. In accordance with two kinds of parameter set for tag generation, we get two signature schemes with different properties of reduction loss and verification key size. One of our schemes has tighter reduction and as the same size verification key of O(log n) as that of Ducas et al.’s scheme, where n is the security parameter. Another scheme achieves much tighter reduction loss of O(Qn) for the sake of verification size of O(n), where Q is the number of signing queries.

Original languageEnglish
Title of host publicationProvable and Practical Security - 14th International Conference, ProvSec 2020, Proceedings
EditorsKhoa Nguyen, Wenling Wu, Kwok Yan Lam, Huaxiong Wang
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783030625757
Publication statusPublished - 2020
Externally publishedYes
Event14th International Conference on Provable Security, ProvSec 2020 - Singapore, Singapore
Duration: Nov 29 2020Dec 1 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12505 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th International Conference on Provable Security, ProvSec 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Short Lattice Signatures in the Standard Model with Efficient Tag Generation'. Together they form a unique fingerprint.

Cite this