1樓:六三
基於格的難題你只說了乙個RLWE,不知你是不是已經了解基於格的其它難題。引用剛才在另外乙個問題中的回覆。
讓我們定義最基本的涉及格的計算難題:最短向量問題,簡稱 。 在這裡,我們給出了乙個格,需要我們找到最短的非零格點。
更準確地說,有三個變體,這取決於我們是否必須實際找到最短的向量,找到它的長度,或者僅僅取決於它是否比某些給定的數字小:
Search: 給定格基 求 ,使 。
Optimization: 給定格基 ,找到 。
Decisional:給定格基 和有理數 ,判斷是否成立。
注意,我們限制格基由整數向量組成,而不是任意的實向量。這樣做的目的是使輸入以有限的多位表示,這樣我們就可以將 視為乙個標準的計算難題。我們還可以允許格基由有理向量組成。
這將導致乙個本質上等價的定義,因為通過縮放,可以使所有有理數座標都是整數。
上述三個變體之間的兩個簡單關係是,決策變體不比優化變體更難,優化變體不比搜尋變體更難。 事實上,可以證明逆向也是正確的:優化變數不比決策變數更難,搜尋變數不比優化變數更難。
總之,這三個變體本質上是等價的。
另乙個基本格難題是最近的向量問題,簡稱 ,i.e.,目標是找到最接近給定空間點的格點。 和以前一樣,對於任何近似因子 ,我們可以定義三個變體:
Search: 給定格基 和向量 ,查詢 使得 。
Optimization:給定格基 和向量 ,求 使。
Promise: 由 a triple 給出乙個難題例項,其中 是格基, 。 在 YES 例項中, 。在沒有情況下, 。
Membership: 給定格基 和向量 ,decide 是否屬於 。 方程 可以看作是 個變數中的 線性方程組。
因此,我們可以通過高斯消除來有效地解決它。 如果乙個解存在,並且它恰好在 (as opposed to )中,則輸出YES;否則輸出NO。
Equivalence: 給定格基 , decide if 。 為了解決這個問題,我們檢查了兩件事:
的每一列都包含在 中, 的每一列都包含在 中。 如果 ,則滿足這兩個檢查。 相反,如果滿足這些檢查,則 和 ,因此 。
2樓:愈學就愈發現自己無知
靠譜的假設:
加密:格(RLWE/LWE)、子集求和、糾錯碼。。。
簽名:格、Hash。。。
金鑰協商:格、糾錯碼、子集求和。。。
應用:零知識、UC、Random Oracle等等其中,多變數的提案很少活過5年,無已知安全的基於編碼的簽名方案。同源等等新假設沒有經過實踐檢驗。
3樓:
推薦一本書《post quantum cryptography》
code-based
hash-based
lattice-based
multivariate
LWE,LPN當然也是抵抗量子計算機攻擊的
4樓:Qian Chen
NIST 前段時間召集post-quantum 的非對稱標準。
主要三個候選:
Multivariant systems,Code based crypto,
LWE.
5樓:黑照
零知識證明與圖同構問題。
ZERO-KNOWLEDGE。
圖是資料結構裡面的圖,由點和邊組成的結構。然後對點進行編號,記錄點與邊的資料比如這裡有n個點記為a1、a2.。。an同時記錄點與邊的關係比如a1->a3,然後對點換乙個名字再記錄b1、b2。。
bn與點與邊的關係。
那麼這兩個圖顯然是一樣的。(廢話,出自同一張圖)。
這個時候問題來了,請找出a1到an分別對應b1到bn的那個點?
這個問題的計算複雜度是O(n!)
你沒看錯。這個問題的計算複雜度就是O(n!)。因為只有窮舉才能解決。哪怕排序也可能出現某點和其他點的某些一樣的地方(比如點的度,最短路徑、介數等等)。
這個是乙個密碼學問題。因為你可以把資料隱藏到點與邊的關係中同時設定一大堆的多餘點和邊。同時任何乙個數學問題都可以轉化為乙個圖問題。
對這個問題的證明相當於找到乙個漢密爾頓圈。
通過零知識你可以給對方演示證明過程,但是對方沒有辦法掌握這個證明。
國內研究零知識的有很多。我還是傾向於推薦外國的研究。
6樓:xchen
代數幾何裡面有不少把,經典的elliptic curve,最近的是bilinear map和multilinear map(http://
eprint.iacr.org/2013/451.pdf
). 這些都是道聽途說來的,自己從沒讀過,有些我也不知道reference也可能記錯了。
量子計算機屬於幾進製?
苦逼青年DB 量子有多種自旋態,可以表示多進製位,然後就可以做成多進製計算機,二進位制也屬於多進製中 具體採用幾進製還沒有定則,要看目前各個專案的具體設計 sari 不能用進製衡量,是一種狀態疊加,倒不是0或1的疊加,而是介於0和1的無數種可能性,量子科學不是具象科學,不能確定狀態。至少對於觀測者而...
量子計算機模擬出的世界是否可以產生具備意識的類似人的這種生物?
Larry 意識本來就是一堆邏輯和資訊而已,這些邏輯和資訊由你大腦裡的神經元承載。甚至你手機的siri都能算一種簡單邏輯的意識,不信你騙乙個5歲小朋友說siri是真人,他肯定信。至於量子計算機能不能模擬真實世界,我覺得理論上可以,但實際上很難。因為現實世界中任何乙個粒子都涉及量子力學的計算,所以計算...
量子計算機會取代人們家中的普通計算機還要經過多少年?
本源量子 量子計算機不會取代經典計算機,而是與經典計算機融合發展,解決目前無法完成的超大規模資料的處理。從目前的技術路徑來看,量子計算機需要足夠穩定的執行環境才能避免外界雜訊干擾,這意味著量子計算機需要製冷裝置,需要大量的能源消耗。從這一點來看,量子計算機不太可能像家用計算機一樣。當然,我們可以通過...