Puncte:1

Formulare matematică pentru un criptosistem

drapel cd

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\}$.

Nav89 avatar
drapel cd
@kelalaka acesta este un criptosistem pe care cred că se potrivește pe deplin la întrebarea mea anterioară. Deci, scriu asta aici...
Nav89 avatar
drapel cd
P.s. Știu că toate aceste întrebări sunt greu de răspuns, dar oricine va răspunde la una sau la unele dintre ele, voi vota în sus. Vreau doar răspunsuri. Nicio problemă dacă cineva ar putea ajuta să răspundă doar la unul dintre ele. Aș aprecia orice ajutor! Multumesc anticipat!
Nav89 avatar
drapel cd
Cred că trebuie să-mi schimb întrebările de la multe la una
Hunger Learn avatar
drapel ua
Mi se pare că ai scris întregul model pentru a obține un răspuns la această întrebare https://math.stackexchange.com/questions/4355406/if-we-re-define-this-function-could-it-be- bijective?noredirect=1#comment9096449_4355406 nu?
Nav89 avatar
drapel cd
ei bine, nu este atât de simplu. Dau un exemplu mai sus, după cum puteți vedea. Aș dori să știu dacă pot defini un cifr cu 3 chei și 3 coduri, de exemplu, deci noi perechile $(x_{i,1},y_{i,1})$, $(x_{i,2}, y_{i,2})$ și $(x_{i,3},y_{i,3})$ sunt asociate cu un $t_i$ așa cum am menționat deja... ceva de genul $\rho_i(t_i,y_ {i,1},y_{i,2},y_{i,3})=\text{calcul de $x_{i,1}$, $x_{i,2}$ și $x_{i,3 }$}$ astfel încât mesajul va fi decriptat după cum urmează $$x_{i}\oplus y_{i}=(x_{i.1}+y_{i,2})+(x_{i.2}+y_{i,2})+(x_{i. 3}+ y_{i,3}) (mod{n}_i)=z_i(e_i)$$ sau ceva de genul asta...
Nav89 avatar
drapel cd
@kelalaka vrei să-l șterg pe acesta sau pe celălalt pe care l-am postat acolo?
Nav89 avatar
drapel cd
@kelalaka ok l-am pastrat pe asta...
Nav89 avatar
drapel cd
Altceva? :)
Nav89 avatar
drapel cd
Oricum... corespondențele de raportare au întotdeauna această formulare? $$\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)\}$$ de unde obțineți informațiile pe care le doriți doar adăugând codul și cheia? Este aceasta o schemă universală? $z_i(e_i)=x_i+y_i(mod{n}_i)$
Nav89 avatar
drapel cd
întrebarea sa schimbat din nou... oricine ar putea ajuta la o reprezentare polinomială simplă a cifrului $\rho_i$?
Puncte:1
drapel ua

Ei bine, doar un gând... în cazul în care cifrul ia mai mult valeus ca chei sau coduri, asta nu înseamnă că lucrezi într-o schemă în care sunt aplicate protocoalele BGW? Și anume cu o cheie și un cod înseamnă că aveți o mapare lienară pentru cihper $\rho_i$ cu toate acestea, când aveți mai multe puncte, atunci lucrați cu polinoame. Dacă acesta este cazul, puteți generaliza schema care funcționează pentru cifrurile polinomiale și atunci aceasta poate păstra proprietățile pe care le doriți și acesta este noul mecanism.

P.s. O generalizare a dovezii protocolului BGW daca te poate ajuta cineva cu matematica si definitii...

Pot eticheta unele persoane care sunt la curent cu astfel de scheme, dar schimbați dacă doriți întrebarea dacă protocolul BGW ar putea fi aplicat cumva în această schemă... pentru multele coduri și chei care vor fi nimic mai mult sau mai puțin decât perechi de cifrul polinom aleator $\rho_i$ care va fi dat jucătorilor pentru ca nimeni să nu poată învăța $e_i$ de unul singur, dar trebuie să facă în continuare câteva calcule. În plus, dacă un jucător se înclină $e_i$ de fapt nu invata $t_i$, pentru că după cum vezi $t_i\în e_i$, ceea ce înseamnă că este suficient de informativ dar nu dă prezice $t_i$ poate conține ceva zgomot sau ceva de genul ăsta.

Nav89 avatar
drapel cd
bine gândit, dar știm că pentru fiecare polinom de grad $k$ de exemplu avem $k$ perechi $(x_i,y_i)$ care determină în mod unic polinomul $f$ cu termen constant informația $e_i$? Pentru că dacă acesta este cazul, ipoteza bijectivă despre $\rho_i$ rămâne
Nav89 avatar
drapel cd
dupa comentariul tau cred ca acesta este punctul exact. Îmi voi redefini întrebarea acum

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.