next up previous
Successivo: Analisi dell'informazione di Bob Su: Bit commitment Precedente: Bit commitment

Il protocollo

Forniamo, innanzitutto, alcuni formalismi matematici che ci saranno utili nel seguito. Sia tex2html_wrap_inline1937 la variabile casuale che assume il valore binario 0 con probabilità p e 1 con probabilità 1-p. Se p=1/2 ometteremo l'apice 1/2. Denotiamo con tex2html_wrap_inline1945 la funzione selezione tale che tex2html_wrap_inline1947 . Sia tex2html_wrap_inline1949 il prodotto scalare booleano, cioè se tex2html_wrap_inline1951 , tex2html_wrap_inline1953 sono gli i-esimi bit di x e y, avremo:

displaymath1959

Sia, infine, tex2html_wrap_inline1631 un limite superiore alla percentuale d'errore del canale quantistico, cioè la probabilità che un fotone tex2html_wrap_inline1963 polarizzato venga rilevato come tex2html_wrap_inline1965 . Desciviamo, inizialmente, il protocollo commit(x) utilizzato da Alice per impegnarsi ad un bit x nei confronti di Bob.

commit(x)

  1. Bob sceglie una matrice booleana M come una matrice generatrice di un codice binario lineare (n,k,d) C, tale che tex2html_wrap_inline1969 e k/n = 0.52 e la annuncia ad Alice.
  2. Alice sceglie una stringa casuale a n bit tex2html_wrap_inline1975 e la annuncia a Bob.
  3. Alice sceglie una parola codice casuale a n bit tex2html_wrap_inline1979 da C, tale che tex2html_wrap_inline1981 .
  4. Per i=1,...,n
  5. Per i=1,...,n
Siano c', b e b' i vettori tex2html_wrap_inline2049 , tex2html_wrap_inline2051 e tex2html_wrap_inline2053 . Alice tiene x, c e b segreti finché (e se) le rivelazioni hanno luogo, mentre Bob tiene c' e b' segreti per sempre. Notiamo anche che il vettore casuale r è fornito a Bob in chiaro, mentre la parola codice casuale c è mandata attraverso il canale quantistico, codificandola mediante fotoni polarizzati nelle basi scelte casualmente. Poichè Bob non conosce in quali basi i fotoni sono polarizzati, egli li misura in basi scelte casualmente. Quando sceglie la base corretta ( tex2html_wrap_inline2067 ), il che avviene con probabilità 1/2, egli ottiene il corretto bit ( tex2html_wrap_inline2069 ), eccetto con probabilità d'errore al più tex2html_wrap_inline1631 . Dall'altro lato, quando sceglie la base errata ( tex2html_wrap_inline2073 ), il suo bit non è correlato con il bit di Alice, tuttavia, tex2html_wrap_inline2069 ugualmente con probabilità 1/2 (in quanto anche se sbaglia la base, comunque puó ottenere 0 o 1 con probabilità 1/2, per il principio di indeterminazione). Quindi, la lettura di Bob della parola c di Alice è corretta su approssimativamente il tex2html_wrap_inline2079 dei bit ( tex2html_wrap_inline2081 nel primo caso e tex2html_wrap_inline1371 nel secondo, per cui in media tex2html_wrap_inline2079 ). Un ingannevole Bob, come sappiamo, potrebbe ottenere circa l' tex2html_wrap_inline2087 dei bit correttamente, utilizzando la base Breidbart, e dimostreremo che questo è il meglio che possa fare. Notiamo, inoltre, che il codice lineare C è scelto in maniera tale che ci sono esponenzialmente molte parole codice intorno a quella ricevuta da Bob, c', che sono alla stessa distanza di Hamming da quella trasmessa da Alice c. Ciò per evitare che Bob possa risalire più facilmente alla parola c di Alice e, quindi, ad x. Per questo motivo, la distanza minima tra parole codice non dovrebbe essere grande (perché, altrimenti, le parole codice alla stessa distanza da c sarebbero poche da trovare). Il risultato precedente è indispensabile per un corretto protocollo, perché come vedremo nel seguito (teorema 5.4), essendo r scelta casualmente, la conoscenza di r e c' danno a Bob un ammontare di attesa informazione di Shannon esponenzialmente piccola su tex2html_wrap_inline2101 . Dall'altro canto , tuttavia, la distanza minima tra parole codice deve essere sufficientemente grande da prevenire Alice nel trovare due differenti parole codice, tex2html_wrap_inline2103 e tex2html_wrap_inline2105 (insieme con basi mandate possibilmente false) in maniera tale da poter affermare di aver mandato l'una anziché l'altra, così che Bob sarebbe disposto a dare la colpa agli errori di trasmissione per la differenza tra la parola codice mandata da Alice e la sua misura c' (Teorema 5.7). Di conseguenza è necessario bilanciare queste due esigenze, nella scelta della distanza minima del codice C, per prevenire Alice e Bob dall'ingannare, da cui i misteriosi parametri tex2html_wrap_inline2109 e 0.52 nel protocollo commit(x). A questo punto, se Alice decide di rivelare il suo impegno x, affinché Bob possa apprendere il corretto valore di x e provare che Alice aveva in mente proprio quel bit, è necessario che entrambi intraprendano il seguente protocollo: unveil((c,b,x),(c',b'))
  1. Alice rivela c,b e x a Bob.
  2. Bob pone

    displaymath2131

  3. if ( tex2html_wrap_inline2133 ), ( tex2html_wrap_inline2101 ) e (c è una parola codice)

    then Bob dà in output accettato

    else Bob dà in output rifiutato

In effetti, i parametri che Alice rivela al passo 1 potrebbero anche non essere quelli reali. Tuttavia vedremo che la sicurezza del protocollo è garantita dal valore 1.4 tex2html_wrap_inline1631 .


next up previous
Successivo: Analisi dell'informazione di Bob Su: Bit commitment Precedente: Bit commitment

Aniello Castiglione e Gerardo Maiorano < anicas,germai@zoo.diaedu.unisa.it >