為什麼格加密可以抵抗量子計算機？
量子計算機
補一個 Lior Eldar 上個月在 MSR 關於 systematic normal form of lattices 的 talk 吧: youtube.com 的頁面
--------------------------------------------------------------
在 Nov 24 已經被暫時撤稿了, 被 Oded Regev 指出了致命 bug. 期待 Peter Shor 和 Lior Eldar 能 make the algorithm great again...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
BTW, 加上去年 NTLS conjecture 的證明有 bug, Lior 也是夠倒霉的......
--------------------------------------------------------------來個大新聞。。
[1611.06999] An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem
關於最高票答案的論文[1611.06999v1] An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem最新的討論參見Google Group - Cryptanalysis Algorithms，包括了Oded Regev發現錯誤的聲明Regarding the arXiv preprint of Eldar and Shor以及Lior Eldar關於演算法目前進展的說明Status of our algorithm還有D.J.Bernstein等人的討論gapBDD broken with poly approx factors?
當然本渣並看不懂，以及非常好奇這個Group為什麼有這麼多牛掰的大神。。
反正如果Shor最後真的"make the algorithm great again"，那我就該換研究課題了。。
-------------------
咦怎麼票數上來了。。那就說是某匿名用戶的答案吧（無法確實地證明，目前清楚的只有
然而整數分解肯定是 BQP 了，所以還是換掉比較好
由於目前沒有多項式時間的演算法解決格上困難問題，包括量子計算機，所以格密碼被認為是抗量子的
推薦閱讀：