Lattice‐based hash‐and‐sign signatures using approximate trapdoor, revisited
Huiwen Jia, Yupu Hu, Chunming Tang
Abstract
Abstract For the purpose of improving the efficiency of the cryptosystems built upon lattice trapdoors, Chen, Genise and Mukherjee at ASIACRYPT 2019 modified the gadget trapdoor (G‐trapdoor) to an approximate trapdoor, which enables one to sample short preimages approximately from a discrete Gaussian distribution. The implementation shows that the sizes of the hash‐and‐sign signature scheme can be reduced to 3.67 kB for an estimation of 81.67‐bit security, and 9.97 kB for an estimation of 168.81‐bit security. In this study, the spherical sampling method is adapted to the non‐spherical setting, without leaking any information about the trapdoor. Due to the fact that the signature size and the concrete security are closely related to the Gaussian parameter of the sampling algorithm, this technique provides a tradeoff between them. Specifically, two modes of parameters were set up for different goals. (a) Mode 1 admits to achieve the ‘win–win’ scenario, that is, gain concrete security and simultaneously reduce the signature size. Our proof‐of‐concept implementation shows that for an estimation of 94.5‐ and 185.88‐bit security, the signature sizes can be reduced to 3.3 and 6.98 kB. (b) Mode 2 aims mainly to further reduce the signature sizes, without a decrease in the security level. The implementation shows that the signature size can be reduced to 2.35 kB for an estimation of 81.67‐bit security, and 5.75 kB for an estimation of 168.82‐bit security.