Welcome to the resource topic for 2014/593
Title:
Improved Exponential-time Algorithms for Inhomogeneous-SIS
Authors: Shi Bai, Steven D. Galbraith, Liangze Li, 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.
ePrint: https://eprint.iacr.org/2014/593
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .