Number-Theory
如何構造多個形式的零知識證明n=p一種qbn=p一種qbn=p^a q^b
讓 $ n = p^a $ $ q^b $ 其中 p 和 q 是不同的素數， a 和 b 是正整數。如何構造一個零知識證明 n 具有這種形式？
這實際上是一個家庭作業問題，暗示如果一個 $ n = p^a $ $ q^b $ 然後恰好是一半的元素 $ Z_n $ 帶有 jacobi 符號 +1 的是二次殘差 mod n，我們假設最初驗證者知道帶有 jacobi 符號 +1 的二次非殘差 x。
我堅持在那裡，因為似乎很難說服 Verifier n 具有給定的形式。這不僅僅是在 Verfier 向 Prover 發送挑戰號之後，Prover 表明他知道挑戰號是 QNR 還是 QR 的事實。讓我說服 Verfier 所有 jacobi +1 元素必須在 $ Z_n $ 並且 Prover 已經證明其中有一半是 QR。（假設 Verifier 可以用 x 本身生成，因此它不違反零知識。但我不確定生成所有 Jacobi +1 元素是否容易（多項式耗時）。好吧，如果我們讓 $ z = r^2 $ 對於從隨機挑選的 r $ Z_n $ 然後 $ y = r^2x $ 也是一個帶有 jacobi 符號 +1 的 QNR…因此，對於驗證者來說，找到另一個帶有 jacobi 符號 +1 的 QNR 很容易…）但是要顯示“正好一半”，那麼 Prover 需要顯示哪個是 QR，哪個是QNR 那麼它將違反零知識屬性，因為假設 V 不知道這一點。但是還有其他方式來顯示“正好一半”嗎？
非常感謝任何提示或幫助。謝謝！
實際上，證明者沒有必要證明 Jacobi 符號為 +1 的元素中“恰好一半”實際上是 QR。相反，這裡有一些提示：
- 假設 n 不是那種形式（並且 n 也不是那種形式 $ n = p^a $ , 這很容易測試), 具有 Jacobi 符號 +1 的隨機元素是 QR 的機率最多為 $ q $ （給你的家庭作業：價值是什麼？ $ q $ )
- 如果我們得到一個值 $ x $ 從作為 QR 的驗證者中，我們如何以零知識的方式顯示 $ x $ 是一個 QR（機率 $ > 1 - \delta $ )?
- 如果提供者給我們一系列隨機 $ x $ 的，我們要麼回應每一個 $ x $ 帶有“不是二維碼”或“它是二維碼”；這是機率為零的知識證明 $ > 1 - \delta $ ‘，在驗證結束之前需要多少次隨機元素的試驗（機率 $ > 1 - \epsilon $ ) Jacobi 符號 +1 元素的分數是 QR 是 $ > q $ ?