Există un protocol de criptare asimetrică care oferă în mod arbitrar multe chei publice aparent fără legătură pentru o singură cheie privată?

Caut un protocol de criptare cu următoarele proprietăți.

• Alice are o cheie privată $x$. Folosind această cheie privată, ea alege cheia publică $p$ corespunzătoare acestei chei private. L-a informat pe Bob despre această cheie publică. Bob folosește apoi această cheie publică pentru a cripta un mesaj către Alice.
• Mai târziu, Alice vrea să primească din nou un mesaj. Ea creează cheia publică $q$ folosind la fel cheie privată $x$. Bob folosește apoi această cheie publică pentru a cripta un mesaj pentru Alice.
• Bob nu ar trebui să poată deduce din $p$ & $q$ că cele două chei publice $p$ și $q$ au fost generate folosind aceeași cheie privată $x$.
• Alice nu ar trebui să aibă mai mult de o cheie privată.
• Protocolul ar trebui să permită lui Alice să producă în mod arbitrar multe chei publice, dacă li se permite să fie arbitrar lungi.

Există un astfel de protocol?

Pentru a completa răspunsul generic, iată o construcție concretă bazată pe ElGamal.

ElGamal bazat pe un grup $G$ de ordine $p$ cu generator $g$ are o cheie publică $y = g^a$, Unde $a$ este cheia privată.

Pentru a crea o nouă cheie publică, alegeți un număr aleatoriu $s$ și calculează $(u,v)$ la fel de $u=g^s$ și $v=y^s$.

Pentru a cripta $m$ cu $(u,v)$, alegeți un număr aleatoriu $r$ și calculează $(x,w)$ la fel de $x=u^r$ și $w = v^r m$.

Pentru a decripta $(x,w)$, calculează $wx^{-a}$.

În ipoteza DDH, $(u,v)$ nu se distinge de o pereche aleatorie, așa că este bine. Este ușor să arătați că schema este sigură sub DDH.

Exercițiu pentru cititor: este util să ne dăm seama de ce această schemă este în esență doar ElGamal.

Extensiile la spații de mesaje mai utile sunt triviale folosind tehnici standard.

Această schemă (cu câteva trucuri suplimentare) a fost folosită pentru a construi malware teoretic mai bun. (Din câte știu eu, nu a fost niciodată folosit pentru a construi malware real.)