Lattice-Crypto
SIS 的 ZK 證明
設Ax=0modq $ A x = 0 \bmod q $ 和‖X‖<b $ \Vert x \Vert < \beta $ 作為格 SIS 問題的一部分。這種解決方案是否存在有效的零知識知識證明？
我的想法是將它用於身份驗證協議。但是到目前為止我看到的所有 ZK 協議都是承諾或差距 問題。由於這個差距，我看不到如何建構身份驗證協議。因為攻擊者有一個解X $ x $ 且X>b $ x > \beta $ 但X $ x $ 在間隙內的攻擊者也可以說服驗證者。
如果您對基於格的（..和非互動式..）零知識感興趣，最新技術來自2008 年的一篇論文（是的，2008 年..），可在此處找到：https://web。 eecs.umich.edu/~cpeikert/pubs/latticeNISZK.pdf
從格中獲取 NIZK 是一個主要的開放性問題。（據我們所知，您可能必須一直使用多線性映射和 P/poly 的 IND 混淆才能獲得“格狀”形式的 NIZK。）
如果您需要的不僅僅是該論文中的 SZK，則必須使用非 SIS、非 LWE 解決方案（或者，您可以花大價錢自己從 LWE 建構 NIZK！）
“我知道一個X $ x $ 使得一個X=0反對q $ Ax = 0,\text{mod},q $ 和‖X‖<b $ \Vert x\Vert < \beta $ ”這句話在 NP 中很明顯，所以任何 zkSNARK 都可以給你這樣的證明，例如這篇論文. 雖然，這是知識論據（不是知識證明），但兩者之間似乎幾乎沒有實際區別。
如果你不喜歡不可證偽的假設，你可以從一個通用的 ZKP 為你的 SIS 聲明開始（例如從這篇不錯的最近論文建構），然後使用標準轉換將其編譯成知識證明。