În primul rând, analogia ta cu aruncarea monedelor este simultan
- adevărat, și
- nu este relevant din punct de vedere criptografic.
Voi explica pe scurt de ce, oferind o declarație oficială a rezultatului aruncării monedelor.
Apoi voi încerca să răspund la răspunsul de partajare secretă, care în mod similar are un răspuns relativ simplu (negativ).
Lăsa $p\în[0,1]$ fi arbitrar. Apoi, există o procedură de eșantionare din a $\mathsf{Berna}(p)$ care foloseste $\leq H(p)+2$ coinflip-uri binare în așteptare, Unde $H(x)$ este funcția de entropie binară.
Aceasta este de la apelarea la „Eșantionarea Knuth-Yao” (cel puțin pentru a obține o limită de $H(p) + 2$).
Este relativ greu să găsiți lucrarea inițială despre aceasta, dar iirc se află în unele dintre lucrările colectate de Knuth.
Cea mai importantă parte a teoremei menționate mai sus este în așteptare afirmație.
În timp ce se poate eșantiona perfect a $\mathsf{Berna}(p)$, unu nu poti eșantionează perfect din această distribuție dacă există cel mai rău caz limita superioară a numărului de coinflips utilizate.
Se poate eșantiona dintr-o aproximare (rațională) extrem de bună la $\mathsf{Berna}(p)$, dar ați menționat că nu este ceea ce doriți.
Conteaza asta?
Răspunsul este da --- dacă numărul de coinflips pe care le folosești este variabil, atunci (în principiu) poate deschide un canal lateral.
Concret, cineva care poate observa câte coinflips au fost folosite pentru a proba $\mathsf{Berna}(p)$ poate descoperi informații non-triviale despre rezultat al $\mathsf{Berna}(p)$, care poate afecta securitatea.
Acest lucru este rău și de ce oamenii în general eșantionează dintr-un (de înaltă calitate) apropiere a unei distribuții dorite, mai degrabă decât eșantionul exact dintr-o anumită distribuție.
În ceea ce privește partajarea secretelor, răspunsul este nu.
Cel mai simplu motiv este un motiv „plictisitor”, deși voi specula puțin despre motive mai interesante pentru care răspunsul este probabil „nu”.
O schemă de partajare secretă este parametrizată formal prin două numere
- $t$, pragul pentru reconstrucția acțiunilor și
- $n$, numărul total de acțiuni.
Uneori există un al treilea parametru (pentru o anumită noțiune de partajare secretă „aproximativă”), dar nu voi acoperi acest lucru aici.
Oricum, a $(t,n)$-schema de partajare secretă este parametrizată cu doi numar natural parametrii $(t, n)$.
Apoi, fracția necesară pentru reconstrucție dacă $\frac{t}{n}$, care este (trivial) un prag rațional.
La fel de $t, n$ sunt întotdeauna date ca numere naturale, există un obstacol semnificativ în implementarea ideii dvs.
Totuși, acest lucru este oarecum plictisitor, deoarece spune doar că definiția actuală a partajării secrete împiedică ideea dvs. să funcționeze.
Dintr-un motiv mai interesant, numerele reale o fac nu se amestecă bine cu calculul.
Pentru a vedea de ce, voi vorbi pe scurt despre codificări.
Un codificare este o funcție injectivă $\phi : A\la B$.
Vrem ca codificarea lucrurilor diferite să conducă la codificări diferite, de ex. $a\neq b\implică \phi(a)\neq\phi(b)$, ceea ce înseamnă a fi „injectiv”.
Oricum
Lăsa $X$ fi o mulțime finită. Apoi pentru orice alt set $A$, orice codificare $\phi : A\la X$ are $|A|\geq |X|$.
Acesta este adesea numit „principiul pidgeonhole”.
Oricum, acest rezultat poate fi văzut ca spunând că dacă vrem ca codificarea noastră să fie într-un set finit $X$, putem avea doar un număr limitat de „lucruri de codat” $A$.
Aceasta înseamnă că dacă, dintr-un motiv oarecare, am folosit numere iraționale $\alpha$ în codificarea noastră, am putea lua în considerare doar un număr finit de multe distincte.
Când cineva face această restricție, nu este clar cum diferă lucrurile față de situația standard (terminate multe perechi de numere naturale, adică numere raționale).
De ce ne-am dori $X$ a fi finit?
Din același motiv pentru care nu putem eșantiona exact din $\mathsf{Berna}(p)$.
Dacă $X$ era infinit, apoi lungimile fiecărui lucru codificat $\varphi(x)$ ar trebui să fie fie
- „lungime infinită” (adică nu poate fi folosită pe un computer real) sau
- lungime variabilă.
Dar dacă codificarea este de lungime variabilă, se scurge informații despre ceea ce a fost codificat, ceea ce nu este potrivit pentru criptografie.
