Puncte:2

Paillier versus Lifted ElGamal pentru adăugarea homomorfă pentru votul electronic

drapel ng

Caut să creez un sistem de vot electronic anonim care să atribuie un anumit număr de biți fiecărui candidat în timpul unui vot, de ex. 010000 pentru Alice, 000100 pentru Bob și 000001 pentru Charlie. Funcționează bine cu ElGamal la o scară mai mică, dar când încerc să o fac pe o scară mai mare (adăugând numere mai mari), expiră. Pe de altă parte, Paillier pare să fie mai eficient în a adăuga numere mai mari.

Am câteva întrebări în legătură cu asta, deoarece nu sunt expert în criptografii:

  • ElGamal are într-adevăr o problemă cu adăugarea de numere mai mari sau aceasta se datorează unei constrângeri de implementare? Ar avea sens, deoarece folosește exponentiația, dar aș dori să confirm.
  • De asemenea, deoarece Paillier permite atât adunarea, cât și înmulțirea, îl face mai „maleabil” și mai puțin sigur decât ElGamal? Nu am putut găsi nicio măsurători pentru analiza lor comparativă de securitate, dar am descoperit că ElGamal ar trebui să fie mai eficient, de unde întrebarea mea inițială.

ACTUALIZAȚI: Acest ziarul spune ca: „De exemplu, pentru a atinge nivelul de securitate de 128 de biți, 4096 de biți p și 256 de biți q sunt în mod normal utilizate în ElGamal, în timp ce în Paillier, dimensiunea lui n este în mod normal aleasă să fie de 4096 de biți.”

Asta înseamnă că Paillier este mai slab?

Puncte:1
drapel gb

Deci, în general, criptarea ElGamal este doar homomorfă. multiplicare. Cu toate acestea, cu câteva săptămâni, se poate transforma ElGamal în ElGamal exponențial (și cred că la asta vă referiți).

Principala diferență dintre ElGamal și ElGamal exponențial este că, în loc de un mesaj: $m$ trebuie sa criptezi $g^{m}$. La decriptare, asta înseamnă că trebuie să rezolvi problema jurnalului discret pentru a obține $m$. Pentru numerele mici, aceasta nu este deloc o problemă (deci funcționează perfect într-o schemă de vot, unde numerele acumulate nu sunt atât de mari în general), dar aveți dreptate când $m$ devine mai mare, lucrurile pot deveni dezordonate și lente.

Din câte știu eu, nu aveți această constrângere cu Paillier.

Securitatea acelor algoritmi provine din ipoteze diferite. În timp ce El-Gamal se bazează pe Diffie-Hellman (respectiv Decizional-Diffie-Hellman), Paillier se bazează pe presupunerea resudiozității compozite decizionale.

Nu m-am uitat în documentele respective pentru a vedea ce dovezi de securitate oferă, dar cred că atunci când folosiți o implementare adecvată a acestora, cu parametri corespunzători, ambele sunt perfecte pentru un sistem de vot electronic.

drapel ng
Am editat întrebarea pentru a adăuga câteva cercetări. Crezi că face diferența?
Reppiz avatar
drapel gb
Cunoștințele mele despre detaliile specifice ale acelor algoritmi sunt destul de limitate, totuși dacă în lucrare se spune că acești parametri sunt aleși pentru a obține securitate pe 128 de biți, atunci ambii realizează securitate pe 128 de biți cu parametrii respectivi. Astfel, complexitatea unui atac asupra ambelor ar fi $2^{128}$ (pentru parametrii dați).
drapel ng
Ce înseamnă că necesită o cheie mai mare pentru securitatea pe 128 de biți? Ar rezulta asta într-un text cifrat mai mare?

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.