(â¦) este $\alpha\oplus\beta$ imposibil de distins de un număr aleatoriu?
Rețineți că trebuie să convertim $\alpha$ și $\beta$ la șiruri de biți pentru a se aplica XOR pe biți. Deci cu adevărat calculăm $\subliniat\alpha\oplus\subliniat\beta$ Unde $\subliniat\gamma$ is este notația pentru o reprezentare definită în mod unic a unui element de grup arbitrar $\gamma$ ca șir de biți de dimensiune fixă și este întrebat dacă $\subliniat\alpha\oplus\subliniat\beta$ este un șir de biți aleatoriu. Răspunsul va depinde de reprezentarea folosită.
Este ușor să găsiți un contraexemplu clar cu un grup criptografic familiar și o reprezentare, cum ar fi subgrupul de reziduuri pătratice al grup multiplicativ modulo $(2p+1)$, când $p$ este un mare aleatoriu Sophie Germain prim de exemplu, 1999 biți¹ și biți conducători 1010, și reprezentarea elementelor grupului ca șiruri de biți de 2000 de biți per big-endian convenţie. $\subliniat\alpha$ și $\subliniat\beta$ sunt șiruri de biți de 2000 de biți cu o părtinire marcată către 0 în primii doi biți și există o părtinire similară (deși mai mică) în primii doi biți ai $\subliniat\alpha\oplus\subliniat\beta$.
Pe de altă parte, dacă în cele de mai sus înlocuim 1010 cu 111â¦111 deci peste 200 de biți² $\subliniat\alpha$ va fi imposibil de distins de aleatoriu, cu excepția reprezentării unui $\alpha$ acesta este un reziduu pătratic. În ciuda acestui fapt, și $\alpha$ și $\beta$ nefiind strict independentâ´, presupun că ambele efecte sunt suficient de slabe încât $\subliniat\alpha\oplus\subliniat\beta$ nu se distinge din punct de vedere computațional de aleatoriu.
Pentru orice reprezentare a elementelor de grup ca șir de biți, putem concepe o altă reprezentare de aceeași dimensiune prin aplicarea unei Pseudo-Permutații aleatorii reversibile și calculabilă publică la reprezentare. Proprietățile grupului rămân, criptarea ElGamal încă funcționează și este la fel de sigură. Și acum, pentru orice $p$ suficient de mare încât DLP-ul să fie greu, $\subliniat\alpha\oplus\subliniat\beta$ poate fi dovedit că nu se poate distinge din punct de vedere computațional de aleatoriu folosind proprietățile PRP.
¹ Astfel încât criptarea ElGamal este sigură, ceea ce este implicit în întrebare.
² Poate dorim să mărim dimensiunea biților a $p$ ușor pentru a compensa problema logaritmului discret fiind ușor ușurată de $p$ fiind aproape de o putere de doi.
³ O caracteristică care poate fi testată eficient verificând simbolul Legendre $\left(\frac\alpha{2p+1}\right)\,\underset{\text{def}}=\,\alpha^p\bmod(2p+1)$ este $+1$
â' Observă asta $\alpha^{-1}\beta\bmod(2p+1)$ este un element ușor părtinitor al grupului.
