scientific article; zbMATH DE number 2196508
The paper proves that the solution to the problem of finding a short vector in a certain random lattice would imply the solution of three ``famous lattice problems: (P1) Find the length of a shorter vector in an \(n\)-dimensional lattice approximately. (P2) Find the shorter vector in an \(n\)-dimensional lattice where the shorter vector is unique. (P3) Find a base in an \(n\)-dimensional lattice whose length is the smallest possible up to a polynomial factor. In the Introduction the author describes the cryptographic context: public key cryptosystems use a specific instance of an NP-problem where the instance is supposed to be difficult to solve. A solution to the lack of a mathematical proof of this ``difficulty is to prove that the solution of a random instance would solves one ``famous unsolved problem in the worst case. Finding short vectors in a lattice is a classical problem that goes back to Dirichlet, a landmark being the \(L^3\) algorithm of \textit{A. K. Lenstra, H. W. Lenstra jun.} and \textit{L. Lovasz} [Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)]. Section 2 describes the lattices to be considered and states the main result of the paper. The author defines a random variable whose values are lattices \(\Delta (\nu, q)\),\, where \(\nu = \langle u_1,\dots, u_m\rangle\), \(u_i\in \mathbb{Z}^n\). \(\Delta (\nu, q)\)\, is the lattice of all sequences of integers \(h_1,\dots,h_m\) such that \(\sum h_iu_i\equiv 0\bmod q\) (where \(m,q\) are integers depending only on \(n\)). Then Theorem 2.1 states that ``If there is an algorithm which finds a short vector, with a non-trivial probability, in \(L=\Delta (\nu, q)\) then there is a probabilistic algorithm which solves the worst case problems. Section 3 gives a sketch of the proof of Theorem 2.1. In particular it is shown that it is enough to prove P3 since P1 and P2 easily follow. The remaining three sections give the details of the proof. For the entire collection see [Zbl 1062.68004].
- scientific article; zbMATH DE number 1256724
- Generating hard satisfiability problems
- scientific article; zbMATH DE number 6168348
- Generating and measuring instances of hard semidefinite programs
- Generating hard instances of the short basis problem
- Generating hard instances for robust combinatorial optimization
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- On the probability of generating a lattice
- The complexity of some lattice problems
- Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures
- A note on the minimal volume of almost cubic parallelepipeds
- Bonsai trees, or how to delegate a lattice basis
- Random self-reducibility of ideal-SVP via Arakelov random walks
- Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
- Generating hard instances for robust combinatorial optimization
- A new Gaussian sampling for trapdoor lattices with arbitrary modulus
- The remote set problem on lattices
- On the probability of generating a lattice
- Improved hardness results for unique shortest vector problem
- Counting lattice vectors
- A note on the concrete hardness of the shortest independent vector in lattices
- Lower bounds of shortest vector lengths in random NTRU lattices
- Lattice Point Enumeration on Block Reduced Bases
- The geometry of lattice cryptography
- scientific article; zbMATH DE number 5726469 (Why is no real title available?)
- scientific article; zbMATH DE number 15884 (Why is no real title available?)
- scientific article; zbMATH DE number 1256724 (Why is no real title available?)
- scientific article; zbMATH DE number 1313325 (Why is no real title available?)
- Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
- The shortest vector problem in lattices with many cycles
- Generating hard instances of the short basis problem
- Improved discrete Gaussian and Subgaussian analysis for lattice cryptography
- Cryptographic functions from worst-case complexity assumptions
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- Generating shorter bases for hard random lattices
- Generating shorter bases for hard random lattices
- Asymptotically Efficient Lattice-Based Digital Signatures
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
- Functional commitments for all functions, with transparent setup and from SIS
- Lattice problems beyond polynomial time
- Trace-based cryptanalysis of cyclotomic \(R_{q, 0} \times R_q\)-PLWE for the non-split case
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- On the LWE cryptosystem with more general disturbance
- Cryptanalysis of lattice-based sequentiality assumptions and proofs of sequential work
- Authenticated sublinear quantum private information retrieval
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5465355)
