Search

The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, an orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice Z n is of particular interest (Z LIP). Heuristic analysis suggests that the BKZ algorithm with blocksize β = n / 2 + o (n) solves such instances (Ducas, Postlethwaite, Pulles, van Woerden, ASIACRYPT 2022). In this work, I propose a provable version of this statement, namely, that Z LIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem oracle in dimension at most n / 2 + 1 . [ABSTRACT FROM AUTHOR]

We propose a concrete family of dense lattices of arbitrary dimension n in which the lattice bounded distance decoding (BDD) problem can be solved in deterministic polynomial time. This construction is directly adapted from the Chor–Rivest cryptosystem (IEEE-TIT 1988). The lattice construction needs discrete logarithm computations that can be made in deterministic polynomial time for well-chosen parameters. Each lattice comes with a deterministic polynomial time decoding algorithm able to decode up to large radius. Namely, we reach decoding radius within O (log n) Minkowski's bound, for both ℓ 1 and ℓ 2 norms. [ABSTRACT FROM AUTHOR]

In this work we consider the closest vector problem (CVP)-a problem also known as maximum-likelihood decoding-in the tensor of two root lattices of type A ( $$A_m \otimes A_n$$ ), as well as in their duals ( $$A^*_m \otimes A^*_n$$ ). This problem is mainly motivated by lattice based cryptography, where the cyclotomic rings $${\mathbb {Z}}[\zeta _c]$$ (resp. its co-different $${\mathbb {Z}}[\zeta _c]^\vee $$ ) play a central role, and turn out to be isomorphic as lattices to tensors of $$A^*$$ lattices (resp. A root lattices). In particular, our results lead to solving CVP in $${\mathbb {Z}}[\zeta _c]$$ and in $${\mathbb {Z}}[\zeta _c]^\vee $$ for conductors of the form $$c = 2^\alpha p^\beta q^\gamma $$ for any two odd primes p, q. For the primal case $$A_m \otimes A_n$$ , we provide a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph $$K_{m+1,n+1}$$ . This leads-relying on the Bellman-Ford algorithm for negative cycle detection-to a CVP algorithm running in polynomial time. Precisely, our algorithm performs $$O(l\ m^2 n^2 \min \{m,n\})$$ operations on reals, where l is the number of bits per coordinate of the input target. For the dual case, we use a gluing-construction to solve CVP in sub-exponential time $$O(n m^{n+1})$$ . [ABSTRACT FROM AUTHOR]