{"id":36001,"date":"2026-02-18T04:51:28","date_gmt":"2026-02-18T03:51:28","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=36001"},"modified":"2026-02-16T17:41:46","modified_gmt":"2026-02-16T16:41:46","slug":"ancora-sulle-dimostrazioni-a-conoscenza-zero","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2026\/02\/18\/ancora-sulle-dimostrazioni-a-conoscenza-zero\/","title":{"rendered":"Ancora sulle dimostrazioni a conoscenza zero"},"content":{"rendered":"

Ultima puntata, almeno per il futuro prevedibile, sulle dimostrazioni a conoscenza zero. Stavolta il punto di vista \u00e8 per\u00f2 un po’ diverso: spiegher\u00f2 cosa c’\u00e8 filosoficamente dietro a questo tipo di dimostrazioni, basandomi essenzialmente su questo vecchio post<\/a> di Matthew Green. <\/p>\n

Per prima cosa, il concetto nacque una quarantina d’anni fa, come spinoff degli studi sui sistemi di dimostrazione interattiva, dove un Dimostratore deve convincere un Verificatore che una certa affermazione matematica \u00e8 vera. Il Verificatore ha a disposizione molte meno risorse computazionali del Dimostratore, altrimenti il problema non si porrebbe nemmeno. Fino alla met\u00e0 degli anni ’80 del secolo scorso gli studi erano orientato sul vedere se il Verificatore poteva avere fiducia del Dimostratore, oppure quest’ultimo poteva fregarlo: Shafi Goldwasser, Silvio Micali e Charles Rackoff hanno pensato invece di rovesciare il punto di vista, chiedendosi “e se fosse il Verificatore quello di cui non ci fidiamo?” L’esempio che fa Green \u00e8 quello delle password Unix. Il server salva una versione codificata (hash) della password pi\u00f9 alcuni caratteri casuali (il salt); quando l’utente si collega manda la password, il sistema ricalcola l’hash e se coincide con quello salvato fa entrare l’utente, perch\u00e9 sa che l’utente conosce la password. Questo per\u00f2 significa che se il server \u00e8 compromesso allora il cracker vede la password in chiaro: non esattamente una bella idea. Si pu\u00f2 fare di meglio? La risposta \u00e8 stata “(statisticamente) s\u00ec: posso avere una probabilit\u00e0 alta a piacere che il Verificatore riesca solo a sapere il bit di informazione “l’affermazione \u00e8 vera”. <\/p>\n

L’esempio fatto \u00e8 diverso da quello delle due porte fatto la scorsa settimana, e rende forse pi\u00f9 l’idea di come vanno le cose: poi il raccontino, pensato originariamente da Micali, \u00e8 anche divertente. Io ho un grafo molto grande, e vorrei che i vertici fossero colorati con solo tre colori in modo che due vertici adiacenti non abbiano mai lo stesso colore. Questo mi pu\u00f2 per esempio servire per una rete di trasmissione radio: due celle troppo vicine non possono usare le stesse frequenze, perch\u00e9 altrimenti i segnali interferirebbero. Il problema \u00e8 computazionalmente pesante, NP completo: Google ha dirottato un bel po’ delle sue TPU dai chatbot per risolverlo, e adesso mi dice che ha la soluzione e mi chiede i soldi. Siamo per\u00f2 in un vicolo cieco: io non pago se non sono sicuro che la soluzione ci sia davvero, e Google non me la vuole mostrare finch\u00e9 non pago. Che fare? Basta avere un capannone abbastanza grande; pennarelli di tre colori; tanta, tanta carta. E un bel po’ di cappelli, come omaggio ai problemi di logica. Io disegno il mio grafo (diciamo con 1000 archi che uniscono i vertici) su un enorme foglio di carta ed esco; gli amici di Google scelgono a caso un associazione tra i colori dei pennarelli e la colorazione del grafo, e poi mettono un cappello sopra ogni vertice. Quando sono rientrato, scelgo un arco qualunque che connette due vertici. Google toglie i cappelli che coprono i due vertici: se i colori sono identici sono certo che mi aveva preso in giro e non aveva la soluzione, se invece sono diversi potrebbe<\/i> avere ragione. Certo, avrebbe ancora una probabilit\u00e0 dell’ordine del 99,9% di avere solo avuto fortuna, visto che non posso sapere cosa c’\u00e8 dietro tutti gli altri archi. Per\u00f2 Google mi dice che posso rifare l’esperimento quante volte voglio. Ogni volta si partir\u00e0 da un’associazione casuale dei colori, quindi non posso sperare di costruirmi man mano una mappa; in compenso posso sempre scegliere l’arco che voglio. A furia di moltiplicare fattori 0,999 (il 99,9%), la probabilit\u00e0 che sia solo questione di fortuna pu\u00f2 essere resa piccola a piacere. C’\u00e8 persino un gioco interattivo<\/a>, se volete divertirvi.<\/p>\n

La definizione di un protocollo a conoscenza zero, secondo gli autori, deve soddisfare tre propriet\u00e0:<\/p>\n

    \n
  1. Completezza<\/b>: se il Dimostratore ha effettivamente una dimostrazione, deve convincere il Verificatore con una probabilit\u00e0 prossima a piacere al 100%.<\/li>\n
  2. Validit\u00e0<\/b>: il Dimostratore pu\u00f2 convincere il Verificatore solo se effettivamente ha una dimostrazione.<\/li>\n
  3. Conoscenza zero<\/b> Il Verificatore non avr\u00e0 nessuna idea di quale possa essere la soluzione.<\/li>\n<\/ol>\n

    L’esperimento visto soddisfa sicuramente i primi due punti. Per il terzo, l’equivalente del video editato nell’esempio della settimana scorsa, le cose si fanno pi\u00f9 fantascientifiche. Supponiamo che Google non sia in realt\u00e0 riuscita a trovare una colorazione. In compenso uno dei loro progetti segreti \u00e8 il prototipo di una macchina del tempo. Essa funziona perfettamente: l’unico problema \u00e8 che al momento permette di tornare indietro solo di 314,15926… secondi. Avere poco pi\u00f9 di cinque minuti \u00e8 per\u00f2 sufficiente: se si acccorgono che sto scegliendo un arco i cui vertici hanno lo stesso colore, mandano un segnale e un tecnico torna indietro nel tempo, cambiando la colorazione ma lasciandola sempre casuale: il tutto fino a che non si ha uno schema dove i vertici hanno colori diversi. Il tutto senza che io mi possa accorgere di niente, ovviamente. Cosa significa tutto questo? Che se per assurdo io avessi una strategia che “estrae” informazione dopo avere osservato i due colori, estrarrei la stessa informazione anche nel caso che la macchina del tempo fosse stata messa in funzione. Ma in questo secondo caso la soluzione al mio problema non esiste: quindi l’assunto di partenza \u00e8 falso e io non posso estrarre informazione. <\/p>\n

    Nell’ambito informatico, tutto questo si ottiene mediante uno “schema d’impegno” (commitment scheme<\/a>). Il ruolo della macchina del tempo \u00e8 banalmente il rilanciare il programma corrispondente al Dimostratore pi\u00f9 volte. La morale di tutto ci\u00f2 \u00e8 che viviamo in un mondo difficile, dove non ci si pu\u00f2 mai fidare di nessuno, ma per fortuna la matematica ci aiuta a ritrovare questa fiducia!<\/p>\n","protected":false},"excerpt":{"rendered":"

    Stavolta mostro una visione pi\u00f9 filosofica del protocollo<\/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_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"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-36001","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-9mF","jetpack-related-posts":[{"id":37224,"url":"https:\/\/xmau.com\/notiziole\/2026\/05\/27\/dimostrazioni-a-conoscenza-zero-e-crittografia\/","url_meta":{"origin":36001,"position":0},"title":"Dimostrazioni a conoscenza zero e crittografia","author":".mau.","date":"2026-05-27","format":false,"excerpt":"In teoria non possono esistere dimostrazioni a conoscenza zero non interattive: in pratica, grazie a G\u00f6del, possiamo trovarle.","rel":"","context":"In "mate-light 2026"","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":35855,"url":"https:\/\/xmau.com\/notiziole\/2026\/02\/11\/un-racconto-sulle-dimostrazioni-a-conoscenza-zero\/","url_meta":{"origin":36001,"position":1},"title":"Un racconto sulle dimostrazioni a conoscenza zero","author":".mau.","date":"2026-02-11","format":false,"excerpt":"Una storiella che mi permette di spiegare meglio come funzionano.","rel":"","context":"In "mate-light 2026"","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2026\/02\/0know-a.drawio.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":35799,"url":"https:\/\/xmau.com\/notiziole\/2026\/02\/04\/logaritmo-discreto-e-dimostrazioni-a-conoscenza-zero\/","url_meta":{"origin":36001,"position":2},"title":"Logaritmo discreto e dimostrazioni a conoscenza zero","author":".mau.","date":"2026-02-04","format":false,"excerpt":"Un protocollo per dimostrare che conosco qual \u00e8 il logaritmo discreto di un numero.","rel":"","context":"In "mate-light 2026"","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":29434,"url":"https:\/\/xmau.com\/notiziole\/2024\/08\/07\/che-cosa-non-e-una-dimostrazione-elegante\/","url_meta":{"origin":36001,"position":3},"title":"Che cosa NON \u00c8 una dimostrazione elegante","author":".mau.","date":"2024-08-07","format":false,"excerpt":"Cominciamo dal fondo, insomma","rel":"","context":"In "mate-light-2024"","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"\"proof\"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/08\/%E2%80%94Pngtree%E2%80%94proof-text-effect-editable_6100719-300x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":6851,"url":"https:\/\/xmau.com\/notiziole\/2009\/02\/24\/dimostrazioni_s\/","url_meta":{"origin":36001,"position":4},"title":"Dimostrazioni senza parole","author":".mau.","date":"2009-02-24","format":false,"excerpt":"Come \"dimostrare\" senza formulacce varie","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":4023,"url":"https:\/\/xmau.com\/notiziole\/2006\/03\/22\/qed_fenomenologia_della_dimostrazione\/","url_meta":{"origin":36001,"position":5},"title":"QED – Fenomenologia della dimostrazione","author":".mau.","date":"2006-03-22","format":false,"excerpt":"Troppo tecnico, purtroppo.","rel":"","context":"Articolo simile","block_context":{"text":"Articolo simile","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/36001","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=36001"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/36001\/revisions"}],"predecessor-version":[{"id":36002,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/36001\/revisions\/36002"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=36001"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=36001"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=36001"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}