On basing search SIVP on NP-hardness

DOI10.1007/978-3-030-03807-6_4MaRDI QIDQ1629401zbMATH OpenOpenAlexFDO

Authors Tianren Liu

Publication date 11 December 2018

Full work available at URL https://doi.org/10.1007/978-3-030-03807-6_4

zbMATH Keywords

approximate shortest independent vector problem (SIVP)complexity-theoretic cryptography

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Recommendations

• A note on the concrete hardness of the shortest independent vector in lattices
• Inapproximability of the shortest vector problem: toward a deterministic reduction
• A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
• Hardness of approximating the shortest vector problem in lattices
• On the limits of nonapproximability of lattice problems

Cites work

• Advances in Cryptology - CRYPTO 2003
• Classical hardness of learning with errors
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• Limits of provable security for homomorphic encryption
• New bounds in some transference theorems in the geometry of numbers
• Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
• On basing one-way functions on NP-hardness
• On basing private information retrieval on NP-hardness
• On basing size-verifiable one-way functions on NP-hardness
• On lattices, learning with errors, random linear codes, and cryptography
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• On the limits of nonapproximability of lattice problems
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Relativized cryptography
• Trapdoors for hard lattices and new cryptographic constructions
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(1)

• On basing private information retrieval on NP-hardness

This page was built for publication: On basing search SIVP on \(\mathbf{NP}\)-hardness

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