泛型組模型之間的區別
我試圖了解 Shoup 描述的（經典）通用組模型之間的區別$$ Shoup $$以及 Schnorr 和 Jakobsson 在$$ SJ00 $$. 為了清楚起見，我將給出這兩個模型的定義。為此，我正在使用論文的解釋$$ BL19 $$. 在這兩種設置中，我們都有一個乘法循環群 $ G = \langle g \rangle $ 有秩序的 $ p $ . （GGM = 通用組模型）
- Shoup 的通用組模型
自從 $ G $ 同構於 $ \mathbb{Z}_p $ ，我們可以選擇一個隨機的單射圖 $ \tau: \mathbb{Z}_p \rightarrow \mathbb{G} $ ， 在哪裡 $ \mathbb{G} $ 是長度的位串的集合 $ l \ (2^l \geq p) $ 我們編碼組元素的離散對數而不是組元素本身。關鍵思想是地圖 $ \tau $ 不需要是群同態。GGM 假設對手無法訪問組元素的具體表示。相反，攻擊者可以訪問由以下參數設置的預言機 $ \tau $ ，它間接計算組操作 $ G $ . 更準確地說，對於輸入 $ (a,b) \in \mathbb{G} \times \mathbb{G} $ 神諭的行為如下 $ Mult(a,b) = \tau(\tau^{-1}(a) + \tau^{-1}(b)), \ Inv(a) = \tau(-\tau^{-1}(a)) $ . 我們注意到對手無法訪問地圖 $ \tau $ 本身。
- 基於碰撞的 Schnorr 和 Jakobssen GGM
通用算法的數據被劃分為組元素 $ G $ 和非組數據。一個通用的步驟是 $ mexp: \mathbb{Z}^d_q \times G^d \mapsto G, (\underline{a}, (f_1,…,f_d)) \mapsto \prod_{i=1}^d f_i^{a_i} $ . 正式定義： 通用算法是一系列 $ t $ 通用步驟；時間 $ 1 \leq t’ < t $ , 該算法將輸入作為 $ f_1,…,f_{t’} $ ， 在哪裡 $ (a_1,…,a_{i-1}) \in \mathbb{Z}^{i-1}p $ 任意取決於 i、非群元素和集合 $ CO{i-1} := \lbrace (j,k) | f_j = f_k, 1 \leq j <k \leq i-1 \rbrace $ 該組之前的“碰撞”。
主要區別似乎是 Shoup 模型中的攻擊者被賦予了直接句柄 $ \tau(g) $ 對於作為任何通用組查詢輸出的任何組元素。而第二種模型中的攻擊者只能通過送出查詢間接引用先前計算的組元素 $ (a_i, …, a_{i-1}) \in \mathbb{Z}_p^{i-1} $ 到通用組oracle。但是這兩個定義對我來說似乎如此不同，如果有人能幫助我指出差異和相似之處，我將非常感激。特別是，我想了解 Shoup 模型中的安全性證明與 Schnorr 模型中的安全性證明相比的優勢。
提前謝謝了！
兩種模型具有相同的“計算能力”：您可以建構 $ Mult $ ， 和 $ Inv $ 常式與 $ mexp $ ，你可以建立 $ mexp $ 和 $ Mult $ （通過使用平方和乘法算法）。
我們可以認為，在第二個模型中，攻擊者可以訪問元素的真實值，但它可以使用它來獲得更好的效率，因為係數 $ f_i $ 不能依賴於這些值（除非在第一個模型中檢測到相等）。
對我來說，唯一的區別是第二個模型的不均勻性（第二個模型對我來說就像一個電路，與第一個模型相反，它更像是一個帶有預言機的圖靈機），以及時間複雜性：
您無法輕鬆比較兩個模型中兩種算法的時間複雜度，因為在第二個模型中考慮某些運算（例如求冪）比在第一個模型中要快得多。因此，第一個模型的下限可能會更大/更好（據我所知，橢圓曲線操作在實踐中仍然相關）。