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 indistinguishab...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2024-09, Vol.19 (9), p.e0310708
Main Authors: Woo, Joo, Lee, Kwangsu, Park, Jong Hwan
Format: Article
Language:English
Subjects:
Algorithms
Collisions (Physics)
Computer and Information Sciences
Computer Security
Digital signatures
Efficiency
Engineering and Technology
Investment analysis
Knapsack problem
Methods
Models, Theoretical
Modules
Physical Sciences
Polynomials
Prevention
Research and Analysis Methods
Security
Social Sciences
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0310708