短 Schnorr Signature 的雜湊函式要求
內文等人。在他們的論文Hash Function Requirements for Schnorr Signatures以下定理（使用分叉引理）中陳述： $ \mathbb{G} $ 是通用組（第 2 節）， $ s \approx \log_2q $ , 雜湊函式 $ H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n $ .
定理 1 如果離散對數問題在 $ \mathbb{G} $ 是 $ (t_\text{dlog}, \epsilon_\text{dlog} $ -hard，那麼 Schnorr 簽名是 $ (t_\text{uf-cma}, q_S,q_H, \epsilon_\text{uf-cma}) $ - 安全的 $ \epsilon_\text{uf-cma} = \sqrt{(q_H+q_S+1)\epsilon_\text{dlog}} + \frac{q_H+q_S+1}{2^n} + \frac{q_S(q_H+q_S+1)}{q} $ 和 $ t_\text{uf-cma}= t_\text{tdlog}/2 − q_S t_\text{exp} + \mathcal{O}(q_H + q_S + 1) $ ， 在哪裡 $ t_\text{exp} $ 是組中求冪的成本 $ \mathbb{G} $ .
他們得出結論，這個界限清楚地表明一個散列函式 $ n = s/2 $ 輸出位應足以獲得安全級別 $ s/2 $ 位。形式的一個術語 $ q_H^2/2^n $ 會建議使用 s 位散列函式。
有人可以更詳細地向我解釋一下嗎？
這裡， $ k $ 安全位意味著優勢最多 $ O\left(\frac{T^\alpha}{2^{\alpha k}}\right) $ , 做完之後 $ T $ 對手進行的（所有類型的）操作。通過這種形式主義，我們可以得出結論，對手需要做 $ O(2^k) $ 破壞系統的“操作”（ $ T^\alpha \approx2^{\alpha k}\implies T \approx 2^k $ ).
然後，我們詳細查看了總和中的所有術語。
當我們看第三項時： $ \frac{q_S(q_H+q_S+1)}{q}\leq\frac{T}{q} $ ， 沒關係。
第二學期 $ \frac{q_H+q_S+1}{2^n}=O(T2^{-n}) $ : 如果我們想讓這個詞在 $ O(T2^{-s/2}) $ ，我們需要有 $ n\geq s/2 $ ， （記起 $ n $ 是雜湊函式的輸出大小）。
關於第一學期，它有點複雜： $ \sqrt{(q_H+q_S+1)\epsilon_\text{dlog}}\leq\sqrt{T2^{-s/2}} $ ，但也可以（與 $ \alpha=\frac{1}{2} $ ).