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

摘要

We propose a short signature scheme under the ring-SISassumption in the standard model. Specifically, by revisiting an existingconstruction [Ducas and Micciancio, CRYPTO 2014], we demonstratelattice-based signatures with improved reduction loss. As far as we know,there are no ways to use multiple tags in the signature simulation of securityproof in the lattice tag-based signatures. We address the tag-collision possibilityin the lattice setting, which improves reduction loss. Our schemegenerates tags from messages by constructing a scheme under a mild securitycondition that is existentially unforgeable against random messageattack with auxiliary information. Thus our scheme can reduce the signaturesize since it does not need to send tags with the signatures. Our schemehas short signature sizes of O11o and achieves tighter reduction loss thanthat of Ducas et al.’s scheme. Our proposed scheme has two variants. Ourscheme with one property has tighter reduction and the same verificationkey size of O(log n) as that of Ducas et al.’s scheme, where n is the securityparameter. Our scheme with the other property achieves much tighterreduction loss of O(Q/?n) and verification key size of O1no, where Q is thenumber of signing queries.