Aleatorie scurtă în ElGamal și Paillier

Securitatea semantică în această setare se reduce la securitatea semantică pentru schema standard dacă și numai dacă o anumită distribuție cu entropie scăzută în subgrupul „zero text cifrat” nu se poate distinge din punct de vedere computațional de aleatoriu.

• În cazul lui ElGamal, presupunerea este că $(g^r, h^r)$ pentru mici aleatorii $r$ nu se distinge din punct de vedere computațional de o pereche DH standard, și anume $(g^r, h^r)$ pentru uniformă $r$. Acest lucru a fost studiat de Kurosawa și Koshiba într-un Hartie PKC 2004, și au arătat că ipoteza este valabilă dacă problema logului discret cu exponent scurt computațional este grea. Pentru grupurile cu relevanță criptografică, cel mai bun atac asupra jurnalului discret cu exponent scurt este de obicei fie lambda lui Pollard, fie același ca pentru jurnalele discrete non-scurte, deci dacă $r$ este suficient de mare (cel puțin de două ori parametrul de securitate), acest lucru este considerat ok. Cu toate acestea, aceasta s-a legat $r$ oricum, este aceeași cu limita pentru un exponent de dimensiune completă dacă setați corect parametrii, așa că este inutil să faceți acest lucru în majoritatea setărilor.

• În cazul lui Paillier, presupunerea este că $r^n$ pentru mici $r$ nu se distinge din punct de vedere computațional de aleatoriu în subgrupul de ordine $\varphi(n)$ de $\mathbb{Z}/n^2\mathbb{Z}$. Nu sunt conștient de niciun atac asupra acestei probleme specifice și pare oarecum plauzibil dacă $r$ nu este prea mic, deși nu știu cu ce presupunere mai standard ar putea fi legată. Indiferent, cu toate acestea, accelerarea de la utilizarea unui mai mic $r$ în calculul $r^n \bmod n^2$ ar trebui să fie neglijabil (de fapt, nu ar trebui să existe deloc accelerare dacă utilizați aritmetică rapidă), așa că nici nu sunt sigur că văd rostul acestei variante.