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