înregistrare Logare
Puncte:1
zhuo chen avatar Crypto

PRF Xored (sau multiplicat) cu un număr aleatoriu este încă un PRF sigur?

drapel cn
zhuo chen

Știu că un PRF Xored cu cheia sa nu este un PRF sigur. Apoi mă întreb dacă articolul Xored (sau multiplicat) este un alt număr aleatoriu. Expresia formală este următoarea:

Lăsa $F_k(x):\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ fi un PRF.

"$<<$" operațiunea indică rotația la stânga, "$\cdot$„operația indică modulul de multiplicare binară $2^n$ unde an $n$- șirul de biți este interpretat ca număr în $Z_{2^n}$ și "$(a, b)$" denotă cel mai mare divizor comun al $a$ și $b$.

Î1. Defini $F'_{k_1,k_2}(x) = F_{k_1}(x) \oplus k_2$, Unde $k_2$ este aleasă uniform din $\{0,1\}^n$. Atunci este $F'_{k_1,k_2}(x)$ un PRF?

Q2. Defini $F''_{k_1,k_2}(x) = (F_{k_1}(x)<<1) \oplus k_2$, Unde $k_2$ este aleasă uniform din $\{0,1\}$. Atunci este $F''_{k_1,k_2}(x)$ un PRF?

Q3. Defini $F'''_{k_1,k_2}(x) = k_2 \cdot F_{k_1}(x)$, Unde $k_2$ este aleasă uniform din $\{0,1\}^{n-1}||1$, adică $(k_2,2^n) = 1$. Atunci este $F'''_{k_1,k_2}(x)$ un PRF?

Cred că sunt PRF-uri, dar sunt confuz cum să demonstrez în mod oficial. $k_2$ în Q.3 este necesar să fie un număr impar, deoarece dacă este par atunci $F'''$ returnează un număr par și nu poate fi un PRF.

119
0 + 0
drapel cn
Maeher
Referitor la Q3: Ce înseamnă înmulțirea acolo? Lucrăm $\pmod {2^{n}}$ acolo sau ce?
0
Răspunde
zhuo chen avatar
drapel cn
zhuo chen
@Maeher Da, înmulțirea indică înmulțirea binară $\pmod {2^n}$ și funcționează în $Z_{2^n}$. În plus, $k_2$ și $F_{k_1}(x)$ sunt interpretate ca numere în $Z_{2^n}$. Scuze pentru asta, descrierea înmulțirii nu este foarte clară din cauza tipografiei și mi-am editat tipografia.
0
Răspunde
drapel cn
Maeher
O condiție suficientă ar fi ca înmulțirea $\bmod 2^n$ cu o constantă impară să fie o permutare peste $\mathbb{Z}_{2^n}$. Intuitiv, aș spune că este adevărat, dar nu îmi vine în minte un argument formal din capul meu acum.
0
Răspunde
zhuo chen avatar
drapel cn
zhuo chen
@Maeher Da, de asemenea, cred că da, și cred că acesta este punctul de a demonstra că $F'''$ este un PRF. Cunoștințele legate de teoria numerelor pot fi utile. O sa incerc. Daca reusesc, te anunt. Mulțumesc pentru ajutor ~
0
Răspunde
zhuo chen avatar
drapel cn
zhuo chen
Dacă $A=\{a_1,a_2,\cdots, a_m\}$ este o permutare, atunci $K=\{k \cdot a_1,k \cdot a_2,\cdots, k \cdot a_m\}$ este de asemenea o permutare peste $Z_{2^n}$, unde $k$ este impar și $m \leq 2^n$. Dovada. Să presupunem că $K$ nu este o permutare și $k \cdot a_i \equiv k \cdot a_j \pmod {2^n}$ï¼ unde $i,j \in [1, m]$. Atunci avem $a_i \equiv a_j \pmod {2^n}$ deoarece $(k, 2^n)=1$, ceea ce contrazice presupunerea. Am dreptate? Și este procesul de demonstrare ulterior care demonstrează Q3 similar cu Q1?
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.