Eprint first made available on ORBilu (E-prints, Working papers and Research blog)
The Hidden Lattice Problem
Notarnicola, Luca; Wiese, Gabor
2021
 

Files


Full Text
hidden_lattice.pdf
Author preprint (653.28 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Euclidean Lattices; Lattice Reduction; Cryptanalysis
Abstract :
[en] We consider the problem of revealing a small hidden lattice from the knowledge of a low-rank sublattice modulo a given sufficiently large integer -- the {\em Hidden Lattice Problem}. A central motivation of study for this problem is the Hidden Subset Sum Problem, whose hardness is essentially determined by that of the hidden lattice problem. We describe and compare two algorithms for the hidden lattice problem: we first adapt the algorithm by Nguyen and Stern for the hidden subset sum problem, based on orthogonal lattices, and propose a new variant, which we explain to be related by duality in lattice theory. Following heuristic, rigorous and practical analyses, we find that our new algorithm brings some advantages as well as a competitive alternative for algorithms for problems with cryptographic interest, such as Approximate Common Divisor Problems, and the Hidden Subset Sum Problem. Finally, we study variations of the problem and highlight its relevance to cryptanalysis.
Disciplines :
Mathematics
Author, co-author :
Notarnicola, Luca ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Mathematics (DMATH)
Wiese, Gabor  ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Mathematics (DMATH)
Language :
English
Title :
The Hidden Lattice Problem
Publication date :
2021
Focus Area :
Computational Sciences
Available on ORBilu :
since 10 November 2021

Statistics


Number of views
75 (0 by Unilu)
Number of downloads
49 (0 by Unilu)

Bibliography


Similar publications



Contact ORBilu