兩個素數乘積的 ZKP
我正在努力從以下論文中理解這個證明的零知識的直覺。
證明是 2 輪，驗證者要求證明者提取二次殘差的平方根。
我已經閱讀了 HVZK 證明（如下圖所示），並且我同意您可以生成像普通證明一樣分發的成績單，但是我仍然無法克服一個簡單的事實：
- 沒有見證（分解），您無法提取平方根模 $ N $ .
- 當通過 Fiat-Shamir 轉換將證明轉換為 NIZK 時，證明者在證明中以原始形式記錄平方根，因此驗證者可以學習以前無法自行計算的組中數字的平方根。
這不是“知識”洩露嗎？為什麼這個證明可以變成 NIZK？
提前謝謝了。
我正在猜測：
“HVZK”代表“誠實驗證者零知識”，對吧？您的反對意見是不誠實的驗證者可以隨機選擇 $ x_i $ , 計算 $ \rho_i\equiv x_i^2\mod N $ ，然後當他們得到 $ \sigma_i $ 從證明者那裡，有一個 $ 1/4 $ 機會 $ gcd(\sigma_i-x_i,N) $ 是一個重要的因素。但是誠實的驗證者應該隨機生成 $ \rho_i $ .
這應該是安全的，基於以下幾點：假設 $ A $ 是一種可以因式分解的算法 $ N $ 隨機給定 $ \rho_i $ 和 $ \sigma_i $ 這樣 $ \sigma_i^2\equiv \rho_i\mod N $ . 然後我們可以考慮任何 $ N $ 和 $ A $ 通過隨機選擇 $ \sigma_i $ , 計算 $ \rho_i\equiv\sigma_i^2\mod N $ , 並發送 $ \rho_i $ 和 $ \sigma_i $ 至 $ A $ .
Fiat-Shamir tansform 應該能夠將 HVZK 轉換為 NIZK（可能需要一些額外的條件），這在直覺上似乎是正確的。HVZK 可能會失敗，因為不誠實的驗證者可以發送“危險”的挑戰來揭示資訊，但 Fiat-Shamir 強制挑戰是隨機的。只要這種危險的挑戰足夠罕見，那麼 Fiat-Shamir 變換就應該產生 NIZK。
因此，驗證者可以學習之前無法自行計算的組中數字的平方根。
通過 Fiat-Shamir 變換，這些根將是隨機數。學習者可以很容易地通過隨機抽樣來計算這些 $ x $ 和計算 $ x^2 $ （模組 $ N $ ）。這種分佈與 $ (\sqrt{x},x) $ 將在協議中給出的對。