Menu
I giochi del lunedì di Prisma del 18 ottobre 2021 a cura di Fabio Ciuffoli
Il Premio Abel, considerato il Premio Nobel della matematica, è stato assegnato nel marzo 2021 all’informatico israeliano Avi Wigderson e al matematico ungherese Laszlo Lovasz, per il loro contributo alla teoria delle scienze computazionali e della matematica discreta, inclusa la Prova a Conoscenza Zero. Con questa Prova è possibile dimostrare che un’affermazione è vera senza rivelare alcuna informazione di supporto. Inizialmente sembrava un’idea bizzarra e controintuitiva, ma ha rappresentato un’importante rivoluzione concettuale e ha trovato fantastiche applicazioni nei sistemi di autentificazione, crittografici e nelle criptovalute.
Il gioco che proponiamo oggi si ispira alla Prova a Conoscenza Zero e si presta a più soluzioni è quindi un problema “a risposta aperta” e perciò invitiamo lettori a presentarci liberamente osservazioni e suggerimenti nello spazio riservato ai commenti. Alle ore 17.00 di domani pubblicheremo le nostre proposte di soluzione.
Premio Abel e la Prova a Conoscenza Zero
LA PEN DRIVE RUBATA. In un ufficio dove lavorano 100 persone è stata rubata una Pen Drive. I due capiufficio, Andrea e Dario, hanno ciascuno un’idea abbastanza chiara di chi sia il ladro, ma nel timore che stiano pensando a persone diverse, nessuno dei due è disposto a dichiarare il sospettato. E’ possibile verificare se entrambi sospettano della stessa persona, senza rivelare alcuna informazione nel caso in cui i sospettati non coincidessero?
In sintesi si chiede se Andrea e Dario possono concordare un modo per determinare se possiedono le stesse informazioni, senza rivelarle reciprocamente nel caso in cui non lo posseggano.
Forniamo alcuni spunti per la riflessione. Andrea non può condividere con Dario informazioni che possano identificare il suo sospettato, ad esempio non può dire: “Il mio sospettato arriva tardi il lunedì”, poiché rivelerebbe sospetti su quella persona. Un’altra procedura non accettabile sarebbe quella di rivolgersi a un amico comune. Andrea e Dario potrebbero scrivere, ciascuno su un proprio foglio, il nome o il numero in codice della persona sospettata e consegnarli all’amico. Se questo amico comune dice che i nomi o i numeri sono gli stessi, allora i sospettati coinciderebbero. Se fossero diversi, né Andrea né Dario saprebbero i rispettivi sospettati. Anche questa opzione non è soddisfacente. In primo luogo, non è detto che esista un amico comune, ovvero un verificatore indipendente e veritiero. Inoltre, ancora più importante, entrambi rivelerebbero informazioni a questo amico comune. Il punto centrale di questo esercizio è non rivelare alcuna informazione. Anticipiamo che ci sono diverse soluzioni, ognuna con punti di forza e di debolezza.
Il gioco di oggi è una rielaborazione tratta dal documento Comparing Information Without Leaking It di Ronald Fagin, Moni Naor e Peter Winkler.
In questa pagina vengono pubblicati giochi matematici, logici e di ragionamento ogni 15 giorni il lunedì in mattinata.
Siamo sempre alla ricerca di nuovi giochi e nuove proposte. Se vuoi suggerirne uno, scrivici un’e-mail a:
blog.giochi@prismamagazine.it
Fabio Ciuffoli è autore di diversi libri sul problem solving e i giochi logici e matematici, il più recente è Giochi matematici e logici.
PRISMA: pubblicazione mensile registrata presso il Tribunale di Milano (N. 235 del 19.09.2018).
Tutti i diritti di proprietà artistica e letteraria sono riservati.
L’editore è a disposizione di eventuali detentori di diritti che non sia stato possibile rintracciare.
Mateinitaly srl – p.iva 09164520968 – Corso Vercelli 27 – 20144 Milano (MI).
9 risposte
Mi sembra in ogni caso vulnerabile mediante un attacco a dizionario. Cioè io ho il nome di tutti e 100 i dipendenti, genero 100 hash e poi vedo quale hash corrisponde nella lista che mi manda Andrea. Un PC lo fa in un attimo.
Sono state pubblicate le soluzioni al link https://www.prismamagazine.it/giochi/x-soluzioni-del-xx-2021-prova-a-conoscenza-zero/
Si potrebbe costruire una sorta di ‘macchina’ che confronta una scansione delle due stringhe, come uno specchio. Se c’è matching produce un output, altrimenti nulla, e cancella l’informazione man mano che procede nella scansione, pixel per pixel. Finita la scansione, l’informazione di input non c’è più.
Ok, resta il fatto che il gestore della “macchina”, che confronta le scansioni, potrebbe “vendere” l’informazione all’altra parte. A domani per le soluzioni.
Riporto la suggestiva immagine, utilizzata dai ricercatori, nella pubblicazione nel 1996.
Un metodo potrebbe essere quello di usare un algoritmo della serie SHA (Secure Hash Algorithm), ossia un algoritmo che trasforma una qualunque stringa di testo in un altra stringa (hash). Un algoritmo SHA deve soddisfare due caratteristiche:
1. La stessa stringa deve generare sempre lo stesso hash
2. Dall’hash non si può risalire alla stringa che lo ha generato
Esistono diversi algoritmi SHA, con diversi gradi di sicurezza, per cui l’osservanza del punto 2 non è un valore assoluto ma una probabilità.
Riepilogando: i due si accordano su quale algoritmo usare (o ne elaborano uno essi stessi…), applicano ognuno l’algoritmo al nome del proprio sospettato, e quindi confrontano i due hash ottenuti. Se sono uguali, vuol dire che avevano in mente lo stesso sospettato; in caso contrario, nessuno dei due potrà risalire al nome che aveva in mente l’altro.
A questo punto si presenta però un altro problema: è vero che dall’hash non si può risalire al nome che lo ha generato, ma dato l’esiguo numero di sospettati, ciascuno dei due potrebbe dopo pochi tentativi trovare comunque il sospettato dell’altro.
Per risolvere questo problema ognuno dei due potrebbe presentare all’altro una lista di hash in cui soltanto uno è l’hash corrispondente al nome del proprio sospettato, e gli altri sono “segnaposto” generati a caso. Se confrontando le liste si trova un valore in comune, allora quello sarà relativo allo stesso sospettato. Quanto più lunga sarà la lista di hash casuali, tanto più sarà arduo per ognuno dei due cercare di risalire per tentativi al sospettato dell’altro. (Arduo = lungo ma non impossibile).
Ottimo anche le soluzioni proposte dai ricercatori propongono punti di forza e punti di debolezza di ciascuna ipotesi. A domani per le soluzioni.
Non é il mio genere di problemi. E’ difficile e indeterminato. Non so dove comunciare. Cosa é l’immagine in alto con due ombre, mi sembra?
Si tratta di una scultura astratta centrale che, illuminata da due punti luce differenti, proietta sulle pareti due ombre che raffigurano due famose sculture: il Pensatore di Rodin e la Venere di Milo. La tecnica è simile alla scultura seguente dove una serie di rifiuti, opportunamente disposti e illuminati da un determinato punto luce, produce l’ombra di una coppia seduta una di spalle all’altra.