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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.