TL,DR: o conjuncție de simplu $\Sigma$-protocoalele pot dovedi această afirmație compusă în cunoștințe zero. Cu toate acestea, dovada este oarecum mare.
În primul rând, să descompunem declarația ta compusă în declarații mai simple. Observați că, în esență, doriți să dovediți în cunoștințe zero pentru $C_1=m^e$ și $C_2=g^m$ că următoarea relaţie $\mathcal{R}(x,\omega)$ ($x$ este parametrul public și $\omega$ este martor) susține: $$\mathcal{R}=\{((C_1,C_2),(m,l)):m\în QR_{N}\land C_1=m^e\bmod{N}\land C_2=g^m \bmod{p}\}, $$
Unde $l$ este rădăcina pătrată a $m\bmod{N}$, adică martorul este $(m,l)$ pereche. De dragul simplității, să folosim următoarea notație pentru afirmațiile elementare: $$\mathcal{R}_1=\{((C_1,C_2),(m,l)):m\în QR_{N}\}, $$
$$\mathcal{R}_2=\{((C_1,C_2),(m,l)): C_1=m^e\bmod{N}\}, $$
$$\mathcal{R}_3=\{((C_1,C_2),(m,l)):C_2=g^m\bmod{p}\}. $$
Rețineți că ambele afirmații elementare $\mathcal{R}_2$ și $\mathcal{R}_3$ sunt ușor de dovedit cu $\Sigma$-protocoale, deoarece ambele relații dovedesc cunoașterea unei preimagine sub un homomorfism de grup (adică a $w$ satisfăcător $x=\phi(w)$). În cazul în care $\mathcal{R}_2$ homomorfismul de grup $\phi(\omega)=\omega^e$, in timp ce in $\mathcal{R}_3$, homomorfismul este $\phi(\omega)=g^{\omega}$. Acestea sunt afirmații destul de standard și puteți găsi cum să demonstrați preimaginea unui homomorfism în Bangerter și colab. sau în Cartea Boneh-Shoup, printre multe altele.
A dovedi $\mathcal{R}_1$ este un pic cam complicat la prima vedere, din moment ce $m$ trebuie ținută secretă și vrem să dovedim asta $m$ este un reziduu pătratic, adică $m\în QR_N$. În aproape toate implementările criptosistemului RSA $e$ este ciudat (presupun că acesta este și cazul în aplicația dvs.), așa că $C_1=m^e\în QR_{N} \iff m\în QR_{N}$. Presupun, de asemenea, că criptatorul știe $l$, una dintre rădăcinile pătrate ale $m$, deoarece factorizarea este necunoscută. Dacă criptatorul nu cunoaște un astfel de $l$, atunci nu poate dovedi că este un reziduu pătratic, deoarece nu cunoaște factorizarea. Având în vedere această discuție, acum $\mathcal{R}_1$ presupune în esență demonstrarea următoarei afirmații: $$\mathcal{R}_1=\{((C_1),(l)):C_1=l^{2e}\bmod{N}\}, $$
care este din nou o dovadă a cunoașterii unei preimagine a unui homomorfism de grup. Știm cum să dovedim această afirmație.
Pentru a combina toate acestea pentru a obține o dovadă de cunoștințe zero pentru declarația compusă $\mathcal{R}$, verificatorul trebuie doar să trimită aceeași provocare aleatorie pentru toate instrucțiunile elementare (provocarea aleatoare este diferită de-a lungul repetărilor protocolului!).
Care este dimensiunea dovezii? Pentru $\Sigma$-protocoale în grupuri de ordine necunoscută, eroarea de soliditate este mare, așa că trebuie să repetați $\Sigma$-protocol de multe ori pentru a obține niveluri rezonabile de soliditate. La fiecare repetare, eroarea de soliditate scade cu $\aproximativ 1/2$. Prin urmare, protocolul trebuie repetat secvențial pentru a obține o eroare de cunoștințe suficient de mică (de exemplu, $80$ repetări secvențiale sunt necesare pentru a obține o eroare de cunoaștere a $1/2^{80}$). Aceasta ar rezulta într-o dovadă constând în $2*2*80=320$ elemente de grup pentru $3$ enunțuri elementare (2 dintre enunțuri apar într-un grup RSA, de aceea trebuie să repetăm de multe ori).
Pentru a evita această limitare de eficiență, trebuie să utilizați un șir de referință comun pentru a reduce dimensiunea probei. Vedea Bangerter și colab.
Sper că asta ajută! Anunță-mă dacă am lăsat vreo zonă gri în răspuns!
