Search results for "closest-vector"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
81	Haibin Kan, Hong Shen 0001, Hong Zhu 0004	The Closest Vector Problem on Some Lattices.	GCC (2)	2003	DBLP DOI BibTeX RDF	dual lattice, closest vector, root lattice, Lattice
49	Mårten Trolin	Lattices with Many Cycles Are Dense.	STACS	2004	DBLP DOI BibTeX RDF	lattices, shortest vector problem, closest vector problem
41	Uriel Feige, Daniele Micciancio	The Inapproximability of Lattice and Coding Problems with Preprocessing.	CCC	2002	DBLP DOI BibTeX RDF
36	Oded Regev 0001, Ricky Rosen	Lattice problems and norm embeddings.	STOC	2006	DBLP DOI BibTeX RDF	embedding, lattices, norms, hardness of approximation
35	Phong Q. Nguyen, Igor E. Shparlinski	The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces.	Des. Codes Cryptogr.	2003	DBLP DOI BibTeX RDF	cryptanalysis, distribution, lattices, elliptic curves, discrepancy, exponential sums, ECDSA, LLL, closest vector problem
35	Edwin El Mahassni, Phong Q. Nguyen, Igor E. Shparlinski	The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces.	CaLC	2001	DBLP DOI BibTeX RDF	Exponential Sums, DSA, Hidden Number Problem, Closest Vector Problem
35	Irit Dinur, Guy Kindler, Shmuel Safra	Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.	FOCS	1998	DBLP DOI BibTeX RDF	CVP, closest-vector, approximation, lattice
30	W. Chen, J. Meng	The Hardness of the Closest Vector Problem With Preprocessing Over ellinfty Norm.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
30	Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi	Hardness of Approximating the Closest Vector Problem with Pre-Processing.	FOCS	2005	DBLP DOI BibTeX RDF
26	Dmitry V. GRathoreribanov, Dmitriy S. Malyshev, I. A. Shumilov	Structured (min, +)-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems.	CoRR	2022	DBLP DOI BibTeX RDF
26	Priyanka Mukhopadhyay	Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in ℓp Norm.	Algorithms	2021	DBLP DOI BibTeX RDF
26	Priyanka Mukhopadhyay	Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in p norm.	CoRR	2019	DBLP BibTeX RDF
26	Divesh Aggarwal, Priyanka Mukhopadhyay	Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm.	ISAAC	2018	DBLP DOI BibTeX RDF
26	Chandan K. Dubey, Thomas Holenstein	Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle	CoRR	2011	DBLP BibTeX RDF
26	Chandan K. Dubey, Thomas Holenstein	Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
25	Nicolas Brisebarre, Sylvain Chevillard	Efficient polynomial L-approximations.	IEEE Symposium on Computer Arithmetic	2007	DBLP DOI BibTeX RDF	Efficient polynomial approximation, absolute error, L norm, floating-point arithmetic, LLL algorithm, lattice basis reduction, closest vector problem
25	Miklós Ajtai, Ravi Kumar 0001, D. Sivakumar 0001	Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.	CCC	2002	DBLP DOI BibTeX RDF	SVP, CVP, Lattice, shortest vector problem, closest vector problem
22	Chris Peikert	Limits on the Hardness of Lattice Problems in lp Norms.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	11H06, 94B75, 68Q25, Subject classification. 68Q17
20	Dmitry V. Gribanov, I. A. Shumilov, Dmitriy S. Malyshev	Structured $(\min ,+)$-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems.	Optim. Lett.	2024	DBLP DOI BibTeX RDF
20	Arnaud Girès Fobasso Tchinda, Emmanuel Fouotsa, Celestin Nkuimi Jugnia	A Polynomial Algorithm for Solving the Closest Vector Problem in Tensored Root Lattices of Type D.	SN Comput. Sci.	2023	DBLP DOI BibTeX RDF
20	Eduardo Canale, Claudio Qureshi, Alfredo Viola	Qubo model for the Closest Vector Problem.	CoRR	2023	DBLP DOI BibTeX RDF
20	Divesh Aggarwal, Rajendra Kumar 0002	Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!	FOCS	2023	DBLP DOI BibTeX RDF
20	Alfredo Braunstein, Louise Budzynski, Stefano Crotti, Federico Ricci-Tersenghi	The closest vector problem and the zero-temperature p-spin landscape for lossy compression.	CoRR	2022	DBLP DOI BibTeX RDF
20	Divesh Aggarwal, Rajendra Kumar 0002	Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms, and of the Subset Sum Problem!	CoRR	2022	DBLP DOI BibTeX RDF
20	Márton Naszódi, Moritz Venzin	Covering Convex Bodies and the Closest Vector Problem.	Discret. Comput. Geom.	2022	DBLP DOI BibTeX RDF
20	Wenbin Chen 0003, Jianer Chen	Approximating Closest Vector Problem in ℓ∞-Norm Revisited.	Comput. J.	2022	DBLP DOI BibTeX RDF
20	S. Thomas McCormick, Britta Peis, Robert Scheidweiler, Frank Vallentin	A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices.	SIAM J. Discret. Math.	2021	DBLP DOI BibTeX RDF
20	Thijs Laarhoven, Michael Walter 0001	Dual lattice attacks for closest vector problems (with preprocessing).	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
20	Thijs Laarhoven, Michael Walter 0001	Dual Lattice Attacks for Closest Vector Problems (with Preprocessing).	CT-RSA	2021	DBLP DOI BibTeX RDF
20	Tristram Bogart, John Goodrick, Kevin Woods	A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems.	SIAM J. Discret. Math.	2020	DBLP DOI BibTeX RDF
20	S. Thomas McCormick, Britta Peis, Robert Scheidweiler, Frank Vallentin	A polynomial time algorithm for solving the closest vector problem in zonotopal lattices.	CoRR	2020	DBLP BibTeX RDF
20	Márton Naszódi, Moritz Venzin	Covering convex bodies and the Closest Vector Problem.	CoRR	2019	DBLP BibTeX RDF
20	Wenbin Chen 0003, Jianer Chen	Approximating Closest Vector Problem in ℓ∞ Norm Revisited.	AAIM	2019	DBLP DOI BibTeX RDF
20	Léo Ducas, Wessel P. J. van Woerden	The closest vector problem in tensored root lattices of type A and in their duals.	Des. Codes Cryptogr.	2018	DBLP DOI BibTeX RDF
20	Ferdinand Blomqvist, Marcus Greferath	The Double-Plane Algorithm: A simple algorithm for the closest vector problem.	ISITA	2018	DBLP DOI BibTeX RDF
20	Saeid Sahraei, Michael Gastpar	Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward.	IEEE Trans. Inf. Theory	2017	DBLP DOI BibTeX RDF
20	Zhe Li, San Ling, Chaoping Xing, Sze Ling Yeo	On the Closest Vector Problem for Lattices Constructed from Polynomials and Their Cryptographic Applications.	CoRR	2017	DBLP BibTeX RDF
20	Zhe Li, San Ling, Chaoping Xing, Sze Ling Yeo	On the Closest Vector Problem for Lattices Constructed from Polynomials and Their Cryptographic Applications.	IACR Cryptol. ePrint Arch.	2017	DBLP BibTeX RDF
20	Daniel Dadush, Gábor Kun	Lattice Sparsification and the Approximate Closest Vector Problem.	Theory Comput.	2016	DBLP DOI BibTeX RDF
20	Léo Ducas, Wessel P. J. van Woerden	The closest vector problem in tensored root lattices of type A and in their duals.	IACR Cryptol. ePrint Arch.	2016	DBLP BibTeX RDF
20	Thijs Laarhoven	Randomized lattice sieving for the closest vector problem (with preprocessing).	IACR Cryptol. ePrint Arch.	2016	DBLP BibTeX RDF
20	Chengliang Tian, Wei Wei, Dongdai Lin	Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle.	J. Comput. Sci. Technol.	2015	DBLP DOI BibTeX RDF
20	Saeid Sahraei, Michael Gastpar	Polynomially Solvable Instances of the Shortest and Closest Vector Problems with Applications to Compute-and-Forward.	CoRR	2015	DBLP BibTeX RDF
20	Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz	Solving the Closest Vector Problem in $2^n$ Time - The Discrete Gaussian Strikes Again!	CoRR	2015	DBLP BibTeX RDF
20	Daniel Dadush, Nicolas Bonifas	Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing.	SODA	2015	DBLP DOI BibTeX RDF
20	Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz	Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!	FOCS	2015	DBLP DOI BibTeX RDF
20	Daniel Dadush, Oded Regev 0001, Noah Stephens-Davidowitz	On the Closest Vector Problem with a Distance Guarantee.	CoRR	2014	DBLP BibTeX RDF
20	Nicolas Bonifas, Daniel Dadush	Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing.	CoRR	2014	DBLP BibTeX RDF
20	Chengliang Tian, Wei Wei, Dongdai Lin	Solving closest vector instances using an approximate shortest independent vectors oracle.	IACR Cryptol. ePrint Arch.	2014	DBLP BibTeX RDF
20	Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi	Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.	SIAM J. Comput.	2014	DBLP DOI BibTeX RDF
20	Daniel Dadush, Oded Regev 0001, Noah Stephens-Davidowitz	On the Closest Vector Problem with a Distance Guarantee.	CCC	2014	DBLP DOI BibTeX RDF
20	Benjamin Fine, Anja I. S. Moldenhauer, Gerhard Rosenberger	A secret sharing scheme based on the Closest Vector Theorem and a modification to a private key cryptosystem.	Groups Complex. Cryptol.	2013	DBLP DOI BibTeX RDF
20	Anja Becker 0001, Nicolas Gama, Antoine Joux	Solving shortest and closest vector problems: The decomposition approach.	IACR Cryptol. ePrint Arch.	2013	DBLP BibTeX RDF
20	Daniel Dadush, Gábor Kun	Lattice Sparsification and the Approximate Closest Vector Problem.	SODA	2013	DBLP DOI BibTeX RDF
20	Daniel Dadush, Gábor Kun	Lattice Sparsification and the Approximate Closest Vector Problem	CoRR	2012	DBLP BibTeX RDF
20	Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi	2log1-ε n hardness for the closest vector problem with preprocessing.	STOC	2012	DBLP DOI BibTeX RDF
20	Daniele Micciancio	Closest Vector Problem.	Encyclopedia of Cryptography and Security (2nd Ed.)	2011	DBLP DOI BibTeX RDF
20	Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi	Hardness of Approximating the Closest Vector Problem with Pre-Processing.	Comput. Complex.	2011	DBLP DOI BibTeX RDF
20	Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi	2log1-έn Hardness for Closest Vector Problem with Preprocessing.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
20	Johannes Blömer, Stefanie Naewe	Solving the Closest Vector Problem with respect to ℓp Norms	CoRR	2011	DBLP BibTeX RDF
20	Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi	$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing	CoRR	2011	DBLP BibTeX RDF
20	Céline Engelbeen, Samuel Fiorini, Antje Kiesel	A closest vector problem arising in radiation therapy planning.	J. Comb. Optim.	2011	DBLP DOI BibTeX RDF
20	Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier	Covering cubes and the closest vector problem.	SCG	2011	DBLP DOI BibTeX RDF
20	Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier	Covering Cubes and the Closest Vector Problem	CoRR	2010	DBLP BibTeX RDF
20	Céline Engelbeen, Samuel Fiorini, Antje Kiesel	A closest vector problem arising in radiation therapy planning	CoRR	2009	DBLP BibTeX RDF
20	Wenbin Chen 0002, Jiangtao Meng	Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
20	Daniele Micciancio	Closest Vector Problem.	Encyclopedia of Cryptography and Security	2005	DBLP DOI BibTeX RDF
20	Daniele Micciancio	The hardness of the closest vector problem with preprocessing.	IEEE Trans. Inf. Theory	2001	DBLP DOI BibTeX RDF
20	Boleslaw K. Szymanski, Balaram Sinharoy	Corrigenda: Complexity of the Closest Vector Problem in a Lattice Generated by (0, 1)-Matrix.	Inf. Process. Lett.	1992	DBLP DOI BibTeX RDF
20	Boleslaw K. Szymanski, Balaram Sinharoy	Complexity of the Closest Vector Problem in a Lattice Generated by (0, 1)-Matrix.	Inf. Process. Lett.	1992	DBLP DOI BibTeX RDF
19	Yi-Kai Liu 0001, Vadim Lyubashevsky, Daniele Micciancio	On Bounded Distance Decoding for General Lattices.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
19	Johannes Blömer	Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices.	ICALP	2000	DBLP DOI BibTeX RDF
17	Daniele Micciancio, Salil P. Vadhan	Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More.	CRYPTO	2003	DBLP DOI BibTeX RDF
14	Daniele Micciancio	Improved cryptographic hash functions with worst-case/average-case connection.	STOC	2002	DBLP DOI BibTeX RDF
12	Thomas Plantard, Willy Susilo, Khin Than Win	A Digital Signature Scheme Based on CVPinfinity.	Public Key Cryptography	2008	DBLP DOI BibTeX RDF
12	Daniele Micciancio	Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	11H06, Subject classification. 68Q17, 94B15
12	Johannes Blömer, Stefanie Naewe	Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima.	ICALP	2007	DBLP DOI BibTeX RDF
12	Chris Peikert, Alon Rosen	Lattices that admit logarithmic worst-case to average-case connection factors.	STOC	2007	DBLP DOI BibTeX RDF	algebraic number theory, worst-case to average-case reductions, lattices
12	Chris Peikert	Limits on the Hardness of Lattice Problems in ell _p Norms.	CCC	2007	DBLP DOI BibTeX RDF
12	Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan	Concurrent Zero Knowledge Without Complexity Assumptions.	TCC	2006	DBLP DOI BibTeX RDF
12	Subhash Khot	Hardness of approximating the shortest vector problem in lattices.	J. ACM	2005	DBLP DOI BibTeX RDF	Approximation algorithms, cryptography, lattices, hardness of approximation, shortest vector problem
12	Subhash Khot	Hardness of Approximating the Shortest Vector Problem in Lattices.	FOCS	2004	DBLP DOI BibTeX RDF
12	Daniele Micciancio	Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection.	CCC	2002	DBLP DOI BibTeX RDF	worst-case/average-case connection, computational complexity, cryptography, hash functions, lattices
10	Walid Abdallah, Mohamed Hamdi, Noureddine Boudriga	A public key algorithm for optical communication based on lattice cryptography.	ISCC	2009	DBLP DOI BibTeX RDF
10	Daniele Micciancio	Efficient reductions among lattice problems.	SODA	2008	DBLP BibTeX RDF
10	Dorit Aharonov, Oded Regev 0001	Lattice problems in NP cap coNP.	J. ACM	2005	DBLP DOI BibTeX RDF	Algorithms, approximation, lattices, Fourier series
10	Domingo Gómez, Jaime Gutierrez 0001, Álvar Ibeas, Carmen Martínez, Ramón Beivide	On Finding a Shortest Path in Circulant Graphs with Two Jumps.	COCOON	2005	DBLP DOI BibTeX RDF
10	Phong Q. Nguyen, Damien Stehlé	Low-Dimensional Lattice Basis Reduction Revisited.	ANTS	2004	DBLP DOI BibTeX RDF
10	Dorit Aharonov, Oded Regev 0001	Lattice Problems in NP cap coNP.	FOCS	2004	DBLP DOI BibTeX RDF
10	SungJun Min, Go Yamamoto, Kwangjo Kim	Weak Property of Malleability in NTRUSign.	ACISP	2004	DBLP DOI BibTeX RDF	NTRUSign, Strong Existential Forgery, Centered Norm, Digital Signature Scheme, Malleability
10	Venkatesan Guruswami, Daniele Micciancio, Oded Regev 0001	The Complexity of the Covering Radius Problem on Lattices and Codes.	CCC	2004	DBLP DOI BibTeX RDF
10	Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra	Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.	Comb.	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 68Q17
10	Seong-Hun Paeng, Bae Eun Jung, Kil-Chan Ha	A Lattice Based Public Key Cryptosystem Using Polynomial Representations.	Public Key Cryptography	2003	DBLP DOI BibTeX RDF	GGH cryptosystem, lattice based public key cryptosystem, polynomial representation
10	Peter James Leadbitter, Nigel P. Smart	Analysis of the Insecurity of ECMQV with Partially Known Nonces.	ISC	2003	DBLP DOI BibTeX RDF
10	Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte	NTRUSIGN: Digital Signatures Using the NTRU Lattice.	CT-RSA	2003	DBLP DOI BibTeX RDF
10	Dorit Aharonov, Amnon Ta-Shma	Adiabatic quantum state generation and statistical zero knowledge.	STOC	2003	DBLP DOI BibTeX RDF	quantum adiabatic computation, quantum sampling, spectral gap, state generation, statistical zero knowledge, Markov chains, Hamiltonian
10	Oded Regev 0001	Improved Inapproximability of Lattice and Coding Problems with Preprocessing.	CCC	2003	DBLP DOI BibTeX RDF
10	Phong Q. Nguyen, Igor E. Shparlinski	The Insecurity of the Digital Signature Algorithm with Partially Known Nonces.	J. Cryptol.	2002	DBLP DOI BibTeX RDF
10	Roger Fischlin, Jean-Pierre Seifert	Tensor-Based Trapdoors for CVP and Their Application to Public Key Cryptography.	IMACC	1999	DBLP DOI BibTeX RDF