## CryptoDB

### Daniel Sheffield

#### Publications

Year
Venue
Title
2019
JOFC
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.

#### Coauthors

Shi Bai (1)
Steven D. Galbraith (1)
Liangze Li (1)