Parameter Selection in Cryptography based on Lattice Isomorphism — Cryptanalysis of the Lattice Isomorphism Problem

Abstract

The Lattice Isomorphism Problem (LIP) is a promising foundation for post-quantum cryptography due to its structural parallels with classical lattice problems and its computational hardness. This thesis explores the security of LIP, focusing on cryptanalytic reductions and parameter choices that influence its difficulty. Key contributions include an analysis and extension of the Hull Attack, which leverages the trivial hull property of certain lattices to reduce LIP to the Permutation Code Equivalence (PCE) problem, through a novel reduction from 𝑞-ary to 𝑝-ary LIP, under certain conditions.

Additionally, the thesis extends the Lattice Estimator to evaluate the complexity of solving LIP using various algorithms, such as Haviv and Regev’s algorithm and the Hull Attack. It also demonstrates the existence of orthogonal transformations beyond signed permutations between 𝑞-ary lattices, broadening the scope of isomorphic transformations. These results provide theoretical and practical insights into the resilience of LIP-based cryptographic schemes against emerging attacks.

Lattice Isomorphism Problem (LIP) är en lovande grund för post-kvantkryptografi på grund av dess strukturella likheter med klassiska gitterproblem och dess beräkningsmässiga svårighet. Denna avhandling undersöker säkerheten hos LIP, med fokus på kryptanalytiska reduktioner och val av parametrar som påverkar dess komplexitet. Viktiga bidrag inkluderar en analys och utvidgning av Hull Attack, som utnyttjar egenskapen av trivial hull hos vissa gitter för att reducera LIP till Permutation Code Equivalence (PCE)-problemet, genom en ny reduktion från 𝑞-ärt till 𝑝-ärt LIP, under vissa villkor.

Avhandlingen utökar dessutom Lattice Estimator programmet för att utvärdera komplexiteten i att lösa LIP med olika algoritmer, såsom Haviv och Regevs algoritm samt Hull Attack. Den visar också existensen av ortogonala transformationer bortom signerade permutationer mellan 𝑞-ära gitter, vilket breddar omfånget av isomorfa transformationer. Dessa resultat ger både teoretiska och praktiska insikter i motståndskraften hos LIP-baserade kryptografiska system mot framväxande attacker.