Paper 2022/1665

GCKSign: Simple and Efficient Signatures from Generalized Compact Knapsacks

Joo Woo, Korea University
Kwangsu Lee, Sejong University
Jong Hwan Park, Sangmyung University

In 2009, Lyubashevsky proposed a lattice-based signature scheme by applying the Fiat-Shamir transformation and proved its security under the generalized compact knapsack (GCK) problem. This scheme has a simple structure but has large signature and key sizes due to the security requirement of their security reduction. Dilithium, which was submitted to the NIST Post-Quantum Cryptography standardization and selected as one of the final candidates, is an improvement of the Lyubashevsky's signature scheme and decreases key and signature sizes by modifying the form of a public key and including additional steps in key generation, signing, and verification algorithms. Thus, Dilithium has a more complex structure to implement compared to the Lyubashevsky's scheme. To combine the strength of both signature schemes, we modify the Lyubashevsky's signature scheme and present a new security proof that removes their security requirement. As a result, we propose a simple and practical GCKSign signature scheme based on the hardness of a new GCK assumption, called target-modified one-wayness of GCK function. The signature size of our signature scheme decreases 40 percent, the sum of signature and public key sizes decreases 25 percent, and the secret key size decreases 90 percent for the NIST security level III, compared to Dilithium. Furthermore, by the simplicity of our structure, the key generation, signing, and verification algorithms of our scheme run 2.4$\times$, 1.7$\times$, and 2.0$\times$ faster than those of Dilithium, respectively.

Available format(s)
Public-key cryptography
Publication info
Post-quantum cryptography Lattice-based signature Generalized compact knapsack problem
Contact author(s)
woojoo0121 @ korea ac kr
kwangsu @ sejong ac kr
jhpark @ smu ac kr
2022-11-30: approved
2022-11-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joo Woo and Kwangsu Lee and Jong Hwan Park},
      title = {GCKSign: Simple and Efficient Signatures from Generalized Compact Knapsacks},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1665},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.