{"id":514,"date":"2015-02-10T13:53:49","date_gmt":"2015-02-10T12:53:49","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=514"},"modified":"2022-10-11T13:49:44","modified_gmt":"2022-10-11T11:49:44","slug":"dimostrazioni-a-conoscenza-zero","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2015\/02\/10\/dimostrazioni-a-conoscenza-zero\/","title":{"rendered":"Dimostrazioni a conoscenza zero"},"content":{"rendered":"

Il biglietto da visita dice semplicemente “L’uomo che sa contare gli spilli”. Il proprietario del biglietto \u00e8 un omino che afferma che se gli presentate un qualunque contenitore pieno di spilli, fossero una scatoletta o un tir, lui \u00e8 in grado con una sola occhiata di dire quanti ce ne sono. Come possiamo fidarci che il tipo non ci stia prendendo in giro, senza metterci a contare tutti gli spilli?<\/p>\n

Un modo per avere non proprio la certezza ma una probabilit\u00e0 grande a piacere di accorgerci che il tipo sta cercando di prenderci in giro \u00e8 spiegato da Dennis Shasha nel suo libro Codes, Puzzles, and Conspiracy<\/i>. Mostriamogli un mucchio di spilli e chiediamogli quanti ce ne sono. Poi lo facciamo uscire dalla stanza, togliamo dal mucchio un numero di spilli abbastanza piccolo perch\u00e9 lo possiamo contare senza troppa fatica, facciamo rientrare il Contatore e gli chiediamo “Bene: quanti spilli ci sono ora<\/b>“? Se la differenza tra i due numeri da lui divinati coincide con il numero di spilli che abbiamo tolto, possiamo iniziare a fidarci del tipo; altrimenti siamo certi che sia un ciarlatano. Se siamo dei malfidenti, possiamo sempre rifare pi\u00f9 volte l’esperimento. Ma c’\u00e8 di meglio ancora! Immaginiamo che il Contatore di spilli non voglia rivelarci il numero esatto di spilli – chess\u00f2, sa che un nostro amico ha scommesso mille euro che noi non sappiamo dirgli quanti spilli ci sono nel mucchio, e vuole cento euro in anticipo per darci la risposta. Bene, noi possiamo allora chiedergli quanti spilli abbiamo tolto. Se sono relativamente pochi rispetto al numero totale, il Contatore di spilli non ha nessun problema a risponderci, ammesso naturalmente che sappia davvero quanti elementi ci sono nel mucchio: fornirci questa informazione anche per un numero ripetuto di tentativi non ci d\u00e0 infatti nessuna informazione sul numero totale. Insomma, possiamo essere del tutto fiduciosi che il Contatore di spilli sappia davvero contarli senza che lui renda pubblica la risposta.<\/p>\n

Dimostrazioni di questo tipo sono dette a conoscenza zero<\/b> (in inglese, “Zero-knowledge proofs”), e come sempre Wikipedia \u00e8 la nostra amica<\/a>. Il concetto \u00e8 relativamente recente, visto che \u00e8 apparso in letteratura solo nel 1985 con il lavoro di Shafi Goldwasser, Silvio Micali e Charles Rackoff. (Nota a latere: Micali \u00e8 diventato professore al MIT a 29 anni, e ha vinto il premio G\u00f6del e il premio Turing. Insomma, un cervello in fuga niente male). Wikipedia presenta anche una “spiegazione per bambini” di cosa \u00e8 una dimostrazione a conoscenza zero, ideata da Jean-Jacques Quisquater, Louis C. Guillou e Thomas A. Berson. Ci sono due personaggi: il possessore<\/b> della dimostrazione Patrizia e il verificatore<\/b> Valerio, e c’\u00e8 una caverna con due ingressi, A e B. All’interno della caverna c’\u00e8 una porta chiusa, che impedisce di entrare da una parte e uscire dall’altra a piacere. Patrizia afferma di avere la parola magica per aprire quella porta, ma non vuole rivelarla a Valerio prima che questi la paghi per l’informazione. Come pu\u00f2 Patrizia convincere (ragionevolmente: tenetelo a mente) Valerio che lei effettivamente possiede quella parola magica, senza dargli nessun’altra informazione? Semplice. Patrizia entra nella caverna senza che Valerio la veda, e a questo punto Valerio le chiede di uscire da un ingresso specifico. Se Patrizia effettivamente conosce la parola magica non avr\u00e0 problema a eseguire la richiesta; altrimenti c’\u00e8 una possibilit\u00e0 su due che non possa farlo perch\u00e9 era entrata dall’altra parte. Valerio pu\u00f2 ripetere l’operazione quante volte vuole, fino a che la probabilit\u00e0 che Patrizia sia solo molto fortunata diventa cos\u00ec bassa che Valerio si convincer\u00e0. Per esempio, dopo venti richeste la probabilit\u00e0 di riuscire sempre per pura fortuna \u00e8 meno di una su un milione.<\/p>\n

Traducendo l’esempio in modo formale, abbiamo un possessore e un verificatore; entrambi devono dimostrare all’altro di essere onesti, il verificatore seguendo un preciso modo di operazioni (un protocollo) e il possessore dando la risposta corretta alle domande del verificatore. Per avere una “dimostrazione” a conoscenza zero di un’affermazione, occorrer\u00e0 che siano verificate tre condizioni:<\/p>\n

    \n
  1. Completezza<\/b>: se l’affermazione \u00e8 vera, un possessore onesto potr\u00e0 convincere un verificatore onesto.<\/li>\n
  2. Correttezza<\/b>: se l’affermazione \u00e8 falsa, nessun possessore disonesto potr\u00e0 convincere (sufficientemente) il verificatore onesto che essa \u00e8 vera.<\/li>\n
  3. Conoscenza zero<\/b>: se l’affermazione \u00e8 vera, un verificatore potr\u00e0 sapere solo tale informazione, e nulla pi\u00f9. <\/li>\n<\/ol>\n

    Ci sono due punti fondamentali da notare. Il primo, legato alla correttezza, ci ricorda che queste non sono dimostrazioni in senso matematico: non abbiamo mai la certezza ma solo una probabilit\u00e0 che possiamo rendere piccola a piacere di sbagliarci. Il secondo \u00e8 un po’ pi\u00f9 complicato da spiegare, e richiede l’introduzione di un terzo personaggio, il perfido simulatore<\/b> Stanislao. Immaginiamo che Valerio, ormai convinto che Patrizia conosca effettivamente la parola magica per aprire la porta segreta, abbia filmato tutta la scena, con lui che per venti volte arriva, dice “destra” o “sinistra” e vede Patrizia uscire dalla parte giusta. Valerio porta il video al notaio Nicoletta per certificare la propria scoperta… e Nicoletta gli risponde “nulla da fare, questo video non ha alcun valore”. Come mai? Semplice. Stanislao le aveva appena consegnato un video taroccato nel quale una sosia di Patrizia sembrava fare esattamente le stesse cose, pur senza conoscere la parola magica. Come ha fatto? Beh, ci sono varie possibilit\u00e0. Per esempio, ha filmato una cinquantina di tentativi e ha rimontato il video mostrandone solo venti coronati da successo: oppure si \u00e8 messo d’accordo con la sosia spiegandole quale sarebbe stata la successione esatta di richieste che le avrebbe fatto. In pratica, dunque, il mero fatto di vedere le risposte esatte pu\u00f2 sempre essere simulato, il che significa che non d\u00e0 nessuna informazione aggiuntiva a quella “il possessore conosce effettivamente il segreto”.<\/p>\n

    Chi vuole divertirsi a vedere un giochino interattivo sulle dimostrazioni a conoscenza zero pu\u00f2 andare su questa pagina<\/a>, dove ci sono due grafi sulla 3-colorabilit\u00e0 di un grafo, vale a dire sulla possibilit\u00e0 di colorare i vertici un grafo con soli tre colori in modo che due vertici tra loro connessi non abbiano mai lo stesso colore. Il computer \u00e8 il possessore del segreto, e colora il grafo (se possibile…) in quel modo. Noi siamo i verificatori, e possiamo indicare due vertici connessi: il computer ci mostrer\u00e0 allora come sono colorati. Naturalmente dopo ogni nostra verifica il computer generer\u00e0 una nuova colorazione, perch\u00e9 altrimenti potremmo man mano testare tutti i vertici e ricavare la colorazione completa del grafo. Il modo turbo fa fare tutto (in fretta) al computer, cos\u00ec potete vedere in pratica le probabilit\u00e0 che il grafo sia stato effettivamente 3-colorato dal computer. <\/p>\n

    E a chi invece si sta chiedendo perch\u00e9 mai si fa tutta questa fatica per creare dimostrazioni che dimostrazioni non sono, che si pu\u00f2 dire? Semplice. Immaginate di dovervi connettere a un sistema non solo senza inviare la password in chiaro – quello lo fate facilmente cifrando il protocollo – ma anche senza che il sistema remoto sappia<\/i> qual \u00e8 la vostra password: si sa, fidarsi \u00e8 bene ma non fidarsi \u00e8 meglio. Un sistema a conoscenza zero \u00e8 allora l’ideale: una successione abbastanza lunga di challenge-response dar\u00e0 al computer una sicurezza abbastanza alta che noi conosciamo effettivamente la password. Certo, non la certezza: ma come fa il computer a sapere che la password non ci sia stata rubata da qualcuno che ci sta impersonando? Ricordatevi che la teoria \u00e8 sempre molto bella, ma bisogna anche tenere conto della pratica!<\/p>\n","protected":false},"excerpt":{"rendered":"

    \u00c8 possibile convincere qualcuno che noi conosciamo un segreto, senza effettivamente rivelarglielo? A prima vista sembra impossibile, ma esiste un modo per renderlo pi\u00f9 che ragionevolmente certo.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-514","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-8i","jetpack-related-posts":[{"id":2634,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/06\/quanto-e-irragionevolmente-efficace-la-matematica\/","url_meta":{"origin":514,"position":0},"title":"Quanto \u00e8 “irragionevolmente efficace” la matematica?","author":".mau.","date":"06\/09\/2013","format":false,"excerpt":"Ogni tanto la banda dei matematici non-platonisti si risveglia. Solo che il matematico tipico di filosofia ne sa ben poca","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":159,"url":"https:\/\/xmau.com\/ilpost\/2014\/03\/11\/come-calcolare-pi-greco-a-furia-di-rimbalzi\/","url_meta":{"origin":514,"position":1},"title":"Come calcolare pi greco a furia di rimbalzi","author":".mau.","date":"11\/03\/2014","format":false,"excerpt":"un calcolatore analogico per trovare le cifre di pi greco","rel":"","context":"In \"approssimazioni\"","block_context":{"text":"approssimazioni","link":"https:\/\/xmau.com\/ilpost\/tag\/approssimazioni\/"},"img":{"alt_text":"[due palle un soldo]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2014\/03\/pi-palle-300x200.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2584,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/03\/euclide-aritmetico\/","url_meta":{"origin":514,"position":2},"title":"Euclide aritmetico","author":".mau.","date":"03\/04\/2013","format":false,"excerpt":"Gli Elementi non parlano solo di geometria, ma anche di aritmetica; e anche qua brilla l'esposizione di Euclide.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/04\/Euclids_algorithm_Book_VII_Proposition_2_3.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2640,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/25\/matematica-e-liberta\/","url_meta":{"origin":514,"position":3},"title":"Matematica e libert\u00e0","author":".mau.","date":"25\/09\/2013","format":false,"excerpt":"Non ho certo le capacit\u00e0 di interloquire con il papa emerito sui temi teologici, ma forse su quelli pi\u00f9 prettamente matematici qualcosa posso dire.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2624,"url":"https:\/\/xmau.com\/ilpost\/2013\/07\/08\/basta-saperlo\/","url_meta":{"origin":514,"position":4},"title":"Basta saperlo…","author":".mau.","date":"08\/07\/2013","format":false,"excerpt":"Spesso in matematica sapere qual \u00e8 il risultato da dimostrare fa anche intuire qual \u00e8 la strada da prendere per dimostrarlo. Il guaio \u00e8 appunto riuscire a saperlo...","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1389,"url":"https:\/\/xmau.com\/ilpost\/2018\/12\/25\/quizzini-per-natale-2018\/","url_meta":{"origin":514,"position":5},"title":"Quizzini per Natale 2018","author":".mau.","date":"25\/12\/2018","format":false,"excerpt":"Che Natale sarebbe senza i quizzini del Post? Le risposte tra una settimana. Gli ultimi due sono pi\u00f9 difficili, magari poi poster\u00f2 un aiutino ;-) 1. Non essere ottusi Considerate tutti gli insiemi I di cento numeri interi positivi distinti con la seguente propriet\u00e0: dati tre qualunque elementi a, b\u2026","rel":"","context":"In \"quizzini\"","block_context":{"text":"quizzini","link":"https:\/\/xmau.com\/ilpost\/tag\/quizzini\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2018\/12\/q361a.png?resize=350%2C200","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/514","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=514"}],"version-history":[{"count":5,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/514\/revisions"}],"predecessor-version":[{"id":519,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/514\/revisions\/519"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=514"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}