Paper 2014/593

Improved Exponential-time Algorithms for Inhomogeneous-SIS

Shi Bai, Steven D. Galbraith, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Journal of Cryptology volume 32, pages 35-83 (2019)
DOI
10.1007/s00145-018-9304-1
Keywords
SISsubset-sum
Contact author(s)
s galbraith @ math auckland ac nz
History
2021-03-07: last of 2 revisions
2014-07-31: received
See all versions
Short URL
https://ia.cr/2014/593
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/593,
      author = {Shi Bai and Steven D.  Galbraith and Liangze Li and Daniel Sheffield},
      title = {Improved Exponential-time Algorithms for Inhomogeneous-SIS},
      howpublished = {Cryptology ePrint Archive, Paper 2014/593},
      year = {2014},
      doi = {10.1007/s00145-018-9304-1},
      note = {\url{https://eprint.iacr.org/2014/593}},
      url = {https://eprint.iacr.org/2014/593}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.