Approximating the densest sublattice from Rankin's inequality

Jianwei Li 1, 2 Phong Q. Nguyen 1, 2
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : We present a higher-dimensional generalization of the Gama{Nguyen algorithm (STOC '08) for approximating the shortest vector problem in a lattice. This generalization approximates the densest sublattice by using a subroutine solving the exact problem in low dimension, such as the Dadush{Micciancio algorithm (SODA '13). Our approximation factor corresponds to a natural inequality on Rankin's constant derived from Rankin's inequality.
Type de document :
Article dans une revue
LMS Journal of Computation and Mathematics, London Mathematical Society, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. 〈http://journals.cambridge.org/download.php?file=%2FJCM%2FJCM17_A%2FS1461157014000333a.pdf&code=1406c0f6df3124f0ff41ae708a1ef5e1〉. 〈10.1112/S1461157014000333〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01057710
Contributeur : Phong Q. Nguyen <>
Soumis le : lundi 25 août 2014 - 11:33:19
Dernière modification le : jeudi 11 janvier 2018 - 06:25:20

Identifiants

Collections

Citation

Jianwei Li, Phong Q. Nguyen. Approximating the densest sublattice from Rankin's inequality. LMS Journal of Computation and Mathematics, London Mathematical Society, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. 〈http://journals.cambridge.org/download.php?file=%2FJCM%2FJCM17_A%2FS1461157014000333a.pdf&code=1406c0f6df3124f0ff41ae708a1ef5e1〉. 〈10.1112/S1461157014000333〉. 〈hal-01057710〉

Partager

Métriques

Consultations de la notice

269