Short Lattice Signatures in the Standard Model with Efficient Tag Generation

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.