如何將散列函式構造成循環組，使其離散對數難以處理？
來自可連結環簽名文件：
讓 $ G = \langle g\rangle $ 是一個素數循環群 $ q $ 這樣潛在的離散對數問題（DLP）就很難了。讓 $ H_1 : {0, 1}^∗ \to \mathbb Z_q $ 和 $ H_2 : {0, 1}^∗ \to G $ 是被視為隨機預言的不同雜湊函式。假設對於任何 $ \alpha\in{0, 1}^* $ , 的離散對數 $ H_2(\alpha) $ 到基地 $ g $ 是棘手的。
為此，正如我之前的問題所建議的那樣，我會選擇一個大的Sophie Germain Prime $ q $ 這樣 $ 2^{q} \bmod {(2q+1)} = 1 $ ， 和 $ 2 $ 作為組生成器。很想定義 $ H_2(a) = g^{H(a)} $ ， 在哪裡 $ H $ 是一個雜湊函式，不同於 $ H_1 $ . 但是，這不會按預期工作，因為在這種結構下， $ log_g(H_2(a)) = H(a) $ . 因此，我怎樣才能為 $ H_2 $ 關於那個問題？
創建這樣一個散列函式的明顯方法是首先定義一個散列函式 $ H $ （區別於 $ H_1 $ ) 生成範圍內的整數作為輸出 $ [2, q] $ ，然後定義 $ H_2(x) = H(x)^2 \bmod (2q+1) $ （即正方形 $ H(x) $ 模組 $ 2q+1 $ ).
如果我們對待 $ H $ 作為隨機預言機，那麼 $ H_2(x) $ 是子群的一個隨機元素（均勻分佈，除了 1） $ \mathbb Z^*_{2q+1} $ 由二次殘差組成。我們可以看到這是一個隨機元素，因為每個可能的值 $ H(x) $ 產生一個明顯的二次餘數，並且有 $ q-1 $ 子組元素（除 1 之外），因此每個輸出都以相等的機率生成。
這個子組是訂單 $ q $ 子組有你正在考慮的，如果 DLP 很難，那麼很難解決隨機元素上的 DLP。