Open AccessDeterministic lattice reduction on knapsacks with collision‐free properties
Author(s) -
Ping Yuan,
Wang Baocang,
Tian Shengli,
Yang Yuehua,
Du Genyuan
Publication year - 2018
Publication title -
iet information security
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.308
H-Index - 34
eISSN - 1751-8717
pISSN - 1751-8709
DOI - 10.1049/iet-ifs.2017.0107
Subject(s) - knapsack problem , lattice problem , cryptosystem , lattice based cryptography , lattice reduction , subset sum problem , public key cryptography , mathematics , discrete mathematics , continuous knapsack problem , cryptography , reduction (mathematics) , computer science , combinatorics , encryption , algorithm , computer security , physics , statistics , beamforming , quantum cryptography , geometry , quantum mechanics , mimo , quantum information , quantum
The knapsack problem is an important problem in computer science and had been used to design public key cryptosystems. Low‐density subset sum algorithms are powerful tools to reduce the security of trapdoor knapsacks to the shortest vector problem (SVP) over lattices. Several knapsack ciphers Chor–Rivest, Okamoto–Tanaka–Uchiyama, and Kate–Goldberg were proposed to defend low‐density attacks by utilising low‐weight knapsack problems. Some evidence was also found on the vulnerabilities of the above three knapsack ciphers to lattice attacks. However, previous lattice‐based cryptanalytic results have been established via a probabilistic approach. The authors investigate some collision‐free properties and derive from the properties a deterministic reduction from the knapsack problems in the Chor–Rivest, Okamoto–Tanaka–Uchiyama, and Kate–Goldberg knapsack ciphers to SVP without imposing any restriction and assumption. To the best of the authors' knowledge, the proposed reduction is the first deterministic reduction from public key cryptographic knapsacks to SVP.