### Short Lattice Signature Scheme with Tighter Reduction under Ring-SIS Assumption

Kaisei Kajita, Go Ohtake, Kazuto Ogawa, Koji Nuida, and Tsuyoshi Takagi

##### Abstract

We propose a short signature scheme under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme generates tags from messages by constructing a scheme under a mild security condition that is existentially unforgeable against random message attack with auxiliary information. Thus our scheme can reduce the signature size since it does not need to send tags with the signatures. Our scheme has short signature sizes of 𝑂(1) and achieves tighter reduction loss than that of Ducas et al.’s scheme. Our proposed scheme has two variants. Our scheme with one property has tighter reduction and the same verification key size of 𝑂(log 𝑛) as that of Ducas et al.’s scheme, where 𝑛 is the security parameter. Our scheme with the other property achieves much tighter reduction loss of 𝑂(𝑄/𝑛) and verification key size of 𝑂(𝑛), where 𝑄 is the number of signing queries.

Note: A preliminary version of this paper was presented at ProvSec 2020.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision.ProvSec 2020
Keywords
digital signatureslattice techniques
Contact author(s)
kajita k-bu @ nhk or jp
History
Short URL
https://ia.cr/2022/479

CC BY

BibTeX

@misc{cryptoeprint:2022/479,
author = {Kaisei Kajita and Go Ohtake and Kazuto Ogawa and Koji Nuida and Tsuyoshi Takagi},
title = {Short Lattice Signature Scheme with Tighter Reduction under Ring-SIS Assumption},
howpublished = {Cryptology ePrint Archive, Paper 2022/479},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/479}},
url = {https://eprint.iacr.org/2022/479}
}

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