Deterministic lattice reduction on knapsacks with collision‐free properties. (1st July 2018)

• Record Type: Journal Article
• Authors: Ping, Yuan; Wang, Baocang; Tian, Shengli; Yang, Yuehua; Du, Genyuan
• Is Part Of: IET information security. Volume 12:Number 4(2018)
• Page Start: 375
• Page End: 380
• Publication Date: 2018-07-01
• Subjects: public key cryptography -- knapsack problems -- probability; deterministic lattice reduction -- collision‐free properties -- computer science -- public key cryptosystems -- low‐density subset sum algorithms -- trapdoor knapsack security -- shortest vector problem -- SVP -- Chor‐Rivest knapsack ciphers -- Okamoto‐Tanaka‐Uchiyama knapsack ciphers -- low‐density attacks -- low‐weight knapsack problems -- lattice attacks -- lattice‐based cryptanalytic -- probabilistic approach -- Kate‐Goldberg knapsack ciphers -- public key cryptographic knapsacks; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2017.0107
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : 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.