Hardness of hinted ISIS from the space-time hardness of lattice problems

252 / BBB

2026-04-14

Russell W. F. Lai

15:45

To assume the hardness of finding short vectors in (Euclidean) lattices is the bread and butter of lattice-based cryptography. These problems are even conjectured (Lombardiexplore and Vaikuntanathan, CRYPTO'20) to be hard for algorithms that run in single-exponential time but polynomial memory. In this work, we explore a perhaps surprising connection between the non-existence of such algorithms with the hardness of solving some hinted lattice problems in polynomial time. Roughly, Hinted Inhomogeneous Short Integer Solutions (H-ISIS) asks, given a random underdetermined system of linear equations (A, b) and as hints many short integral vectors in the kernel of A, to find an integral solution to the linear system only marginally longer than the hints. This suggests that the space-time hardness of lattice problems is a promising foundation for some advanced cryptographic primitives that have recently been proposed but, so far, are based on ad-hoc lattice assumptions with hints. 

Based on joint work with Martin R. Albrecht and Eamonn W. Postlethwaite.