Improved combinatorial algorithms for the inhomogeneous short integer solution problem

DOI10.1007/s00145-018-9304-1zbMath1435.11144OpenAlexW2897786092WikidataQ129092148 ScholiaQ129092148MaRDI QIDQ1715853

Steven D. Galbraith, Shi Bai, Daniel Sheffield, Liangze Li

Publication date: 29 January 2019

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-018-9304-1

zbMATH Keywords

knapsackssubset-sumshort integer solution problem (SIS)SWIFFT hash function

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Extremal combinatorics (05D99)

Related Items (3)

Full quantum equivalence of group action DLog and CDH, and more ⋮ A practical adaptive key recovery attack on the LGM (GSW-like) cryptosystem ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms

Uses Software

• SWIFFT
• SWIFFTX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The extended \(k\)-tree algorithm
• Improved low-density subset sum algorithms
• Hardness of SIS and LWE with Small Parameters
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• Improved Generic Algorithms for Hard Knapsacks
• SWIFFT: A Modest Proposal for FFT Hashing
• New Generic Algorithms for Hard Knapsacks
• A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU
• Lattice-based Cryptography
• Security Bounds for the Design of Code-Based Cryptosystems
• Secure Parameters for SWIFFT
• FSBday
• Solving low-density subset sum problems
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• The Knapsack Hash Function proposed at Crypto’89 can be broken
• Faster space-efficient algorithms for subset sum and k-sum
• An Improved Multi-set Algorithm for the Dense Subset Sum Problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems

This page was built for publication: Improved combinatorial algorithms for the inhomogeneous short integer solution problem