You are looking at a specific version 20141218:214227 of this paper.
See the latest version.
Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- 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
-
CC BY