eprint.iacr.orgpaper

Average-Case Hardness of Lattice Problems in Special Genera of Fixed Rank

The paper proves, under GRH, a worst-case to average-case reduction inside any special genus of Hermitian lattices of fixed rank r≥2 over cyclotomic fields. It covers (H)SVP, HCVP, (Δ)BDD, DSP and DGS, at a poly(d)·det^{O_r(1)/d} loss in the approximation factor. The reduction is a random walk on the Kneser p-neighbour graph, and its fast mixing comes from spectral bounds on Hecke operators. It also gives a direct, tight security proof for a minimal Lattice Isomorphism Problem (LIP) based KEM. The proof rests on two assumptions: the KEM's lattice is indistinguishable from a random lattice of its genus, and ΔBDD is hard on that genus. This removes the need for the ad-hoc qΛ⊕(q+1)Λ lattice and the tightness loss from the dense sublattice.