Cel mai ieftin mod de a demonstra că două chei private diferite sunt cunoscute de aceeași persoană?

Să spunem că există două perechi de taste ECC fără legătură ($Pub_1$, $Priv_1$) și ($Pub_2$, $Priv_2$). Alice susține că le cunoaște pe amândouă $Priv_1$ și $Priv_2$, dar Bob nu are încredere în ea și crede asta $Priv_2$ este cunoscut doar de Eve, prietena lui Alice.

Bob îi cere lui Alice să demonstreze că ea controlează ambele chei private. Acum, Bob știe asta dacă Eve chiar controlează $Priv_2$, ar fi dispusă să se înțeleagă cu Alice pentru a genera o dovadă că Alice le controlează pe ambele. Dar știe și că încrederea lui Eve este limitată... Eve nu ar fi dispusă să-i spună Alicei cheia privată. $Priv_2$.

Ce dovadă i-ar putea da Alice lui Bob că ea (sau cel puțin aceeași persoană) le cunoaște pe amândouă $Priv_1$ și $Priv_2$? Rețineți că de ex. o semnătură imbricată ca de ex. $Sig_1(Sig_2(msg))$ este insuficientă, deoarece Eva doar ar putea genera $Sig_2(msg)$ și dă-i-o lui Alice să-l învelească $Sig_1$ fără să dezvăluie vreodată $Priv_2$.

O altă complicație: dovada trebuie să funcționeze eficient pe curba secp256k1. (M-am gândit să folosesc un zkSNARK pentru asta, dar bibliotecile SNARK pe care le-am văzut nu funcționează eficient pe acea curbă.)

Acest lucru pare teoretic imposibil. Din câte îmi dau seama, nu există nicio distincție între a cunoaște $priv_2$ și să se înțeleagă cu cineva care știe $priv_2$.

Să presupunem un protocol de probă $\Pi$ există între doveditorul (A) și verificatorul (B), care îndeplinește cerințele descrise. Există întotdeauna o cale pentru $A(priv_1)$ și $E(priv_2)$ a se complice pentru a executa $\Pi$ într-un fel în care $A$ nu invata nimic despre $priv_2$. $A$ și $E$ rulați doar un protocol MPC pentru a calcula următorul răspuns la $B$.

Securitatea protocolului MPC garantează asta $A$ nu învață nimic mai mult decât propria sa contribuție $priv_1$ și ieșirile, care sunt răspunsurile la $B$, pe care oricum îl poate vedea toată lumea. Si daca $\Pi$ este zero-cunoaștere la $B$ (de obicei dorit), atunci $A$ nu învață nimic din răspunsuri.

Disclaimer: nu am o dovadă de securitate pentru această schemă. Criticile sunt binevenite.

Pentru a simplifica notația, numesc cele două perechi de chei (private, publice). $(a, A = a\cdot G)$ și $(b, B = b\cdot G)$ pe punctul de bază $G$. Literele mici sunt scalare, literele mari sunt puncte EC. $H_s()$ înseamnă hash și reduce (mod the order of $G$) la un scalar. Toate operațiile între scalari (cum ar fi scăderea și înmulțirea) sunt modificate în ordinea lui $G$.

În primul rând, declara $D = a\cdot b\cdot G$.

lăsa $m = H_s(\text{"mesaj în curs de semnare"})$ ca un mesaj unic care va împiedica reutilizarea acestei semnături în diferite contexte.

A dovedi $D$ într-adevăr este construit corect, utilizați o semnătură Schnorr extinsă:

Semnătura este $(D, c, r)$ Unde $k$ este un scalar aleatoriu, $c = H_s(m \mathbin\| k\cdot G \mathbin\| k\cdot B)$ și $r = k - c\cdot a$.

Semnătura se verifică prin verificare $c \overset{?}{=} H_s(m \mathbin\| r\cdot G + c\cdot A \mathbin\| r\cdot B + c\cdot D)$ iar prin verificare $D$ este un punct valid și nu punctul de la infinit.

Asta dovedește atât că $a$ este cunoscut, și asta $a$ este atât cheia privată a punctului $A$ pe punctul generator $G$, precum și cheia privată a punctului $D$ pe punctul generator $B$. Prin urmare $D$ este dovedit a fi $a\cdot b\cdot G$.

În cele din urmă, trebuie să producem o a doua semnătură care să demonstreze că cineva le cunoaște pe amândouă $a$ și $b$. Putem face asta dovedind cunoașterea cheii private a punctului $D$ pe punctul de bază $G$ (demonstrând astfel cunoștințele despre $a\cdot b$).

Semnătura este $(c', r')$ Unde $k'$ este un scalar aleatoriu, $c' = H_s(m \mathbin\| k'\cdot G)$ și $r' = k' - c'\cdot a\cdot b$.

Semnătura se verifică prin verificare $c' \overset{?}{=} H_s(m \mathbin\| r'\cdot G + c'\cdot D)$.

Dacă Alice ar fi de acord cu Eve fără ca Eve să dezvăluie $b$, Alice ar trebui să-și dezvăluie cheia privată $a$ către Eve. Cunoștințe de $k'$ de către oricare coluder ar permite acel coluder să calculeze cheia privată a celuilalt coluder. Securitatea acestei scheme depinde de faptul că nu este posibil din punct de vedere matematic ca Alice să se înțeleagă cumva cu Eve pentru a construi $r'$ astfel încât fie Alice, fie Eve ar putea apoi determina matematic cheia privată a celuilalt.

Prin urmare, semnătura generală este $(D, c, r, c', r')$ si este $5\cdot 32 = 160$ octeți.