An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor

[daniel.apon]

Hi all,

I felt it was important to let the community know that there is a talk + panel scheduled for tomorrow (Tuesday) on a seemingly important, new quantum algorithm for lattice problems. The talk is hosted by the Simons Institute for the Theory of Computing in Berkeley, CA, USA, and is open to the public.

Details below.

----------------------------------------

Tuesday, September 21. (~ 2pm-4pm Eastern / NIST time)

An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor

Speaker: Sean Hallgren (Penn State University & Senior Visitor at Simons Institute 2021-22)

11:00 am – 12:30 pm (Pacific / local time)
2:00 pm  – 3:30pm (Eastern / NIST time)

Panel on Lattice Algorithms and Cryptography

Speaker: Panel featuring Lior Eldar (MIT), Vinod Vaikuntanathan (MIT), Daniel Apon (NIST), Umesh Vazirani (UC Berkeley; moderator)

12:00 pm – 1:00 pm (Pacific / local time) //that is, following the talk
3:00 pm – 4:00 pm (Eastern / NIST time)

Talk Abstract:  We give a polynomial-time quantum algorithm for solving the Bounded Distance Decoding problem with a subexponential approximation factor on a class of integer lattices.  The quantum algorithm achieves an exponential speedup compared to the best known classical algorithm, and is the first example of an exponential speedup on a general lattice problem not connected to number theory.

Public Zoom webinar link: https://berkeley.zoom.us/j/95040632440


----------------------------------------

My hope is that the talk + panel will be recorded and available later to all. (I've requested that Simons do this.)

For those who are unable to attend, I also plan to briefly summarize my thoughts in this thread after the event.


Cheers,
--Daniel Apon

[daniel.apon]

Video of the event is publicly available on YouTube at the following two links:

https://www.youtube.com/watch?v=K5Apl_qCnDA
https://www.youtube.com/watch?v=Jg--I064WFU

A future message Soon™ from me (or others) in the community will discuss the state of the technical content further.

[Jacob Alperin-Sheriff]

Finally vindication for Daniel Bernstein has been achieved! (I have not watched the talk yet)

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/076fec6b-3d80-4580-90fb-b333c86223ccn%40list.nist.gov.

--

-Jacob Alperin-Sheriff

[Leo Ducas]

Dear PQCer,

following up on the presentation, Wessel and myself wrote a note
on what the state of the art has to say on those specific BDD
instances studied by Lior and Sean.

The note is available at:
https://github.com/lducas/BDD-note/blob/main/note.pdf

A first remark is that these instances are already considered easy
in the average-case for standard classical lattice reduction algorithms.
We can in fact prove this is also true in the worst-case. This requires
no new idea, only due diligence. The algorithm is just straight up
LLL+Babai.

FAQ.

** Does the note contain a new result on lattice problems ?

No. There is only a sudden focus on specific worst-case instances
that were previously undocumented, simply because the average-case
was the case of interest in crypto.

** Does the fact that it is a worst-case result invalidate the
underlying worst-case to average-case reasoning ?

No. Ajtai's and Regev worst-case reduction ranges over *all*
lattices. This polynomial time algorithm applies to a small
class of easy lattices.

** The note only deal with the case k=1, and q = c^n. What about
the general case ?

We will generalize the note as soon as we find the time to do so.
In the mean time, the best guess is that it would behaves as in
the random-case (LWE): BDD in deterministic poly-time for this
class of lattices when parameters satisfies:

    k * log(q) / log^2(α) > cste .


Best regards
-- Léo

[Leo Ducas]

    k * log(q) / log^2(α) > cste .

I obviously meant "< constant".

[daniel.apon]

In the interest of providing free and fair access to public technical information, I refer everyone to additional, expert discussions on this topic at: https://crypto.stackexchange.com/questions/95187/what-does-the-work-an-efficient-quantum-algorithm-for-lattice-problems-achievin

Best,
--Daniel Apon

[Sean Hallgren]

I responded with the timeline of events here:

https://crypto.stackexchange.com/questions/95187/what-does-the-work-an-efficient-quantum-algorithm-for-lattice-problems-achievin

I created a website to crowdsource what is known about algorithms for lattice problems in NP intersect CoNP:

https://latticealgorithms.xyz

Our paper is up:

https://arxiv.org/abs/2201.13450

Sean

[Phong Nguyen]

Le 1 févr. 2022 à 20:17, Sean Hallgren <seanha...@gmail.com> a écrit :

I responded with the timeline of events here:

https://crypto.stackexchange.com/questions/95187/what-does-the-work-an-efficient-quantum-algorithm-for-lattice-problems-achievin

I created a website to crowdsource what is known about algorithms for lattice problems in NP intersect CoNP:

https://latticealgorithms.xyz

Our paper is up:

https://arxiv.org/abs/2201.13450

Thanks for posting your paper: 

it’s nice to see new attempts at solving hard lattice problems.

As this may be of interest to other people in the forum,

I would like to comment that the partition of lattices you are using

is directly related to the one of [GINX16].

Let me briefly recall [GINX16].

If L is a full-rank lattice in Z^n, then Z^n/L is a finite abelian group G,

which leads to a natural partition of integer lattices when G runs over all finite abelian groups,

as well as a natural distribution: for a fixed G, choose uniformly at random

a full-rank lattice L in Z^n such that  Z^n/L is isomorphic to G.

Essentially, the generalization GSIS of SIS asks to find a short nonzero vector in such a random lattice L,

and the generalization GLWE of LWE asks to solve a randomized version of BDD in the dual lattice L*.

[GINX16] gives worst-case to average-case reductions from worst-case lattice problems

to GSIS and GLWE.

 

In your paper, you let L be a full-rank lattice in Z^n.

Your periodicity q is the exponent of the finite group Z^n/L.

Then the dual lattice L* is of the form M/q for some full-rank lattice M in Z^n.

You consider the finite group G=L/(qZ^n).

Then G is isomorphic to (q^{-1}L)/Z^n,

which by duality is isomorphic to Z^n/((q^{-1}L)* = Z^n/M

So your partition corresponds to the one of [GINX16] with respect to the integer dual M.

Best regards,

Phong