Renato Betti


IL SORTEGGIO DI ALICE E BOB

Rimane da esaminare la maniera con cui due contendenti possono eseguire una estrazione a sorte, senza avere la possibilità di incontrarsi per controllare che tutte le operazioni si svolgano correttamente. Questo problema non riguarda direttamente i procedimenti della Crittografia - trasmissione e validazione di messaggi riservati - ma si basa sullo stesso principio della chiave pubblica, vale a dire sulla possibilità di eseguire un'operazione la cui inversa non è accessibile al calcolo immediato, a meno di avere qualche informazione supplementare.
In questo caso, Alice e Bob di comune accordo sceglieranno una funzione a trabocchetto f. Quindi Alice, ad esempio, fissa un valore x dell'argomento, calcola f (x) e propone a Bob di scegliere a caso una proprietà di x che abbia il 50% di probabilità di essere vera: ad esempio, quando x è un numero intero, gli chiede di dire se è pari o dispari. È chiaro che per Bob risulta impossibile risalire da f (x) ad x: se indovina, la vittoria del sorteggio è sua, altrimenti è di Alice e lo stesso Bob può convincersene facilmente. La scelta è stata casuale ed equa, come si richiede ad un sorteggio.
A1 solito, anche per una procedura di questo tipo le funzioni più interessanti sono prese dalla Teoria dei numeri. Eccone una che sfrutta una proprietà non banale: come nella scelta della chiave pubblica, Alice fissa due numeri primi molto grandi p e q e calcola il loro prodotto n=p*q. Comunica a Bob il valore di n ma non la scomposizione in fattori che, al solito, è il suo segreto. Da parte sua, anche Bob esegue la scelta di un intero u compreso fra 1 ed n/2, calcola u2 (mod n) e comunica questo numero ad Alice. Alice può facilmente risalire alle due radici quadrate di u2 che sono comprese nell'intervallo (1,n/2) in quanto conosce la fattorizzazione di n e, se indovina il valore di u scelto da Bob, avrà la vittoria nel sorteggio: per questo ha esattamente il 50% di probabilità di vincere. Dunque Alice comunica la sua scelta a Bob, il quale non può che consentire nel caso Alice abbia indovinato, perché altrimenti gli viene chiesto di dire qual è l'altra radice quadrata di u2... ma lui non è in grado di calcolarla.