Versiune scurta: Este o practică obișnuită (și o practică valabilă) să codificați un element $d \in \mathcal{L}$ a unei limbi într-un simulator? (făcând simulatorul neuniform și neconstructiv)
Versiune lungă:
Am un doveditor $P$ care face următoarele: este nevoie de puțin șir $d \in \mathcal{L}$ pentru unele limbi în $\textsf{NP}$, apoi criptează $d$ folosind o criptare sigură CPA pentru a obține o criptare $k$și trimite o dovadă Non-Interactive Zero-Knowledge (NIZK). $\pi$ demonstrând că $k$ criptează un mesaj $d \in \mathcal{L}$. Aș dori să spun acum că această schemă nu scurge multe informații despre $d$, în sensul că există un simulator $Sim$ astfel încât pentru orice verificator neuniform rău intenționat $V^*$:
$$\{Sim(V_\lambda^*)\}_{\lambda,d} \stackrel{comp}{\equiv} \{\textsf{OUT}_{V^*}(P_\lambda(d) \leftrightarrow V^*_\lambda)\}_{\lambda,d}$$
(cel $\{X_{\lambda,d}\}_{\lambda,d}\stackrel{comp}{\equiv}\{Y_{\lambda,d}\}_{\lambda,d}$ simbolul denotă indistincbilitatea computațională: pentru orice deosebitor neuniform $D$, există un neglijabil $\mu$ astfel încât pentru toți $\lambda \in \mathbb{N},d \in \mathcal{L}$, $|\Pr[D_\lambda(X_d)]-\Pr[D_\lambda(Y_d)]| < \mu(\lambda)$)
Fără partea NIZK, dovada este simplă: simulatorul meu ar alege doar una aleatorie $d'$ și criptați-l în $k'$: Nu pot distinge $k$ și $k'$ fără a încălca securitatea CPA. În mod intuitiv, adăugarea unei dovezi NIZK nu ar trebui să scurgă mai multe informații...Cu toate acestea, nu sunt sigur cum să rezolv acest caz: am o idee, dar mi se pare destul de ciudat (nu am văzut niciodată genul ăsta de metodă) și sunt puțin îndoielnic în privința asta.
Problema mea principală este că dacă introduc o aleatorie $d'$ la NIZK, atunci $d'$ poate să nu aparțină $\mathcal{L}$, așa că nu pot folosi simulatorul NIZK, care se așteaptă $k$ a fi o criptare a unui $d \in \mathcal{L}$. Deci ideea mea este să spun că dacă $\mathcal{L}$ nu este gol, atunci există un șir $d' \in \mathcal{L}$ (care poate fi sau nu egal cu $d$). Apoi, dacă criptez acest șir în $k'$, $k'$ este acum un element „valid” de introdus în simulatorul NIZK. Așa că aș putea rula simulatorul NIZK acum cu $k'$ pentru a obține $Sim$ Am vrut: la dovada finală a indistincibilității ar adăuga o distribuție intermediară, în care folosim $k$ cu simulatorul NIZK: primele două jocuri ar trebui să fie imposibil de distins din cauza proprietății NIZK, celelalte două jocuri ar trebui să fie imposibil de distins din cauza proprietății CPA. (Încă trebuie să scriu această schiță a dovezii în mod formal pentru a verifica dacă nu conține o greșeală stupidă).
Cu toate acestea, codificarea unui element al $\mathcal{L}$ în $Sim$ mi se pare un pic ciudat (în special pentru că simulatorul nu este constructiv și neuniform deoarece pentru orice dimensiune $d$ avem nevoie de altceva $d'$). Este ceva obișnuit/valid în dovezile Zero-Knowledge sau îmi lipsește ceva?
