On the probability of generating a lattice

DOI10.1016/J.JSC.2013.12.002MaRDI QIDQ2437315zbMATH OpenOpenAlexFDO

Authors Felix Fontein, Pawel Wocjan

Publication date 3 March 2014

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.6246

zbMATH Keywords

analysis of quantum algorithmdiscrete logarithm problemRandom generation of a latticeRiemann zeta function

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: We study the problem of determining the probability that m vectors selected uniformly at random from the intersection of the full-rank lattice L in R^n and the window [0,B)^n generate $Lambda$ when B is chosen to be appropriately large. This problem plays an important role in the analysis of the success probability of quantum algorithms for solving the Discrete Logarithm Problem in infrastructures obtained from number fields and also for computing fundamental units of number fields. We provide the first complete and rigorous proof that 2n+1 vectors suffice to generate L with constant probability (provided that B is chosen to be sufficiently large in terms of n and the covering radius of L and the last n+1 vectors are sampled from a slightly larger window). Based on extensive computer simulations, we conjecture that only n+1 vectors sampled from one window suffice to generate L with constant success probability. If this conjecture is true, then a significantly better success probability of the above quantum algorithms can be guaranteed.

Review text

Motivated by an analysis of the success probability of quantum algorithms for solving the discrete logarithm problem in infrastructures obtained from number fields, the paper under review studies the problem of determining the probability that \(m\) vectors selected uniformly at random from \({\mathcal L} \cap [0,B)^n\) generate the (full-rank) lattice \({\mathcal L} \subset {\mathbb R^n}\), when \(B\) is chosen appropriately large. To state the main theorem precisely, assume that \(B \geq 8 n^{ n \over 2 } \nu({\mathcal L})\) and \(B_1 \geq 8 n^2 (n+1) B\), where \(\nu({\mathcal L})\) is the covering radius of \(\mathcal L\) (i.e., the smallest \(r\) such that translates by \(\mathcal L\) of a ball of radius \(r\) covers \({\mathbb R}^n\)), and that \(n\) vectors are selected uniformly at random from \({\mathcal L} \cap [0,B)^n\) and \(n+1\) vectors from \({\mathcal L} \cap [0,B)^n\). If the vectors are sampled independently then the probability that they generate \(\mathcal L\) is at least \[ \left( \prod_{ j=2 }^{ n+1 } \zeta(j)^{ -1 } - {1 \over 4} \right) \prod_{ k=0 }^{ n-1 } \left( 1 - n^{ k \over 2 } {{ \left( 4 n^{ n \over 2 } + 1 \right)^k } \over { \left( 4 n^{ n \over 2 } - 1 \right)^n }} \right) . \] This means that \(2n+1\) vectors suffice to generate \(\mathcal L\) with constant probability, provided that \(B\) is chosen sufficiently large. The authors conjecture that the quantity \(2n+1\) in this statement can be replaced by \(n+1\).

Recommendations

• scientific article; zbMATH DE number 2196508
• scientific article; zbMATH DE number 1256724
• On the smallest number of generators and the probability of generating an algebra
• Probabilistic Analyses of Lattice Reduction Algorithms
• Generating shorter bases for hard random lattices

Cites work

• A key-exchange protocol using real quadratic fields
• Decomposing finite Abelian groups
• Fast quantum algorithms for computing the unit group and class group of a number field
• Generalization of a theorem of Siegel
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• scientific article; zbMATH DE number 1346526 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• scientific article; zbMATH DE number 908573 (Why is no real title available?)
• Natural density of rectangular unimodular integer matrices
• Polynomial time quantum algorithm for the computation of the unit group of a number field
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
• The expected number of random elements to generate a finite Abelian group
• The infrastructure of a global field of arbitrary unit rank
• The probability of choosing primitive sets
• Trapdoors for hard lattices and new cryptographic constructions
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(5)

• Generating random elements of finite distributive lattices
• Loop-abort faults on lattice-based Fiat-Shamir and hash-and-sign signatures
• Enumeration, Counting, and Random Generation of Ladder Lotteries
• scientific article; zbMATH DE number 2196508 (Why is no real title available?)
• On the probability of generating a primitive matrix

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the probability of generating a lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437315)