在 Wesolowski 和 Pietrzak 可驗證延遲函式 (VDF) 中進行平方而不是任意取冪的原因
我正在研究基於 Wesolowski 和 Pietrzak RSA 組的 VDF（可驗證延遲函式）。這些基本上是通過要求證明者在一個未知階的半素群 G 中進行一堆重複平方，然後計算一個驗證者可以檢查的證明，而不必做重複平方模 G 的耗時工作。這些可以是用於工作證明、可信賴的隨機信標、垃圾郵件預防等。
我很好奇為什麼兩者都依賴計算 (g^(2^t) mod G) 作為要完成的工作，而不是僅僅計算 g 到某個任意大指數 mod G 的冪。（大指數可能是通過例如執行由已知輸入播種的 CSPRNG 生成。）在這種情況下，您可以計算 g^bignum mod G 的冪證明並將其提供給驗證者。
使用重複平方而不是任意指數是否具有任何密碼意義？是不是更簡單了？只是好奇，所以我可以理解為什麼做出這些選擇。
也對生成器（g）感到好奇。有什麼理由需要它是一個特定的數字，還是應該只是 3 之類的東西？也許我沒有抓住它，但我沒有看到討論過。
假設我有一個巨大的指數 $ B $ . 計算 $ g^B\mod G $ （我將省略“mod $ G $ “從現在開始），我會使用平方乘法：我會計算 $ g $ , $ g^2 $ , $ g^4 $ ,\點, $ g^{2^t} $ ， 在哪裡 $ t $ 是位長 $ B $ ，然後乘以所有 $ g^{2^i} $ 為了 $ i=1 $ 在二進製表示中 $ B $ . 請注意，這最多涉及 $ t $ 平方和 $ t $ 乘法（我假設平方和乘法花費相同的時間，這並不完全準確，但對於這個解釋來說已經足夠了），所以延遲最多是時間 $ 2t $ 乘以單個平方/乘法的時間。
但是，確切的時間不太清楚。這將取決於 G 的漢明權重，我們如何儲存中間值，或者我們是否保留所有的執行乘積 $ g^{2^i} $ 到目前為止，我們已經達到了等等。請注意，我們必須計算 $ g^{2^t} $ 無論如何要找到 $ g^B $ .
大數的求冪證明與重複平方的證明不應該有太大差異。我也不確定 Pietrzak 驗證方法是否適用於任意指數（可能？但它需要一些修改）。
所以基本上，任意大指數應該可以工作，但它會比重複平方更複雜。
生成器不能是任意數字，因為每次使用都需要更改。如果在兩個不同的應用程序中使用相同的生成器，有人可以保存所有的值 $ g^{2^t} $ 並且只是第二次在記憶體中查找它們，因此它們不會有所需的延遲。定義 2 中的時間鎖定遊戲說 $ g $ 是均勻隨機的；結構沒有提到這一點，但我認為這是所有 VDF 的基本假設。