Paper 2026/2083

Two-Bit Lifting for Ternary SIS: Polynomial-Time Collision Attacks on LtHash

Abstract

LtHash is a lattice-based incremental hash function introduced by Bellare and Micciancio at EUROCRYPT 1997. It can be used in distributed systems to efficiently maintain digests of changing data. Its set-collision resistance rests on the average-case hardness of the ternary short integer solution (SIS) problem in the random oracle model. LtHash implementations typically use power-of-two groups $(\mathbb{Z}/2^d\mathbb{Z})^N$ for efficient machine-word arithmetic and SIMD parallelism. Previous security estimates were based on Wagner-type generalized birthday attacks with sub-exponential running time. Chen, Liu, and Zhandry (CLZ, EUROCRYPT'22) describe a folklore algorithm attributed to Regev that solves ternary SIS modulo $2^d$. Applying this algorithm to LtHash yields polynomial-time collision attacks requiring $O(N^d)$ hash queries, a result that has not been previously documented. We improve the Regev--CLZ algorithm by canceling two modulus bits per layer instead of one, while preserving ternary coefficients. This reduces the number of input columns---and hence the number of LtHash queries---from $O(N^d)$ to $O(N^{\lceil d/2\rceil})$. This refutes the uniform average-case formulation of Liyan Chen et al.'s conjecture (ITC'26) that the Regev--CLZ bound is optimal. Our technique also extends to inhomogeneous SIS with the same bound. For LtHash16 with $(N,d)=(1024,16)$, used at Facebook and in Solana, our attack requires approximately $2^{81}$ hash queries. Its expected computational cost is at most $2^{101}$ scalar operations over $\mathbb{F}_2$, compared with our estimates of approximately $2^{180}$ operations for the Regev--CLZ algorithm and $2^{188}$ for the state-of-the-art generalized birthday attack of Tang et al. (CRYPTO'26), under their respective operation models. Our query and scalar-operation costs are both far below the level suggested by the original claim of at least 200-bit security.