Puncte:2

Pentru orice numere $a, b$, care sunt operatorii $X, Y$ astfel încât dezvăluirea $a\ X\ b$ și $a\ Y\ b$ nu dezvăluie informații despre $a,b$?

drapel in

Anterior M-am gândit la o pereche de numere aleatoare de 8 biți distribuite uniform $(a,b) \în \{0,1\}^8$, și $X$ să fie XOR pe biți, $Y$ să fie adăugare de 8 biți. Dar s-a dovedit acea revelație $a \text{ XOR } b, a+b \bmod{2^8}$ dezvăluie o mulțime de informații despre $a,b$.

Un tip destept aici a menționat „dependența” ca proprietate. Deci, cred că caut operatori independenți? Sau, cel puțin, operatori care sunt independenți atunci când intrarea lor sunt numere aleatoare?

Întrebările mele sunt:

  • Cât de departe putem merge în a minimiza cantitatea de informații care $a\ X\ b$ și $a\ Y\ b$ da despre $a,b$?
  • Putem demonstra matematic orice limite? De exemplu. demonstrând că dacă $a,b$ sunt numere aleatoare uniforme, atunci dacă $X$ este... și $Y$ este..., atunci trebuie să fie așa $a\ X\ b$ și $a\ Y\ b$ nu poate da mai mult de $x$ biți de informații despre $a,b$?
fgrieu avatar
drapel ng
Dacă $X$ (respectiv $Y$) poate lua valori $u$ (respectiv $v$) peste setul complet al celor două argumente, atunci $a\ X\ b$ și $a\ Y\ b$ împreună nu poate lua mai mult de $u\,v$ valori, prin urmare nu poate dezvălui mai mult de $\log_2(u\,v)$ biți de informații. O limită mai bună este posibilă pentru o alegere de $X$ și $Y$ care fac valorile „dependente”, dar nu știu cum să caracterizez asta mai bine decât definirea dependenței ca diferență între acea limită și cantitatea reală de informații dezvăluit,
caveman avatar
drapel in
@fgrieu - Încerc să înțelegem: dacă ne ocupăm doar de variabile de 8 biți, atunci asta înseamnă că $u=v=8$? De asemenea, ai idee cum să demonstrezi legătura $\log_2(uv)$? Mulțumesc mult.
fgrieu avatar
drapel ng
$u$ și $v$ depind de $X$ și $Y$. Dacă definim $a\ X\ b $ și $a\ Y\ b $ ca fiind 42 indiferent de $a$ și $b$, atunci $u=v=1$, $\log_2(u\,v)$ este $0$ și, astfel, această limită superioară ne spune că nu este dezvăluită nicio informație despre $a$ și $b$. Observați că atunci când $a\ X\ b $ și $a\ Y\ b $ sunt neconstante, dar egale indiferent de $a$ și $b$, avem $u=v>1$, limita $\log_2( u\,v)$ ține dar este liber. Dovada limitei $\log_2(u\,v)$: o variabilă care ia valori $w$ nu poate dezvălui mai mult de $\log_2(w)$ biți de informații, iar pentru $(X,Y)$ obținem cel mult $w=u\,v$ valori.
fgrieu avatar
drapel ng
Mă întreb: vă gândiți la „cantitatea de informații pe care $a\ X\ b$ și $a\ Y\ b$ o oferă aproximativ $a,b$” (care poate fi întotdeauna de până la 16 biți, presupunând, de exemplu, $ a\ X\ b$ returnează $a$ și $a\ Y\ b$ returnează $b$), sau cantitatea de informații pe care $a\ X\ b$ și $a\ Y\ b$ o oferă aproximativ una dintre $a$ sau $b$, celălalt fiind privit ca aleatoriu și necunoscut (evident că nu poate depăși 8 biți)?
caveman avatar
drapel in
@fgrieu Primul. Ambele $a,b$ ar trebui să fie pe cât posibil secrete. Încerc să aflu cât de departe se poate ajunge cu operatorii $X,Y$ în ceea ce privește reducerea la minimum a scurgerilor de informații de pe $a,b$. Înțeleg de ce $\log_2(uv)$ este o limită maximă liberă (deoarece aceasta este informația maximă conținută în $uv$ multe numere unice).
Puncte:2
drapel sa

Este posibil să se scurgă informații zero. Să presupunem că sunt distribuite uniform $a$ și $b$ si lasa $a$ variază de-a lungul rândurilor și $b$ de-a lungul coloanelor din tabelele de operații de mai jos:

$$ \begin{matrice}{ccc} \begin{matrice}{c|cccc} X & 0&1&2&3\ \hline 0 & 0&1&2&3 \ 1 & 1&2&3&0 \ 2 & 2&3&0&1 \ 3 & 3&0&1&2 \end{array} & \quad & \begin{matrice}{l|cccc} Y & 0&1&2&3\ \hline 0 & 3&0&1&2 \ 1 & 0&1&2&3 \ 2 & 1&2&3&0 \ 3 & 2&3&0&1 \end{matrice} \end{matrice} $$

Rețineți că pentru fiecare operație cunoașterea ieșirii ($aXb$ sau $aYb$) nu oferă deloc informații despre $a$. Același lucru este valabil și pentru $b$. Dar dacă știi unul dintre $a$ sau $b$ atunci îl cunoști pe celălalt în mod unic.

Mai mult, să spunem $aXb=0.$ Perechile posibile $(a,b)$ sunt acum în set $$ S=\{(0,0),(1,3),(2,2),(3,1)\}. $$

Presupunând că nu există erori în calcularea operațiunii, singura posibilitate pentru $aYb$ este $aYb=3$ iar asta dă nici o informatie despre posibilele perechi în $S$.

Puteți spune că acesta este un exemplu ciudat, dar demonstrează că minimul poate fi zero pentru fiecare variabilă de intrare individuală.

Un ultim punct, pentru că nu vă cunosc exact cerințele. Este posibil să se dubleze lungimea de biți a ieșirii, asigurând în același timp cunoașterea uneia dintre ele $a$ sau $b$ nu scurge nicio informație despre celălalt. Ieșirea $2X3=12$ ar corespunde modelului de biți de ieșire $0110$ cu $01=1,$ și $10=2.$ Iată un exemplu mai jos:

$$ \begin{matrice}{c|cccc} X & 0&1&2&3\ \hline 0 & 00&11&22&33 \ 1 & 13&02&31&20 \ 2 & 21&30&03&12 \ 3 & 32&23&10&01 \end{matrice} $$ Acum să spunem că știi asta $a=1.$ Acest lucru vă limitează la al doilea rând al mesei de operație dar $b$ este încă complet nedeterminat, știi nimic despre valoarea de $b.$

Acest exemplu folosește două MOLS (Pătrate Latine Mutually Orthogonal).

caveman avatar
drapel in
_Uimitoare-totală-uimire-superioare_. Aceasta este glorie pură. Mulțumesc mult. Cu toate acestea, nu o primesc pe cea cu lungime dublă de biți: dacă $aXb = 12$, nu ar fi o căutare trivială pentru a vedea că trebuie să fie $a=2, b=3$? i.e. ambele $a,b$ sunt expuse? Poate că îmi scăpa ceva fundamental?
kodlu avatar
drapel sa
În modelul teoretic al informației despre scurgerea informațiilor observăm anumite variabile și ne întrebăm despre incertitudinea cu privire la celelalte variabile odată ce această valoare este cunoscută. Deci observăm, de exemplu, $aXb$ și întrebăm despre $a$ sau $b$ sau $a,b$ ambele. Alternativ, observăm $a$ și $aXb$ și întrebăm despre $b$. De asemenea, dacă aplicăm modelul unui set mai mare într-un context criptografic, forța brută nu este fezabilă.
caveman avatar
drapel in
Pur și simplu nu sunt în stare să citesc ultimul tabel. $2X3 = 12$, nu? Dar textul tău spune $1X2=12$?
kodlu avatar
drapel sa
vezi editarea pentru o clarificare

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.