Recunoașteți dacă două valori aleatoare sunt ridicate la aceeași putere

Alice selectează două numere aleatorii dintr-un câmp finit $Z_p$ : $a$ și $b$.

Bob face unul dintre următorii doi pași la întâmplare (uneori face pasul 1; uneori pasul 2):

1. El alege un număr aleatoriu $r$ din $Z_p$ si calculeaza $a^r\;mod\;p$ și $b^r\;mod\;p$ și îi dă Alicei aceste două valori
2. El alege două numere aleatoare diferite $r$ și $r'$ din $Z_p$ si calculeaza $a^r\;mod\;p$ și $b^{r'}\;mod\;p$ și îi dă Alicei aceste două valori

Există vreun algoritm eficient pe care Alice îl poate folosi pentru a recunoaște ce pas a făcut Bob?

Puțin aici $a$ și $b$ ar trebui selectat din $\mathbb{Z}^*_p$ și $r$ între $1$ și $p-1$ exclusiv

Arătând astfel, se pare că are legătură directă cu problema DDH, cel puțin dacă există $w$ astfel încât fie $a = b^w$ sau $b = a^w$. Asta dacă măcar unul dintre $a$ sau $b$ generează subgrupul care îl conține pe celălalt care este un dat dacă $p$ este un prim sigur [dacă ambele sunt reziduuri pătratice/nereziduuri fie există, altfel, oricare este un non-rezidu este un generator], nu sunt sigur despre celelalte cazuri. În acest caz $a, b^{r'}, a^{r}$ face triplet DDH generat din $b$ sau $b,a^r,b^{r'}$ face DDH triplet din $a$. În cazul dvs., dacă problema DDH este dificilă, nu depinde de alegerea $a$ și $b$. Dacă ambele $a$ și $b$ generați același subgrup cu o ordine mare mare, atunci problema DDH este considerată a fi dificilă într-un computer clasic. Deci, nu există un algoritm clasic eficient cunoscut în acest caz. Problema DDH poate fi rezolvată cu o probabilitate semnificativ mai mare decât presupunerea aleatorie în multe alte cazuri. De exemplu, dacă ambele $a$, $b$ sunt nereziduuri modulo $p$ iar printre $a^r, b^{r'}$ unul este un reziduu pătratic și altul este un non reziduu despre care puteți spune că unul $r,r'$ este impar și altul este par și astfel $r \neq r'$.

In intrebarea ta $a$ și $b$ sunt generate aleatoriu, așa că aș spune că se distinge. Nu în toate cazurile, dar există un avantaj în cazurile pe care le-am menționat mai devreme, care în informatică este considerat semnificativ pentru a fi considerat nedistins

Nu sunt sigur de cazul în care nici unul $a$ nici $b$ generează subgrupul care îl conține pe celălalt pentru că nu mă pot gândi la o modalitate de a-l raporta la DDH, cel puțin nu pe capul meu. Ar putea exista și unele subcazuri cu avantaje și în această stare

ACTUALIZĂRI: Ați declarat că încercați să proiectați un protocol. În primul rând, nu este prudent să încerci acest lucru fără o înțelegere profundă a criptografiei. Presupunând că întreaga securitate a sistemului se bazează pe aceasta, atunci ar trebui să utilizați a $g$ care este folosit pentru a genera $a$ și $b$ a fi un generator al unui subgrup mare de ordin prim $q$ și alegeți $r,r'$ între $1$ și $q$ pentru a se asigura că problema DDH este presupusă a fi dificilă în computerele clasice. Sau folosiți grupuri EC cunoscute, care nu se împerechează, unde problema DDH este presupusă a fi clasic dificilă. Dar încă nu știu detaliile unui protocol. Și implementarea acestuia are încă probleme precum atacurile pe canale laterale etc.

Dacă Bob este dispus să o ajute pe Alice să recunoască cazul 1, ar putea rula un protocol asemănător Schnorr ca doveditor. El ar produce un răspuns de tratare $r$ ca o cheie privată exact așa cum este specificat de protocol. Alice ar verifica dacă acest răspuns se potrivește ambelor numere aleatorii, considerate ca două chei publice.