Doi oameni care nu au încredere vor să vină cu un număr aleatoriu

Doi oameni vor să vină cu un număr aleatoriu. Nu au încredere unul în altul și nici în niciun terț. Care sunt soluțiile cunoscute la această problemă?

Sunt student la criptografia cuantică și acum lucrez la generarea de numere aleatoare cuantice.Orice soluții, fie clasice, fie cuantice, sunt binevenite.

EDITAȚI | ×

Ok, iată ce am înțeles citind câteva lucrări. Să presupunem că două părți neîncrezătoare vor să vină cu ceva aleatoriu. În scenariul clasic (fără a presupune duritatea de calcul) sarcina este imposibilă. În scenariul cuantic, există două variante; versiuni puternice și slabe. Dacă rezultatul dorit al fiecărei părți este nu se știe că se numește versiunea puternică și invers. Versiunea puternică are o limită diferită de zero asupra părtinirii sale, în timp ce versiunea slabă poate avea o părtinire arbitrar mică.

https://arxiv.org/pdf/1911.13283.pdf

Numărul aleatoriu necesar este un număr întreg între 0 și $\ell$. Fiecare persoană alege un număr aleatoriu $x_i$ intre 0 si $\ell$, și fiecare persoană alege un $n$-bit factor de orbire aleatoriu $b_i$ Unde $n\geq 128$ și $n$ trebuie convenit în prealabil. Fiecare anunță apoi un angajament hash calculat ca $H(b \mathbin\|x)$. Apoi fiecare își deschide angajamentele anunțându-și valorile $b$ și $x$, și calculați numărul lor aleatoriu ca $$x_1 + x_2\ \pmod \ell.$$ Acest lucru este cuantic-secure dacă hash și alegere de $n$ sunt împreună cuantic-sigure.

După cum subliniază @poncho, persoana care își deschide ultima angajament poate simula un eșec de a finaliza protocolul dacă nu este mulțumită de valoarea particulară aleatorie partajată care ar fi generată în timpul acelei invocări a protocolului.Aceasta ar putea fi o problemă mai ales dacă $\ell$ este mic.

O modalitate de a evita această problemă este să vă asigurați că există o pierdere pentru nefinalizarea protocolului. De exemplu, fiecare persoană ar putea depune fonduri la un arbitru de încredere care ar confisca acele fonduri de la persoana care nu a finalizat protocolul. Pierderea trebuie să fie egală sau să depășească câștigul maxim posibil din simularea unei defecțiuni.

cred această hârtie îți rezolvă cel puțin parțial problema.

Manuel Blaum a analizat această problemă în 1981 în Răsturnarea monedelor prin telefon Un protocol pentru rezolvarea problemelor imposibile

Detaliile tehnice sunt pe hartie. Acest protocol le garantează (din hârtie, bolds are mind);

1. Dacă oricare dintre participanți respectă protocolul nu îl prinde pe celălalt trișând, el sau ea poate fi sigur că fiecare monedă are exact 50-50 de șanse independente a da rezultate (demonstrabil în ipoteza rezonabilă că factoring-ul este greu.
2. Dacă oricare participant îl prinde pe celălalt trișând, el sau ea poate dovedi acest lucru unui judecător (acest lucru presupune că toate mesajele sunt trimise semnate).
3. După ce Bob îi aruncă monede lui Alice, ea știe ce monede au venit în cap, care cozi. Nu ar trebui să aibă absolut nicio idee cum au apărut (nici măcar o presupunere bună).
4. După succesiunea de răsturnări de monede, Alice ar trebui să-i poată demonstra lui Bob care monede au venit în cap, care cozi.