Puncte:1

Arătând că $F'(k, x) := F(F(k, 0^{n}), x)$ este un PRF

drapel jp

Am vrut să fac ceva practică cu privire la dovezile de reducere a securității și sunt nedumerit de acesta din cartea Boneh-Shoup.

Dacă $F(k, x)$ este un PRF sigur, apoi arată-l $F'(k, x) := F(F(k, 0^{n}), x)$ este un PRF sigur.

Ce am pana acum este:

Presupune $F'$ este nesigur, cu un distins $D'$. Aceasta înseamnă că $F$ este, de asemenea, nesigur, cu un distinctor $D$. Acum voi arăta construct $D$ folosind $D'$.

  1. $D$ primește o cheie, $k$.
  2. $D$ începe să alerge $D'$.
  3. Oricând $D'$ își interoghează oracolul pe un mesaj $x \leftarrow \lbrace0,1\rbrace^{n}$, da $x$ la $D$, calculează $y:= O(x)$, Unde $O$ este $D$oracolul lui. Apoi trimite $F(F(k, y), x)$ la $D'$.
  4. Ieșire orice $D'$ iesiri.

Aceasta înseamnă că:

Relatii cu publicul[$D'^{F'}(1^{n}) = 1] =$ Relatii cu publicul[$D^{F}(1^{n}) = 1]$ și Pr[$D'^{r}(1^{n}) = 1] =$ Relatii cu publicul[$D^{r}(1^{n}) = 1]$, Unde $r$ este o funcție aleatorie. De asemenea,

$|$Relatii cu publicul$[D^{F}(1^{n}) = 1] - Pr[D^{r}(1^{n}) = 1]| > $ neglijare$n$)

prin presupunere. Cu toate acestea, din moment ce $F$ este un PRF, aceasta este o contradicție, deci $F'$ este un PRF. $\pătrat$

Are sens această dovadă? Am senzația că am greșit definirea $D$, dar nu sunt sigur. Multumesc pentru orice ajutor!

Fractalice avatar
drapel in
De ce $D$ primește o cheie? Aveți $F(F(k,y),x)$ trimis către $D'$ (cu $y=F(k, x)$), în timp ce distinge forma $F(F(k,0), x)$. Poți să repari asta? De asemenea, trebuie să argumentați de ce ceea ce trimiteți către $D'$ este "ca aleatoriu" când $F(k, .)$ este aleatoriu.
ness64 avatar
drapel jp
@Fractalice Hmm, deci în loc de $y=O(x)$, ar fi doar $y=O(0^{n})$, iar apoi $D$ trimite $F(y,x)$ către $D '$? Bănuiesc că, în loc să obțineți o etichetă $D$, puteți calcula $y = O(0^{n})$ la pasul 1.

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.