##### 👈 [[12024-04-13]] | 🕰️ 12023-04-15 🕰️ | [[12024-04-17]] 👉 ### [[Journal]], 12 024, Uke 16, mandag #### 1: Interessante slides fra Nadias talk at [[PKC'24]] To-do: extract to evergreens ![[IMG_5670.jpeg]] ![[IMG_5671.jpeg]] ![[IMG_5672.jpeg]] ![[IMG_5673 1.jpeg]] ![[IMG_5674 1.jpeg]] ![[IMG_5675 1.jpeg]] ![[IMG_5676 1.jpeg]] ![[IMG_5677 1.jpeg]] ![[IMG_5678.jpeg]] ![[IMG_5679.jpeg]] ![[IMG_5680 1.jpeg]] ![[IMG_5681 1.jpeg]] ![[IMG_5682.jpeg]] ![[IMG_5683.jpeg]] ![[IMG_5684.jpeg]] ![[IMG_5685.jpeg]] ![[IMG_5686.jpeg]] ![[IMG_5687.jpeg]] ![[IMG_5688.jpeg]] ![[image 6.jpg]] ![[image 7.jpg]] ![[image 8.jpg]] ![[image 9.jpg]] ![[image 10.jpg]] - (NB: pre eprint 555) ![[image 11.jpg]] ![[image 12.jpg]] Tanker: - Veldig interessant at relevante forskere formoder at både faktorisering og dlog sin «korrekte» klassiske kjøretid er pseudopolynomial. Samme som [[Graph Isomorphism]]! - Dette ville for det første «brutt» [[Shors algoritme]], og satt tvil til hvorvidt [[Kvantedatamaskiner]] kan gi eksponentiell (fremfor «bare» superpolynom) speedup til tallteoretiske problemer. - Et par naturlige formodninger følger: - [[NP snitt coNP]] $\subseteq$ [[BQP]] (ingenting nytt med denne formodningen) - Men: Alle problemer i [[NP snitt coNP]] tillater pseudopolynome klassiske algoritmer. (Denne er ny—og ambisiøs!) - Formodningen impliserer at [[Learning with errors]] og [[Shortest Vector Problem]] (som nå ser ut til å kanskje ligge i [[BQP]]) også tillater pseudopolynome algoritmer. - Hvor ligger [[Isogenies]] i dette landskapet? #### 2: «PKC 2024 Surprise Panel» om [[Chens algoritme]] - Penalist introductory opinions - 1st penalist, Long Chen - Don’t believe the algorithm (even if correct) will eventually be able to fully break [[Learning with errors]]. - This is because if the error is very large compared to the modulus, you will eventually get statistical hardness. So at some point the algorithm must stop anyway. (Question is then, how far can we push it?) - 2nd, Gabrielle De Michelli - Curious about, if there is an error in this paper, it is fundamental or patcheable. Also, to what degree the algorithm can be improved and the result pushed. Big question: Is the fundamental idea of the algorithm correct? - 3rd, Nadia Heninger - «The most interesting thing about this paper is that it is posted online, and it is clearly a huge result, and nobody understands it.» - «Even the people who have co-authored papers with this author don’t understand this paper.» - The probability that there is a mistake in the 50 pages of walls of formula is probably 1. Question, again, is, will it be a fundamental or a superficial/patcheable bug? - If it is under submission, will the three random reviewers be able to understand it? - 4th, Daniele Micciancio - Problem: We can’t even *test* the algorithm on smaller instances. - Kunne man gjort eksperimenter for små instanser med $\leq$ 30 qubits, og dermed simulere klassisk? - It will take some time to figure out whether it is correct or not. - Let’s assume it is correct. Two possibilities: Approximate lattice problems in polynomial time within $n^{4.5}$. - Han sier mer om approximation factors, hele «possibility 1» virker interessant, hør igjen og transkriber. «The optimistic possibility.» - Second possibility, nightmare scenario: We may be in a world where post-quantum encryption *does not exist*. That it is not about lattices, but more fundamental. «I don’t know which one is more likely of the scenarios, but I can tell you which world I *want* to be in.» - Question: How to respond? - Daniele: *If* PKE does not exist, we have to seriously consider how to respond. - Nadia: Historical options, two options, key distribution centres, which enables surveillance. [[Kvante-nøkkelutvidelse]] (men kanskje autentisert med post-kvante signaturer som FAEST), but this *also* enables surveillance, because it is a point-to-point protocol! - Question: What do we do about the problem that there are only 5 people who understand this? - Nadia: «Giant piles of money.» - Daniele: «I don’t think this is enough—» Nadia: «If someone gave you $10M, would you not drop everything and learn enough quantum to read this paper?» Me (thinking): «If you get $10M funding to work on this please call me.» - Nadia: «I’ll expand a little on the giant piles of money.» It enables a lot of things, including time, and students that can spend years becoming experts, you can organize specialized schools. There *is* a gap. There are a lot of people doing quantum algorithms, and a lot of people doing cryptanalysis, but the overlap between them is very small. We need funding to ensure that we have a few hundred people that spend all their time thinking about quantum algorithms for lattice problems, etc. - Daniele: (later on) «People should write proofs to make them readable, and not just leave them as technical details after spending most of the paper on the story.» (…) «Might be useful to try to move our proofs in the direction of being machine checkable.» - Nadia: «I would like to propose an intermediate world, in which the proof of runtime in the algorithm is not quite correct, and it turns out to run in *subexponential* time. Which would put us all in limbo, as why people are excited about lattices is the exponential hardness (and parameters might be prohibitively large). I think this would be the least stable scenario, and might stay such for a long time.» - Daniele: «The algorithm solves lattice problems for *arbitrary* lattices, with *polynomial* approximation factor. This is surprising to me: I would expect that if a quantum algorithm came out for lattice problems, it would be (as a first step) either with subexponential approximation factors or for specialized lattices only.» (Hallgren’s proposed algorithm was like this?)