Cryptology ePrint Archive: Report 2014/593
Improved Exponential-time Algorithms for Inhomogeneous-SIS
Shi Bai and Steven D. Galbraith and Liangze Li and Daniel Sheffield
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 \equiv 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.
Category / Keywords: public-key cryptography / SIS, subset-sum
Date: received 31 Jul 2014, last revised 18 Dec 2014
Contact author: s galbraith at math auckland ac nz
Available format(s): PDF | BibTeX Citation
Version: 20141218:214227 (All versions of this report)
Short URL: ia.cr/2014/593
[ Cryptology ePrint archive ]