Fujisaki-Okamoto 承諾方案參數的數字生成
我需要為一個項目實施 Fujisaki-Okamoto 承諾方案，以便我可以證明各種零知識證明彼此之間的性能，例如 Boudot 的“承諾數屬於區間的證明”（如果您對這意味著什麼感興趣，儘管它不直接相關）等等。在藤崎-岡本承諾計劃中，一條消息 $ x $ 承諾為 $ C=g^{x}h^{r}\mod{n} $ . ( $ r $ 是一個隨機值 $ ℤ^{*}_{n} $ ).
這需要我生成數字 $ n $ , $ g $ ， 和 $ h $ 在哪裡 $ n $ 是一個很大的合數，其因式分解對於 Alice 和 Bob 是未知的。我已將其實現為 $ n=pq $ ， 在哪裡 $ p $ 和 $ q $ 都是大素數，因此離散對數問題是不可行的，所以我知道它在幕後分解。然而 $ p $ 和 $ q $ 每次創建實例時都會動態生成，因此儘管我保存了它們的值，但它們不是靜態的（它們是複合的機會不超過 $ 2^{-100} $ ）。至於 $ g $ 和 $ h $ , " $ g $ 是大階的元素 $ ℤ^{*}_{n} $ ， 和 $ h $ 是由生成的群的大階元素 $ g $ “（使得離散對數
$$ $h$ in base $g$ $$和$$ $g$ in base $h$ $$愛麗絲不知道）。 不幸的是，這對我來說Google很難，因為我真的不知道如何從這裡開始。實際上，我根本找不到關於 Fujisaki-Okamoto 方案的太多資訊，但我的問題不在於使用它，而在於如何生成這些數字以使其首先發揮作用。
基本上我的問題歸結為兩件事：
- 背後的理論要求是什麼 $ h $ 和 $ g $ 在這個計劃中？
- 可以使用哪些算法生成 $ g $ 和 $ h $ ?
如果您可以選擇不同的秘密素數 $ p $ 和 $ q $ 這樣 $ (p-1)/2 $ 和 $ (q-1)/2 $ 也是素數，那麼就變得容易了。對於隨機值 $ r $ , $ g = r^2 $ 將有準確的順序 $ (p-1)(q-1)/4 \approx n/4 $ 除非 $ r, r-1 $ 或者 $ r+1 $ 恰好不是相對質數 $ n $ （其中，如果您選擇 $ r $ 範圍內隨機 $ [2, n-2] $ , 發生機率小於 $ 3/p + 3/q $ ，可以忽略不計。而且，如果您選擇 $ h $ 同樣的方式（選擇不同的隨機值 $ s $ 並將其平方 $ h = s^2 $ )，則保證在生成的組中 $ g $ .
所以，歸結為：
- 到了選擇的時候 $ p $ 和 $ q $ ，選擇安全素數（這需要更多時間，但仍然可行）
- 選擇 $ g $ 和 $ h $ , 選擇獨立的隨機值 $ r, s \in [2, n-2] $ , 並設置 $ g = r^2 \bmod n $ 和 $ h = s^2 \bmod n $
您可以通過選擇一個隨機指數來替換最後一步 $ \lambda $ 和計算 $ h = g^\lambda $ ; 我假設你寧願不知道離散對數 $ h $ 你自己。