### Genus Distribution of Random q-ary Lattices

##### Abstract

The genus is an efficiently computable arithmetic invariant for lattices up to isomorphism. Given the recent proposals of basing cryptography on the lattice isomorphism problem, it is of cryptographic interest to classify relevant families of lattices according to their genus. We propose such a classification for q-ary lattices, and also study their distribution. In particular, for an odd prime q, we show that random q-ary lattices are mostly concentrated on two genera. Because the genus is local, this also provides information on the distribution for general odd q. The case of q a power of 2 is also studied, although we only achieve a partial classification.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Lattice Genus Quadratic Form Distribution Lattice Isomorphism Problem
Contact author(s)
p j bruin @ math leidenuniv nl
leo ducas @ cwi nl
shane gibbons @ cwi nl
History
2022-07-01: approved
See all versions
Short URL
https://ia.cr/2022/861

CC BY

BibTeX

@misc{cryptoeprint:2022/861,
author = {Peter J. Bruin and Léo Ducas and Shane Gibbons},
title = {Genus Distribution of Random q-ary Lattices},
howpublished = {Cryptology ePrint Archive, Paper 2022/861},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/861}},
url = {https://eprint.iacr.org/2022/861}
}

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