Încerc să înțeleg diferența dintre modelul de grup generic (clasic), așa cum este descris de Shoup [Shoup] și modelul de grup generic oarecum restrâns, așa cum este descris de Schnorr și Jakobsson în [SJ00].
Pentru claritate, voi da definiția celor două modele. Pentru asta, folosesc explicațiile din lucrare [BL19]. În ambele setări, avem un grup ciclic multiplicativ $G = \langle g \rangle$ de ordine $p$. (GGM = model de grup generic)
- Modelul de grup generic al lui Shoup
De cand $G$ este izomorfă la $\mathbb{Z}_p$, putem selecta o hartă injectivă aleatorie $\tau: \mathbb{Z}_p \rightarrow \mathbb{G}$, Unde $\mathbb{G}$ este setul de șiruri de biți de lungime $l \ (2^l \geq p)$ și codificăm jurnalul discret al elementului de grup în loc de elementul de grup însuși. Ideea cheie este că harta $\tau$ nu trebuie să fie un homomorfism de grup. GGM presupune că un adversar nu are acces la reprezentarea concretă a elementelor grupului. În schimb, adversarului i se oferă acces la un oracol parametrizat de $\tau$, care calculează indirect operațiunile grupului în $G$. Mai precis, pentru o intrare $(a,b) \in \mathbb{G} \times \mathbb{G}$ oracolele acţionează în felul următor $ Mult(a,b) = \tau(\tau^{-1}(a) + \tau^{-1}(b)), \ Inv(a) = \tau(-\tau^{-1 }(a))$. Remarcăm că adversarul nu are acces la hartă $\tau$ în sine.
- Schnorr și Jakobssen GGM pe baza coliziunilor
Datele algoritmului generic sunt împărțite în elemente de grup din $G$ și date non-grup. Un pas generic este $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}$. Definiție formală:
Un algoritm generic este o secvență de $t$ pași generici; pentru timp $1 \leq t' < t$, algoritmul ia intrări ca $f_1,...,f_{t'}$, Unde $(a_1,...,a_{i-1}) \in \mathbb{Z}^{i-1}_p$ depinde în mod arbitrar de i, elementul non-grup și mulțime $CO_{i-1} := \lbrace (j,k) | f_j = f_k, 1 \leq j <k \leq i-1 \rbrace $ a „coliziunilor” anterioare ale grupului.
Principala diferență pare să fie că atacatorului din modelul lui Shoup i se dă un mâner direct $\tau(g)$ pentru orice element de grup care este rezultatul oricărei interogări generice de grup. În timp ce atacatorul din cel de-al doilea model poate face referire numai indirectă la elementele grupului calculate anterior prin trimiterea unei interogări $(a_i, ..., a_{i-1}) \in \mathbb{Z}_p^{i-1}$ la oracolul de grup generic. Dar aceste două definiții mi se par atât de diferite încât aș aprecia cu adevărat dacă m-ar ajuta cineva să subliniez diferențele și asemănările. În special, aș dori să înțeleg avantajele dovezilor de securitate din modelul lui Shoup în comparație cu dovezile de securitate din modelul lui Schnorr.
Multe mulțumiri in avans!
