În timp ce citeam tutoriale despre calculul în două părți, am întâlnit două (cel puțin formal) definiții diferite ale securității (cu adversari semi-cinstiți).
Ceea ce vreau să știu este dacă aceste definiții sunt de fapt diferite sau pot fi dovedite a fi echivalente.
Bănuiesc că sunt diferite, dar s-ar putea să-mi lipsească ceva, având în vedere că nu am citit nicăieri despre definiții diferite.
În Lindell (2016), calculul securizat în două părți este definit astfel:
Pentru fiecare parte, distribuția comună a simulării și rezultatul ideal trebuie să fie imposibil de distins din punct de vedere computațional de distribuția comună a vederii adverse și a rezultatului calculat.
Formal, pentru fiecare $i \in \{1, 2\}$, trebuie să existe p.p.t. algoritmi $S_i$ astfel încât
$$
{\lbrace (S_i(1^n, x, f_1(x, y)), f(x, y)) \rbace}_{x, y, n}
\stackrel{c}{\equiv}
{\lbrace (\operatorname{vizualizare}^\pi_i(x, y, n), \operatorname{ieșire}^\pi_i(x, y, n)) \rbace}_{x, y, n}
\,\text{.}
$$
Această definiție are sens pentru mine, deoarece autorul definește indistinguibilitatea computațională peste ansambluri de probabilitate indexate atât de parametrul de securitate și intrarea:
Două ansambluri de probabilitate $X = \{X(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ și $Y = \{Y(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ se spune că nu se pot distinge din punct de vedere computațional, notate cu $X \stackrel{c}{\equiv} Y$, dacă pentru fiecare algoritm de timp polinomial neuniform $D$ există o funcție neglijabilă $\mu(\cdot)$ astfel încât pentru fiecare $a \în \{0, 1\}^*$ si fiecare $n \în \mathbb{N}$,
$$
\lvert \Pr[D(X(a, n)) = 1] - \Pr[D(Y(a, n)) = 1] \rvert \leq \mu(n)
\,\text{.}
$$
Aceasta înseamnă că trebuie să existe o singură funcție neglijabilă $\mu$ pentru toate intrările care guvernează securitatea.
În contrast, Evans et al. (2018) definiți indistinguibilitatea computațională pentru ansambluri de probabilitate indexate doar de parametrul de securitate.
Am văzut, de asemenea, definiții ale indistingibilii computaționale ca aceasta în altă parte.
Apoi, atunci când definesc securitatea, ei solicită ca distribuțiile comune să nu se distingă din punct de vedere computațional pentru toate intrările.
Cel puțin formal, acest lucru îmi sugerează că aici, funcția neglijabilă poate depinde de intrare.
Răspunsurile la următoarele întrebări ar fi foarte apreciate:
- Pierd ceva sau înțeleg greșit definițiile? Pot definițiile arătate a fi echivalente exploatând neuniformitatea adversarului?
- Dacă nu, este cazul că, în această din urmă definiție, nu este necesar să existe o singură funcție neglijabilă care „funcționează” pentru toate intrările?
Dacă nu mă înșel, asta ar implica că cele două definiții sunt de fapt diferite?
- În cazul în care sunt diferite: care dintre definiții ar trebui preferată?
