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,s)$ to find a short vector $x$ such that $Ax \equiv s \pmod{q}$. We consider algorithms for this problem due to Camion and Patarin; Wagner; Schroeppel and Shamir; Minder and Sinclair; Howgrave-Graham and Joux (HGJ); Becker, Coron and Joux (BCJ). 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; A new method that exploits symmetries to speed up algorithms for Ring-SIS in some cases.

This paper is published in Journal of Cryptology, Volume 32, Issue 1 (2019) 35--83.

Category / Keywords: public-key cryptography / SIS, subset-sum

Original Publication (with minor differences): Journal of Cryptology volume 32, pages 35-83 (2019)
DOI: 10.1007/s00145-018-9304-1

Date: received 31 Jul 2014, last revised 7 Mar 2021

Contact author: s galbraith at math auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20210307:191058 (All versions of this report)

Short URL: ia.cr/2014/593