Problema utilizzato da molti algoritmi crittografici
$$ \alpha^x \equiv\beta \mod p $$
E’ difficile trovare la $x$ , perche $\alpha^x$ è molto piu grande di $p$
Ci sono 3 possibili applicazioni del logaritmo discreto :
Supponiamo che voglia dire un segreto ma non voglio dirlo fino a che non capiti un determinato evento.
ES:
A VS B : So che la partita è truccata , ma non voglio dare l’informazione.
$p ,\alpha$ sono condivisi , $x$ è un numero che ha tot cifre, all’interno di $x$ in posizione $i$-esima inserirò il vincitore della partita. Tale bit è 1 se vince Alice o 0 se vince Bob. Poco prima che inizi la partita so chi vince , predo un x a caso e ci inserisco il bit.
Calcolo :
$$ \alpha^x\equiv\beta\mod p $$
E spedisco anche $\beta$, ora sono pubbliche sia $\alpha,\beta,p$. Al termine della partita , vince alice.
Consegno anche la $x$, vado nella posizione e trovo il bit a 1 .
Non posso aver cambiato la $x$ perche quell’ $x$ è “inerente” a quel $\beta$.
Essendo un bit ‘era il 50% delle possibilità di pescarlo giusto. Ma la probabilità scende velocemente a seconda di quante puntate di fanno.
Questa tecnica è usata anche nelle blockchain. Vorrei che le mie transazioni rimanessero anonime.