Voi încerca să definesc cu ușurință sistemul criptografic al acestei lucrări. Autorul proiectează un joc de comunicare pentru $N$ jucători. Informațiile private ale fiecărui jucător sunt notate ca $t_i\în T_i$ și reprezintă tipul de jucător $i$. Sistemul de criptare pe care jucătorii îl folosesc pentru a comunica se bazează pe următoarele corespondențe de raportare.
$\textbf{Raportarea corespondențelor:}$ Lăsa $\mathcal{R}_i$ să fie un set nevid, finit și să definească corespondența de raportare $R_i : T_i\la 2^{\mathcal{R}_i}-\{\emptyset\}$ a fi o mapare de la jucător $i$Spațiul de tipare al colecției de subseturi de $\mathcal{R}_i$. Un element $r\in\mathcal{R}_i$ se numeşte mesaj dependent de tip şi $R_i(t_i)$ este setul de mesaje dependente de tip disponibile pentru tastare $t_i$ de jucător $i$. Mesajele dependente de tip certifică declarația unui jucător despre tipul său. De exemplu, dacă $S\în T_i$ este setul de tipuri de jucători $i$ cine poate trimite mesajul $r\în R_i$, atunci $r$ certifică o declarație de tipul âîn care se află tipul meu $S$â. Decorul $S$ este deci numit eveniment certificabil.
$\textbf{Configurații de certificare:}$ Lăsa $E_i\subseteq 2^{T_i}-\{\emptyset\}$ fi un set de submulțimi de $T_i$ care este închis sub intersecție. O configurație de certificare este o $N$-tuplu de corespondențe de raportare specifice $C_i:T_i\la E_i$ pentru fiecare $i = 1, ..., N$, cu
$$C_i(t_i)=\{e_i\in E_i|t_i\in e_i\},\quad\text{$\forall t_i\in T_i$} $$
Aceste corespondențe de raportare au două proprietăți foarte utile. În primul rând, fiecare mesaj este identic cu evenimentul pe care îl certifică. În al doilea rând, orice eveniment care poate fi certificat printr-o combinație de mesaje în $C_i(t_i)$ este inclus si in set.
Lăsa $R=(R_i)_{i\in I}$ să fie un profil arbitrar de raportare a corespondențelor și pentru fiecare jucător $i\în I$, lăsa $E_i^R$ notează cea mai mică mulțime care conține $\{R^{-1}(r_i)|r_i\in \mathcal{R}_i\}$ andd este închis sub intersecție. $E_i^R$ este setul tuturor evenimentelor acelui jucător $i$ poate certifica cu $R_i$. Profilul $R$ poate fi asociat în mod unic cu o configurație de certificare $C_R=(C_i^R)_{i\in I}$, Unde
$$C_i^R(t_i)=\{e_i\in E_i^R|t_i\in e_i\}$$
Configurația de certificare $C_i^R$ de $R$ exprimă informațiile certificabile în mod explicit ca evenimente în spațiul de tip al unui jucător.
$\textbf{Criptare:}$ Lăsa $C=(C_i)_{i\in I}$ fi o configurație de certificare. Dacă informațiile verificabile sunt criptate, pentru fiecare $i\în I$, fiecare eveniment certificabil $e_i\în E_i$ este codificat folosind un algoritm criptografic, numit cifru. Un cifr este o mapare $Ï_i: E_i à Y_i â X_i$ care are ca intrări informațiile private $e_i$ și o informație suplimentară $y_i\în Y_i$, numită cheie și produce ca rezultat un cod $x_i\în X_i$. Se presupune că setul de chei $Y_i$ este suficient de mare, adică $|Y_i| ⥠|E_i|$, și asta pentru fiecare $y_i\în Y_i$ cartografierea $Ï(\cdot, y_i)$ este bijectiv, astfel încât fiecare pereche $(x_i, y_i)$ este asociat cu exact un eveniment certificabil $e_i$. Când informațiile unui jucător sunt criptate, mesajele sale dependente de tip sunt perechi formate dintr-o bucată de cod și o cheie. În momentul în care jucătorii învață tipurile lor, natura alege public un cifr $Ï_i$ pentru jucător $i\în I$ și o cheie privată $y_i$ uniform din set
$Y_i$. Jucător $i$Corespondența de raportare este apoi dată de
$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=Ï_i(e_i, y_i), e_i\in C_i(t_i)\}$$
O interpretare naturală a mesajelor în $R_i$ este ca piese de dovezi criptate cu privire la jucător $i$Tipul, furnizat de o terță parte de încredere, care utilizează un cifr cunoscut public și o cheie privată pentru a cripta informațiile. Rețineți că dacă $C=C^R$, apoi profilele $R(\cdot)=(R_i(\cdot))_{i\in I}$ și $\hat{R}(\cdot,y)=(\hat{R}_i(\cdot,y_i))_{i\in I}$ au o configurație comună de certificare pentru fiecare combinație de taste $y\in(Y_i)_{i\in I}$
Lăsa $E^R=(E_i^R)_{i\in I}$ fie profilul seturi de evenimente cu care sunt certificabile $R$. Decorul $E_i^R$ este finită, astfel încât toate elementele sale pot fi etichetate într-o ordine arbitrară cu un index de la $1$ la un număr întreg pozitiv $n_i$. Fiecare eveniment certificabil poate fi apoi asociat cu indexul său, adică un număr din set $\{1,...,n_i\}$. voi scrie $z_i(e_i)$ pentru a face referire la numărul care reprezintă evenimentul $e_i$ și, printr-un ușor abuz de notație, voi scrie $e_i(z_i)$ pentru a se referi la evenimentul al cărui indice este egal cu $z_i$.
Este necesară următoarea lemă
$\textbf{Lema:}$ Dacă $z_i$ este o variabilă aleatoare cu suport activat $\{1,...,n_i\}$ și $y_i$ este distribuit uniform peste $\{1,...,n_i\}$ independent de $z_i$, apoi variabila aleatoare $x_i$ definit de $x_i=z_iây_i(mod{n}_i)$ este, de asemenea, distribuit uniform peste $\{1,...,n_i\}$.
Aici, $z_i$ reprezintă un eveniment certificabil, $y_i$ reprezintă o cheie și $x_i$ este codul generat de cifru $Ï_i(e_i,y_i)=z_i(e_i)ây_i(mod{n}_i)$. Acum, să presupunem că jucătorul $i$Informațiile private sunt criptate, iar corespondența de raportare este
$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=z_i(e_i)ây_i(mod{n}_i), e_i\in C_i(t_i)\}$ $
deci acel jucător $i$ poate trimite o pereche $(x_i,y_i)$ dacă evenimentul $e_i$ reprezentată de $z_i=x_i+y_i(mod{n}i)$ este in $C_i^R(t_i)$. Configurația de certificare generată în acest fel
este identică cu configurația de certificare a $R$: dacă numai tipuri de jucători $i$ care poate certifica $e_i$ cu $R_i$ poate trimite o pereche $(x_i, y_i)$ care satisface $z_i=x_i+y_i(mod{n}_i)$, atunci trimiterea unei astfel de perechi este la fel cu certificarea $e_i$. De către Lema $1$, ambii $x_i$ și $y_i$ sunt distribuite uniform peste $\{1,...,n_i\}$, și astfel, individual, $x_i$ și $y_i$ nu conțin informații despre $e_i$.
$\textbf{Întrebare:}$ Dacă presupunem că, în cazul structurii matematice de mai sus, cifrul care este definit ca bijectiv unde fiecare pereche $(x_i,y_i)$ se referă la o ecuație liniară astfel încât $h(x)=ax+b$, $b=e_i$. Dacă doi jucători știu $(x_i,y_i)$ pot să le combine și să le ia ceea ce le lipsește astfel încât $x_i+y_i(din cap{n}_i)=z_i(e_i)\quad\text{sau $e_i(z_i)$}$. Prin urmare, în cazul în care luăm pentru $h$ un polinom de grad $t<2N$ astfel încât
$$h(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0,\quad\text{unde $a_0=e_i(z_i)$}$$
care este reprezentarea echivalentă a $\rho_i$, unde știu că sunt necesare $t+1$ perechi de calculat $h(x)$ cu termen constant $e_i(z_i)$ (ceea ce în esență înseamnă că $t+1$ pereche $(x_i,y_i)$ sunt asociate doar cu una $e_i$ (bijectiv))?
Cu alte cuvinte, întrebarea se schimbă în echivalentul care spune: „Ar putea cineva ajuta la o reprezentare polinomială simplă a cifrului? $\rho_i$"?
$\textbf{Sugestie:}$ Cu un ușor abuz de notație cred că folosește autorul $\{1,...,n_i\}$ în loc de $\{0,1,...,n_i-1\}$.