Random Integer Lattice Generation via the Hermite Normal Form

Lattices used in cryptography are integer lattices. Defining and generating a “random integer lattice” are interesting topics. A generation algorithm for a random integer lattice can be used to serve as a random input of all the lattice algorithms. In this paper, we recall the definition of the rand...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gengran Hu, Lin You, Liang Li, Liqin Hu, Hui Wang
Formato: article
Lenguaje:EN
Publicado: MDPI AG 2021
Materias:
Q
Acceso en línea:https://doaj.org/article/197f0c17bb274ab68213184da3831b2e
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
Descripción
Sumario:Lattices used in cryptography are integer lattices. Defining and generating a “random integer lattice” are interesting topics. A generation algorithm for a random integer lattice can be used to serve as a random input of all the lattice algorithms. In this paper, we recall the definition of the random integer lattice given by G. Hu et al. and present an improved generation algorithm for it via the Hermite normal form. It can be proven that with probability ≥0.99, this algorithm outputs an <i>n</i>-dim random integer lattice within <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> operations.