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]

In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, given an ideal lattice of the cyclotomic ring of conductor m, the algorithm finds an approximation of the shortest vector by a factor exp(-õ (vm)). This result exposes an unexpected hardness gap between these structured lattices and general lattices: The best known polynomial time generic lattice algorithms can only reach an approximation factor exp(-O (m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, suchas Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes. [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]

Lattice signature schemes generally require particular care when it comes to preventing secret information from leaking through signature transcript. For example, the Goldreich–Goldwasser–Halevi (GGH) signature scheme and the NTRUSign scheme were completely broken by the parallelepiped-learning attack of Nguyen and Regev (Eurocrypt 2006). Several heuristic countermeasures were also shown vulnerable to similar statistical attacks. At PKC 2008, Plantard, Susilo and Win proposed a new variant of GGH, informally arguing resistance to such attacks. Based on this variant, Plantard, Sipasseuth, Dumondelle and Susilo proposed a concrete signature scheme, called DRS, that is in the round 1 of the NIST post-quantum cryptography project. In this work, we propose yet another statistical attack and demonstrate a weakness of the DRS scheme: one can recover some partial information of the secret key from sufficiently many signatures. One difficulty is that, due to the DRS reduction algorithm, the relation between the statistical leak and the secret seems more intricate. We work around this difficulty by training a statistical model, using a few features that we designed according to a simple heuristic analysis. While we only recover partial secret coefficients, this information is easily exploited by lattice attacks, significantly decreasing their complexity. Concretely, we claim that, provided that 100 000 signatures are available, the secret key may be recovered using BKZ-138 for the first set of DRS parameters submitted to the NIST. This puts the security level of this parameter set below 80-bits (maybe even 70-bits), to be compared to an original claim of 128-bits. Furthermore, we review the DRS v2 scheme that is proposed to resist above statistical attack. For this countermeasure, while one may not recover partial secret coefficients exactly by learning, it seems feasible to gain some information on the secret key. Exploiting this information, we can still effectively reduce the cost of lattice attacks. [ABSTRACT FROM AUTHOR]