Gruppo ciclico

$G$ è ciclico se $\exist$ $a \in G$$:<a> = G$

Problema DL

Sia $\mathcal G$ un algoritmo PPT per la generazione di gruppi ciclici $(G,q,g)$ dove $G$ è la descrizione dell’insieme degli elementi del gruppo, $g$ è un generatore del gruppo e $q$ è il suo ordine

// Supponiamo che nel gruppo l’operazione definita sia calcolabile efficientemente e che sia verificabile efficientemente l’appartenenza di un elemento al gruppo $G$

Abbiamo quindi $G= \{g^0,..,g^{q-1}\}$ e $\forall h \in G \exist !$ $x \in \Z_q: g^x=h$

Il valore $x$ è il logaritmo discreto di $h$ rispetto a $g$, in breve $x = log_g h$

<aside> 💡

$Dlog_{A , \mathcal G}(n)$

1. $C$ esegue $\mathcal G \to (G,q,g)$
2. $C$ sceglie $h \in G$ uniforme
3. $A$ riceve da $C$ i valori $(G,q,g)$ e $h$ e dà a $C$ il valore $x \in \Z_q$
4. Se $g^x = h$ allora $C$ dà in output $1$, altrimenti $0$ </aside>

DL difficile

Relativamente a $\mathcal G(1^n)$, il problema del DL è difficile se $\forall A$ PPT $\exist$ $negl(n):$ $Pr[Dlog_{A, \mathcal G}(n) = 1] \leq negl(n)$

Assunzione DL

Esiste un algoritmo $\mathcal G(1^n)$ relativamente al quale il problema del DL è difficile

Diffie-Hellman computazionale

<aside> 💡

$CDH_{A, \mathcal G}(n)$

1. $C$ esegue $\mathcal G(1^n) \to (G,q,g)$
2. $C$ sceglie uniformemente $x_1,x_2 \in \Z_q$ e calcola $h_1 = g^{x_1} \in G$, $h_2 = g^{x_2} \in G$
3. $A$ riceve da $C$ i valori $(G,q,g)$ e $h_1,h_2$ e dà a $C$ il valore $h_3 \in G$
4. Se $h_3 = g^{x_1x_2}$ allora $C$ dà in output $1$, altrimenti $0$ </aside>

CDH difficile

Relativamente a $\mathcal G(1^n)$, il problema CDH è difficile se $\forall A$ PPT $\exist$ $negl(n):$ $Pr[CDH_{A, \mathcal G}(n) = 1] \leq negl(n)$

Assunzione CDH

Esiste un algoritmo $\mathcal G(1^n)$ relativamente al quale il problema CDH è difficile