Ce este o schemă de criptare sigură, modernă, parțial homomorfă?

Citeam această hârtie de Philippe Golle despre utilizarea proprietăților homomorfe ale criptării ElGamal pentru a juca un joc de poker mental (adică poker criptografic sigur fără un dealer terț de încredere). Am decis că ar fi un proiect bun să încerc să implementez o versiune de bază, dar m-am confruntat rapid cu unele probleme.

Se pare că ElGamal (și RSA, de altfel) sunt considerați în general nesiguri, iar sfatul predominant pare să fie de a le evita. Astfel, cele două mari opțiuni pentru căderea homomorfismului parțial nu sunt disponibile pentru jocurile cu mize suficient de mari. În plus, nu am putut găsi cu adevărat alte criptosisteme standardizate care să aibă această proprietate și să funcționeze pe valori discrete și nu pe aproximări (necesare pentru implementarea algoritmului prezentat în lucrare). Oare imi scapa ceva evident?

Bănuiesc că întrebarea mea este: dacă Golle ar fi scris această lucrare în 2022, ce ar fi propus el în locul lui ElGamal pentru jocurile de poker cu mize suficient de mari?

ElGamal și RSA „sunt considerate în general nesigure” DACĂ se presupune Calculatoare cuantice relevante din punct de vedere criptografic. Dar acestea rămân extrem de ipotetice. Lumea (internet, banking, mobil..) rulează în prezent pe criptosisteme care, atunci când sunt asimetrice, sunt teoretic vulnerabile la aceste CRQC ipotetice: RSA, ECDSA, EdDSA, ECIES...

Criptosistemul lui Paillier merită luată în considerare atunci când se ignoră ipoteza CRQC. Este simplu¹, furnizează criptarea aditiv homomorfă a numerelor întregi (eventual semnate) cu o restricție mică și clară², are eficiență într-un mic factor constant de decriptare RSA (deci suportabilă în multe aplicații), este fără brevet, se poate reduce la o problemă matematică larg considerat a fi super-polinom pentru computerele clasice și este considerat la fel de sigur ca RSA pentru aceeași dimensiune primă.

Principalul motiv pentru care criptosistemul lui Paillier nu este foarte folosit în practică este, cred, că criptarea homomorfă în general nu este la mare căutare.

Adăugare: Criptarea Paillier nu este vulnerabilă la atacul de umplutură oracol sau la alegerea slabă a umpluturii, deoarece (spre deosebire de RSA) nu are nevoie de umplutură. Este vulnerabil la atacurile asupra implementării cam așa cum este RSA, inclusiv exploatarea generatoarelor de numere aleatoare slabe la generarea sau utilizarea cheii, canale secundare și atacuri de eroare. Asemănarea cu RSA este o veste bună, deoarece contramăsurile eficiente împotriva atacurilor sunt cunoscute pentru RSA și pot fi adaptate în mare parte la Paillier.

¹ Mai ales cu restricția comună a $n$ produsul a două numere prime de mărime egală și $g=n+1$.

² Text simplu care depășește $n$ se reduce modulo $n$, cu $n$ parametri publici suficient de mari pentru a nu constitui o problemă pentru nimic care poate fi numărat, inclusiv pentru orice fracțiune semnificativă de monedă, chiar și pentru atomi. Va contrasta cu varianta aditiv homomorfă a lui ElGamal, care are restricții severe cu privire la numerele întregi pe care le poate adăuga.

Sunt două lucruri evidente de menționat. În primul rând, cu avertismentul că am răsfoit doar pe scurt hârtia pe care ați legat-o, văd că secțiunea 3 afirmă că schema de criptare utilizată are nevoie de 3 proprietăți, și anume

1. homomorfism aditiv,

2. „comparație modulară în text clar”, de ex. verificând dacă $Enc(c)$ este o criptare de 0,

3. un protocol distribuit de generare a cheilor.

ar fi mai ușor să răspunzi la această întrebare dacă ai putea oficializa cu exactitate operațiunile/proprietățile de care ai nevoie.

Pe bază de zăbrele

Acestea fiind spuse toate, de departe cel mai comun tip de schemă de criptare parțial homomorfă în prezent sunt variantele de criptare R(LWE). Totuși, aceasta satisface o variantă „zgomotoasă” a homomorfismului aditiv, ceea ce înseamnă că se poate evalua doar o parte a priori mărginit numărul de homomorfisme aditive. Dacă aveți nevoie de adăugiri arbitrare, acest lucru se poate face și, de exemplu, schemele FHEW/TFHE sunt probabil potrivite pentru aceasta (rețineți că acestea sunt complet homomorf scheme de criptare, deși sunt deosebit de eficiente). Este plauzibil/probabil că acest lucru este în regulă în cazul dvs.

Pentru celelalte două puncte, ar trebui să citesc/cunoaștem cu mai multă atenție cerințele precise ale schemei. Totuși, mi se pare plauzibil că schemele de criptare bazate pe RLWE ar putea funcționa pentru situația dvs., dar nu mă obosesc să încerc să completez detalii pentru că...

Bazat în El-Gamal:

Deși aveți dreptate că El-Gamal „clasic” (să zicem bazat pe câmp finit Diffie Hellman) este oarecum învechit, poate sa utilizați El-Gamal pe baza grupurilor de curbe eliptice. Acesta este „modern” (deși încă slab față de computerele cuantice, dacă aceasta este preocuparea dvs.), și probabil mai ușor pentru scopurile dvs. decât să aflați detaliile despre cum să utilizați o schemă bazată pe zăbrele. Rețineți că pentru criptare generală există puține motive pentru a folosi variante de curbă eliptică ale lui El Gamal (vezi aici pentru detalii), dar deoarece doriți în mod special să utilizați homomorfismul aditiv, folosirea El Gamal are sens.

Dacă sunteți împotriva utilizării Eliptic Curve El Gamal dintr-un motiv oarecare, principalele opțiuni rămase sunt schemele bazate pe zăbrele. Acest lucru va necesita mai multă muncă pentru a afla detaliile, ceea ce va fi mai ușor pentru cei de pe acest site web să vă ajute dacă puteți spune cu exactitate ce cerințe aveți pentru schema de criptare de bază.