scientific article; zbMATH DE number 1775383
From MaRDI portal
Publication:4542515
Recommendations
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- scientific article; zbMATH DE number 1335879
- The shortest vector in a lattice is hard to approximate to within some constant
- On the unique shortest lattice vector problem
- Inapproximability of the shortest vector problem: toward a deterministic reduction
Cited in
(only showing first 100 items - show all)- Sampling methods for shortest vectors, closest vectors and successive minima
- Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- The optimal LLL algorithm is still polynomial in fixed dimension.
- On the limits of nonapproximability of lattice problems
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Planckian axions and the weak gravity conjecture
- Segment LLL reduction of lattice bases using modular arithmetic
- Minimal condition for shortest vectors in lattices of low dimension
- Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction
- Computing explicit isomorphisms with full matrix algebras over \(\mathbb {F}_q(x)\)
- Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme
- Random lattices, threshold phenomena and efficient reduction algorithms.
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- The inapproximability of lattice and coding problems with preprocessing
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- Vulnerable public keys in NTRU cryptosystem
- Approximate CVP\(_p\) in time \(2^{0.802n}\)
- Algorithmically solving the tadpole problem
- Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
- On a dual/hybrid approach to small secret LWE. A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Ciphertext-only attacks against compact-LWE submitted to NIST PQC project
- New orthogonality criterion for shortest vector of lattices and its applications
- Improved broadcast attacks against subset sum problems via lattice oracle
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Restricted parameter range promise set cover problems are easy
- Detecting squarefree numbers
- Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
- Fast LLL-type lattice reduction
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
- Improved hardness results for unique shortest vector problem
- Counting lattice vectors
- Revisiting lower dimension lattice attacks on NTRU
- Improving convergence and practicality of slide-type reductions
- The shortest vector in a lattice is hard to approximate to within some constant
- On the complexity of computing short linearly independent vectors and short bases in a lattice
- Note on shortest and nearest lattice vectors
- Magnifying computing gaps. Establishing encrypted communication over unidirectional channels
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- A fast phase-based enumeration algorithm for SVP challenge through \(y\)-sparse representations of short lattice vectors
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- Approximating the closest vector problem using an approximate shortest vector oracle
- The geometry of lattice cryptography
- An efficient lattice reduction using reuse technique blockwisely on NTRU
- A lattice attack on homomorphic NTRU with non-invertible public keys
- New Definition of Density on Knapsack Cryptosystems
- Explicit Hard Instances of the Shortest Vector Problem
- Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
- Practical strategies for generating rank-1 split cuts in mixed-integer linear programming
- scientific article; zbMATH DE number 1335879 (Why is no real title available?)
- Thrackles: an improved upper bound
- Lower bounds of shortest vector lengths in random NTRU lattices
- scientific article; zbMATH DE number 1852143 (Why is no real title available?)
- On the number of circuits in regular matroids (with connections to lattices and codes)
- On pairwise Gaussian bases and LLL algorithm for three dimensional lattices
- Application of algebraic-ring in key exchange protocol
- Hardness of bounded distance decoding on lattices in lp norms
- Cloud-assisted LLL: a secure and efficient outsourcing algorithm for approximate shortest vector problem
- Lattice Identification and Separation: Theory and Algorithm
- A parametric version of LLL and some consequences: parametric shortest and closest vector problems
- Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors
- A greedy algorithm for quantizing neural networks
- Hermite’s Constant and Lattice Algorithms
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- Lattice-Based Identification Schemes Secure Under Active Attacks
- A Digital Signature Scheme Based on CVP ∞
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Approximate CVP_p in Time 2^{0.802 n}
- A simple deterministic reduction for the gap minimum distance of code problem
- On the unique shortest lattice vector problem
- Lattice Sieving via Quantum Random Walks
- Finding points on elliptic curves with Coppersmith's method
- On fluxes in the \(1^9\) Landau-Ginzburg model
- Lattice-based cryptography: a survey
- Mathematics of computation through the lens of linear equations and lattices
- Cryptanalysis of the GGH cryptosystem
- Verification of NP-Hardness Reduction Functions for Exact Lattice Problems
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
- Lattice problems beyond polynomial time
- Improved strategies for branching on general disjunctions
- Solving modular cubic equations with Coppersmith's method
- On polynomial modular number systems over \(\mathbb{Z}/p\mathbb{Z}\)
- The combinatorial game \textsc{Nofil} played on Steiner triple systems
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
- Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
- On the smallest ratio problem of lattice bases
- \((2,2)\) superconformal bootstrap in two dimensions
- Rejection-free framework of zero-knowledge proof based on \textsf{Hint-MLWE}
- On the ability to approximate k-DSP of HKZ, BKZ and slide reduction
- Computing asymptotic bounds for small roots in Coppersmith's method via sumset theory
- Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
- Solving modular linear equations via automated Coppersmith and its applications
- Research of k-sieve algorithm for solving the shortest vector problem in a lattice
- Norm orthogonal bases and invariants of p-adic lattices
- Notes on the generalized Gauss reduction algorithm
- An attack on p-adic lattice public-key encryption cryptosystems and signature schemes
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 Q4542515)
