Rsa
知識證明協議lll-th 根
假設我們有 G 組，其中自適應根假設成立。這個假設表明，如果我們選擇一個元素 $ w $ 之後，如果我們收到一個質數 $ l $ 很難找到 $ u $ 這樣： $ u^l = w $
現在假設我想證明我知道一個 $ l\text{-}th $ 元素的根 $ w $ 沒有透露。（不想透露 $ u $ ）。有什麼協議嗎？
顯而易見的解決方案是這個簡單的選擇協議：
- 證明者：選擇一個隨機值 $ v $ 並發送值 $ y = v^\ell $
- 驗證者：選擇並發送一個隨機位 $ b $
- 證明者：如果 $ b=0 $ , 發送值 $ t_0=v $ . 如果 $ b=1 $ , 發送值 $ t_1=vu $
- 驗證者：如果 $ b=0 $ ，然後驗證 $ t_0^\ell = y $ . 如果 $ b=1 $ ，然後驗證 $ t_1^\ell = y w $
標準的零知識邏輯有效——如果證明者知道 $ y $ 他知道兩個正確響應的值 $ t_0 $ 和 $ t_1 $ ，然後（假設逆也很容易計算）他可以恢復該值 $ u $ （因此，如果他多次成功使用此協議，那麼在他不知道的情況下成功的機率 $ u $ 是最小的）。而且，只有一個答案沒有向驗證者提供任何資訊。
Guillou 和 Quisquater 的“深幣”協議： https ://link.springer.com/content/pdf/10.1007/3-540-45961-8_11.pdf