木字旁一個行人的行怎麼念
1994年，著名
計算機
科學家、
麻省理工學院
的應用數學系教授
彼得·秀爾
提出了在
量子電腦
應用上的“
秀爾演算法
”，又稱
量子質因數分解演算法
，因其證明量子電腦能做出對數運算，而且速度遠勝傳統電腦，對於現在通行於銀行及網路等處的
RSA加密演算法
可以破解而構成威脅。
也就是說，
如果有一天量子計算機被真正發明出來，它們將摧毀今天的許多用於保護線上共享資訊的基礎設施。這種可怕的可能性使科學家們爭先恐後地製作新的
"後量子"加密方案
，以儘量避免資訊落入量子駭客的手中。
如果今天的密碼協議失敗，就不可能保護線上連線傳送機密資訊、進行安全的金融交易或驗證資料。任何人都可以訪問任何東西；任何人都可以偽裝成任何人。數字經濟將崩潰。
當或者如果功能齊全的量子計算機可用時，這正是可能發生的事情。美國國家標準與技術研究院 （NIST） 於 2017 年發起了一項國際競賽，以尋找實現“後量子”密碼學的最佳方法。上個月，評選出了第一批獲勝者：
四個參賽入圍方案，其中有三個使用“
格密碼
”，這是一種受格啟發的方案，即空間中點的規則排列。
基於格密碼是涉及格的密碼原語構造的通用術語，無論是在構造本身還是在安全證明中。基於格的結構目前是後量子密碼學的重要候選者。與更廣泛使用和已知的公鑰方案不同，例如RSA、Diffie-Hellman或橢圓曲線密碼系統，理論上可以在量子計算機上使用Shor 演算法擊敗，一些基於格的結構似乎可以抵抗經典計算機和量子計算機的攻擊。此外，在某些經過充分研究的計算格問題無法有效解決的假設下，許多基於格的結構被認為是安全的。
格密碼和其他後量子可能性在關鍵方面與當前標準不同。但它們都依賴於數學上的不對稱性。目前許多密碼系統的安全性是基於乘法和因式分解。任何計算機都可以快速地將兩個數字相乘，但要將一個密碼上的大數字分解成其素數，可能需要幾個世紀。這種不對稱性使得秘密容易編碼，但難以解碼。
肖爾在他1994年的演算法中所揭示的是，因式分解的一個怪異是使其容易受到量子計算機的攻擊。“科羅拉多大學博爾德分校的數學家凱瑟琳-斯坦格說：”這是量子計算機能做的一件非常具體、特殊的事情。因此，在肖爾之後，密碼學家們有了新的工作。找到一套新穎的數學運算，這些運算很容易做，但幾乎不可能被撤銷。
格密碼是迄今為止最成功的嘗試之一。它最初是在1990年代開發的，依靠的是對點的總和進行反向工程的難度。
格密碼的數學背景：
格密碼的工作原理：
有人可能會問，
格密碼具體是如何
實現
量子安全的，可以免受未來量子計算機攻擊？下面我們透過簡單例子來解釋它的工作原理。
下面是描述格密碼的一種方法。想象一下，你的朋友有一個格，這只是一堆在平面上有規律、重複的點。你的朋友想讓你說出這些點中的10個。但他很為難，他不會畫出整個格。相反，他只列出了兩個點，第一個點的X值為101，Y值為19，另一個點的座標為［235， 44］。
幸運的是，在格上找到新的點很容易，因為當你在格上加減任何兩個點時，你會在同一個格上得到第三個點。所以你要做的就是把你朋友給你的點加起來，或者把它們乘以整數，然後再加起來，或者這兩者的組合。這樣做了八種不同的方法，你就能回答你朋友的問題了。
但是你的朋友仍然不滿意。他給了你同樣的兩個起點，然後問你是否能在同一格上找到靠近［0，0］的點。 為了正確回答這個問題，你必須找到［101，19］和［235，44］的組合，使你接近［0，0］。這個問題比第一個問題要難得多，你最終可能只是猜測和檢查來得到答案。這種不對稱性是格密碼的基礎。
如果你真的想用格密碼來分享資訊，你
可以執行以下操作
。想象一下，一個朋友（一個比較好的朋友！）想給你傳送一條安全資訊。你從一個正方形的數字網格開始。假設它有兩行和兩列，看起來像這樣：
現在你想出了一個只有你自己知道的“私鑰”。在這個例子中，我們假設你的私鑰只是兩個秘密數字：3和-2。你將第一列中的數字乘以3，第二列中的數字乘以-2。 將每一行中的結果相加，得到第三列中的兩個條目。
把新的一列貼在你的網格的末端。這個新的三列網格就是你的公鑰，可自由地分享它。
（實際情況會稍微複雜一些。為了防止駭客破譯你的私鑰，你必須在最後一列加入一點隨機噪音。但在這裡，為了簡單起見，我們將忽略這個步驟）。
現在你的朋友將使用公鑰向你傳送一條資訊。她想到了她自己的兩個秘密數字：2和0。她把第一行的數字乘以2，第二行的數字乘以0，然後把每一列的結果加起來，得到第三行。
現在她把新的一行附在網格的底部，並把它送回給你。（同樣，在一個真實的系統中，她需要在她的行中加入一些噪音）。
現在你將閱讀這個資訊。要做到這一點，你要檢查一下你朋友的最後一行是否正確。將你自己的私鑰應用於她那一行的前兩個條目。結果應該與最後一個條目相符。
你的朋友還可以選擇在最後一列中向你傳送帶有錯誤數字的行。她知道這個數字與你的計算不符。
如果你的朋友傳送的最後一
行
數字是正確的，你會把它解釋為0；如果她傳送的數字是錯誤的，你會把它解釋為1。
該行編碼一個位：0 或 1。
請注意，外部攻擊者無法獲得你和你朋友的私鑰。沒有這些，攻擊者將不知道最後的數字是否正確。
在實踐中，你希望傳送的資訊長於1位元。因此，想要接收100位資訊的人將產生100個新列，而不是隻有一個。然後，資訊的傳送者將建立一個新的行，修改最後100個條目，為每個條目編碼一個0或1。
如果實際地實現格密碼，會有無數的細微差別沒有被涵蓋在這個方案中。例如，如果你想讓資訊真正不被窺視，矩陣需要有一個難以想象的條目數，使整個事情變得如此不容易而不值得使用。為了解決這個問題，研究人員使用具有有用的對稱性的矩陣，可以減少引數的數量。除此之外，還有一整套的調整，可以應用於問題本身，以及納入誤差的方式，等等。
當然，總是有可能有人會在格密碼中找到一個致命的缺陷，就像肖爾對因式分解所做的那樣。我們無法保證一個特定的加密方案在面對任何可能的攻擊時都能發揮作用。密碼在被破解之前總是有效的。
事實上，在今年7月30日，
一個有前途的後量子密碼方案不是用量子計算機，而是用一臺普通的膝上型電腦被破解的。
許多人認為該協議是對抗量子計算能力的一種有希望的防禦措施。
兩名研究人員在一小時內用膝上型電腦破解了該加密協議。從那以後，其他人使攻擊速度更快，在幾分鐘內就予以破解。
數學家和計算機科學家Steven Galbraith評價說，“如此戲劇性和強大的攻擊……令人震驚，”攻擊背後的數學不僅令人驚訝，而且還減少了後量子密碼學的（急需的）多樣性。
結果讓後量子密碼學界既震驚又鼓舞。