GCKSign: Simple and efficient signatures from generalized compact knapsack problems.

In 2009, Lyubashevsky proposed a lattice-based signature scheme using the Schnorr-like identification and the Fiat-Shamir heuristic and proved its security under the collision resistance of a generalized compact knapsack function. However, their security analysis requires the witness indistinguishability property, leading to significant inefficiency and an increase of sizes of public key and signature. To overcome the efficiency issue associated with the WI property, we introduce a new lattice-based assumption, called the target-modified one-wayness problem of the GCK function and show its reduction to well-known lattice-based problems. Additionally, we present a simple and efficient GCK-based signature scheme, GCKSign, whose security is based on the Module GCK-TMO problem in the random oracle model. GCKSign is a natural extension of Lyubashevsky's scheme in a module setting, but achieves considerable efficiency gains due to eliminating the witness indistinguishability property. As a result, GCKSign achieves approximately 3.4 times shorter signature size and 2.4 times shorter public key size at the same security level.
Competing Interests: The authors have declared that no competing interests exist.
(Copyright: © 2024 Woo et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.)