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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Plos One
DOI
10.1371/journal.pone.0310708
Keywords
Post-quantum cryptographyLattice-based signatureGeneralized compact knapsack problem
Contact author(s)
woojoo0121 @ korea ac kr
kwangsu @ sejong ac kr
jhpark @ smu ac kr
History
2024-12-10: revised
2022-11-30: received
See all versions
Short URL
https://ia.cr/2022/1665
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1665,
      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},
      doi = {10.1371/journal.pone.0310708},
      url = {https://eprint.iacr.org/2022/1665}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.