International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem

Authors:
Shi Bai
Steven D. Galbraith
Liangze Li
Daniel Sheffield
Download:
DOI: 10.1007/s00145-018-9304-1
Search ePrint
Search Google
Abstract: The paper is about algorithms for the inhomogeneous short integer solution problem: given $$(\mathbf A , \mathbf s )$$ ( A , s ) to find a short vector $$\mathbf{x }$$ x such that $$\mathbf A \mathbf{x }\equiv \mathbf s \pmod {q}$$ A x ≡ s ( mod 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.
BibTeX
@article{jofc-2019-30149,
  title={Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={32},
  pages={35-83},
  doi={10.1007/s00145-018-9304-1},
  author={Shi Bai and Steven D. Galbraith and Liangze Li and Daniel Sheffield},
  year=2019
}