The Hidden Lattice Problem

Luca Notarnicola and Gabor Wiese

Abstract

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 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 al- ternative 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
Euclidean LatticesLattice ReductionCryptanalysisApproximate Common Divisor ProblemHidden Subset Sum Problem
Contact author(s)
notarnicola luca @ internet lu
gabor wiese @ uni lu
History
Short URL
https://ia.cr/2021/1491

CC BY

BibTeX

@misc{cryptoeprint:2021/1491,
author = {Luca Notarnicola and Gabor Wiese},
title = {The Hidden Lattice Problem},
howpublished = {Cryptology ePrint Archive, Paper 2021/1491},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1491}},
url = {https://eprint.iacr.org/2021/1491}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.