Improved Exponential-time Algorithms for Inhomogeneous-SIS.
Shi Bai, Steven D. Galbraith⋆, Liangze Li, Daniel Sheffield · 2014
Abstract. The paper is about algorithms for the inhomogeneous short integer solution problem: Given (A,b) to find a short vector s such that As ≡ b (mod q). We consider algorithms for this problem due to Camion and Patarin; Wagner; Schroeppel and Shamir; Howgrave-Graham and Joux; Becker, Coron and Joux. Our main results include: Applying the Hermite normal form (HNF) to get faster algorithms; A heuristic analysis of the HGJ and BCJ algorithms in the case of density greater than one; An improved cryptanalysis of the SWIFFT hash function.