Luați în considerare o pereche $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ cu generatoare $g_1$, $g_2$ pentru $\mathbb{G}_1$, $\mathbb{G}_2$ respectiv. Grupurile $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ sunt de ordin primar $p$.
Pentru o trapă $s$, lăsa $[g_1,g_1^s,\cdots,g_1^{s^N}], [g_2,g_2^s,\cdots,g_2^{s^N}]$ să fie șirul de referință comun (deși pentru unele scheme de angajament Snarks și polinomiale, parametrul public nu conține $g_2^{s^i}$ pentru $i\geq 2$).
Elemente date $a,b\în \mathbb{G}_1$, aș dori să demonstrez în ZK că știu o constantă (spre deosebire de un polinom de grad mai mare) $\alpha$ astfel încât $a^{\alpha} = b$. Care este cel mai eficient mod de a face asta?
Am avut câteva idei:
Ideea 1:
Pentru un element generat aleatoriu $a_2\în \mathbb{G}_2$ (provocarea), Proverul trimite elementul $b_2:= a_2^{\alpha}$.
Verificatorul efectuează verificarea asocierii $\mathbb{e}(a,b_2) = \mathbb{e}(a_2,b)$
Ideea 2
Proverul dovedește în cunoștințe zero că el cunoaște un polinom $f(X)$ astfel încât $a^{f(s)} = b$ (Există modalități simple de a face acest lucru, nu prea diferite de protocolul Schnorr pentru PoK-uri de jurnale discrete)
Proverul trimite elementul $b_2:= g_2^{s^N\cdot \alpha}$ (ceea ce nu este posibil dacă $\alpha = f(s)$ pentru un polinom neconstant $f(X)$).
Verificatorul verifică dovada trimisă la Pasul 1.
Verificatorul efectuează verificarea asocierii $\mathbb{e}(a,b_2) = \mathbb{e}(b,g_2^{s^N}) $
Există protocoale mai eficiente care ar face treaba? Nu îmi place în mod deosebit ideea de a mă baza pe un algoritm de hashing care generează elemente aleatorii ale grupului $\mathbb{G}_2$ ca provocări.