在零知識中證明未知階組中離散對數的“符號”
假設我們有一個組的描述 $ \mathbb{G} $ ，一組未知順序：該組的大小未知。例如，一個 RSA 組 ( $ \mathbb{Z}^{*}_N, $ 在哪裡 $ N=pq $ 對於未知素數 $ p $ 和 $ q $ ) 或類組。證明者想要說服驗證者，因為 $ h=g^x $ 並且指數是非負的（ $ x\geq0 $ ) 對於一個隨機的、公開的 $ g\in_R\mathbb{G} $ .
更正式地說，這是我想要一個高效（非互動式）零知識證明系統的語言：$$ \mathcal{R}={((h,g,\mathbb{G}),x)\vert g^x=h \land 0\leq x}. $$
也許，為這種語言設計一個西格瑪協議很容易？或者一些類似剪切和選擇的證明系統？理想情況下，驗證者的效率將獨立於 $ x $ . 你知道滿足這些要求的文獻中的任何證明系統嗎？
注意：在這種情況下，談論元素的離散對數的符號是有意義的，因為您不知道組的順序 $ \mathbb{G} $ 而且你也不知道任何元素的順序 $ g,h\in\mathbb{G} $ . 換句話說，這是一個不平凡的陳述，從某種意義上說 $ \mathcal{R}\notin BPP $ （有界誤差機率多項式時間），因為如果證明者能夠提供同一組元素的兩個不同“符號”，即 $ h=g^x=g^{-y} $ ， 然後 $ g^{x+y}=\mathbb{1}\leftrightarrow \vert\mathbb{G}\vert=k(x+y) $ ， 對於一些 $ k\in\mathbb{Z} $ ，這在一組未知順序中大概很難做到。通常，人們還假設即使是未知群階的整數倍也很難計算。
注 2：對數範圍證明不適用於此處，因為原則上， $ x $ 可以是任意大的整數。
你可以通過證明一個整數可以寫成四個平方和來證明它是非負的。
因此，對於您的協議，您將使用 Fujisaki Okamoto 整數承諾對這四個方塊進行承諾，使用諸如承諾數字位於區間內的有效證明之類的東西；第 2.3 節證明這些實際上是正方形，然後向這個類似 Schnorr 的證明添加一個語句，將所有這些正方形加起來 $ x $ 這樣 $ h = g^x $ .
好的，這是一次嘗試；你問了一個 NIZKP，我會把它寫成互動式的（並且很容易將它轉換成非互動式的）。
這是一個剪切和選擇協議：
- 第一步：證明者選擇正值 $ a $ 和 $ c $ （和 $ c < ax $ ), 並發布值 $ j = g^{ax - c} $ .
- 第 2 步：驗證者要求離散日誌或值 $ a, c $
- 步驟 3a：如果驗證者要求離散日誌，則證明者發布值 $ ax-c $ . 驗證者驗證它是肯定的並且 $ j = g^{ax-c} $
- 第 3b 步：如果驗證者要求提供值 $ a, c $ ，證明者發布它們，驗證者驗證 $ a, c $ 是積極的，而且 $ h^a = j \cdot g^c $
如果值 $ x $ 證明者知道是否定的，那麼證明失敗的機率為 0.5。如果證明者選擇正 $ a, c $ 價值觀，那麼 $ ax-c $ 將為負，因此如果驗證者要求該值，它將失敗。如果證明者使用任何其他策略，那麼如果驗證者要求 $ a, c $ 值。