HackerPapers

arXiv:1611.06999quant-ph

An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem

Lior Eldar, Peter W. Shor

Abstract

The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor '16], in which the basis entries satisfy a certain co-primality condition. Using a "smooth" analysis of lattices by SysNF lattices we design a quantum algorithm that can efficiently solve the following variant of the bounded-distance-decoding problem: given a lattice L, a vector v, and numbers b = λ_1(L)/n^{17}, a = λ_1(L)/n^{13} decide if v's distance from L is in the range [a/2, a] or at most b, where λ_1(L) is the length of L's shortest non-zero vector. Improving these parameters to a = b = λ_1(L)/\sqrt{n} would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.

arXiv comments
This paper has been withdrawn by the author due to an error in Fact 7: the concentration of measure of the n-dimensional sinc^2 function is not a probability of at least 1-n^{-3} for vectors of length at most n^2, but rather 1 - n^{-1.5} for vectors of length n^3
Journal reference
DOI
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Dec 2016 to May 2017. Found in 1 HN submission from Nov 2016 to Nov 2016. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Post-quantum RSA 1 comment

    • Thats a good paper. I thought about it awhile and would retract my remarks of it being expensive and replace it with being expensive or risky. Also there's the problem of "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ", and maybe…

      VLMView on HNParent context

  2. Library-managed 'arXiv' spreads scientific advances rapidly and worldwide 1 comment

    • Here's an example: https://arxiv.org/abs/1611.06999 I believe the PDF link is only removed after a paper has been withdrawn. But if you click on v1, you can still access the original paper (incorrect, in this case).

      greeneggsView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.