înregistrare Logare
Puncte:0
Sean avatar Crypto

Indistincbilitatea computațională

drapel yt
Sean

Dat un grup multiplicativ de ordin $q$ și modul $p$. Date două constante $a$ și $b$ prelevate aleatoriu din $Z_q$. Fie variabilă aleatoare $x_a$ fi o pereche $(x, x^a \mod p)$ și variabilă aleatorie $x_b$ fi o pereche $(x, x^b \mod p)$. Ar distribuirea de $x_a$ și $x_b$ pot fi distinse din punct de vedere computațional?

67
1 + 2
Sean avatar
drapel yt
Sean
Aici se cunosc $a$ și $b$, altfel decizia este simplă: deoarece a este cunoscut, pur și simplu obține $a^{-1}$ și perechea dată $(x, x^a)$ aplică $(x^ a)^{1/a}$ și verificați dacă este egal cu $x$.
0
Răspunde
Mark avatar
drapel ng
Mark
Vrei să spui că $a$ și $b$ sunt *necunoscute*?
0
Răspunde
Puncte:1
Yehuda Lindell avatar Crypto
drapel us
Yehuda Lindell

Întrebarea este confuză în utilizarea termenului „constante”. Cu toate acestea, se spune eșantionat aleatoriu. Deci variabila aleatoare este $(x,x^a \bmod p)$ Unde $a$ este aleatoriu în $\mathbb{Z}_q$. Dacă acesta este cazul, atunci cele două distribuții sunt identice. Sunt doar aceeași distribuție cu notații diferite pentru valoarea eșantionată aleatoriu.

0 + 8
Sean avatar
drapel yt
Sean
Multumesc pentru feedback. Inca sunt putin confuz. Având în vedere o pereche $(x, x^a)$, aș presupune că probabilitatea ei să apară în a 2-a distribuție ar fi 0? Cu un alt cuvânt, $a$ și $b$ sunt fixate pentru prima și a doua distribuție. $x$ este eșantionat aleatoriu și apoi duce la tuplu $(x,x^a)$ și $(x, x^b)$.
0
Răspunde
Yehuda Lindell avatar
drapel us
Yehuda Lindell
Cred că am înțeles greșit întrebarea. Este spațiul de probabilitate numai peste alegerea lui $x$, dar nu și a lui $a$ sau $b$? În acest caz, distribuțiile sunt trivial distinse.
0
Răspunde
Sean avatar
drapel yt
Sean
Mulțumesc pentru intrare! Mă întreb care este ideea de a distinge cele două folosind un program eficient? Având în vedere $x$, cum face o mașină probabilistică diferența dintre $x^a$ și $x^b$ dacă $a$ și $b$ sunt necunoscute? Se pare că are nevoie de o mulțime de mostre (din cele două distribuții) pentru a găsi o pereche conflictuală?
0
Răspunde
Yehuda Lindell avatar
drapel us
Yehuda Lindell
Există confuzie aici. Nu este cunoscut și necunoscut. Dacă sunt fixate, atunci se presupune că sunt cunoscute. Dacă sunt necunoscute, atunci asta ar însemna că sunt alese aleatoriu și atunci este aceeași variabilă aleatorie. Desigur, poate exista un caz în care este ales un singur $a$ și apoi multe perechi cu $x$ aleatoare diferite sunt date în raport cu același $a$. În concluzie, acest lucru pur și simplu nu este bine definit.
0
Răspunde
Sean avatar
drapel yt
Sean
Cred că va trebui să-mi reformulez întrebarea:
0
Răspunde
Sean avatar
drapel yt
Sean
Permiteți-mi să reformulez întrebarea: să fie $P_a$ o mașină probabilistă care cunoaște un secret $a$ și generează o secvență de $n$ tuple: $(x_1, {x_1}^{a}), ..., (x_n) , {x_n}^a)$ unde $x_i$ pentru fiecare tuplu este eșantionat aleatoriu. În mod similar, să fie definit un PPT $P_b$. Acum, lăsați un contestator să aleagă la întâmplare două secvențe generate de $P_a$ și $P_b$ (acestea ar putea fi ambele de la $P_a$ sau una de la $P_a$ și una de la $P_b$). Se poate spune dacă cele două secvențe sunt generate de două PPT-uri diferite?
0
Răspunde
Yehuda Lindell avatar
drapel us
Yehuda Lindell
Numai $P_a$ îl cunoaște pe $a$, sau distincția cunoaște și $a$? Dacă este primul, atunci distribuțiile sunt statistic identice; dacă acesta din urmă, atunci distribuțiile se disting trivial.
0
Răspunde
Sean avatar
drapel yt
Sean
Mersi pentru raspuns! Distinctorul nu cunoaște $a$, $b$. Deci asta îmi rezolvă problema atunci. Multumesc din nou!
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.