Hash omomorf de la grupul de ordine prim $G$ la $Z_p$

Lăsa $G$ fie un grup ciclic cu generatorul $g$ și de ordin prim $p$ astfel încât problema logaritmului discret este dificilă $G$.

O funcție hash este homomorfă dacă $H(a\ast b)=H(a)\cdot H(b)$ (unde operațiunile $\ast$ și $\cdot$ depind de grupuri). Aici nu ne așteptăm ca funcția hash să fie compresivă, ci rezistența la coliziune (CR) și calculabilă eficient.

Acum întrebarea este dacă există o astfel de funcție hash homomorfă din grup $G$ la $Z^+_p$?

Da. Funcția este de obicei denumită funcție de logaritm discret. Este definit de $$H:G\to(\mathbb Z/p\mathbb Z)^+$$ $$H(g^X)=X$$

Funcția există întotdeauna, dar dacă $G$ este un grup criptografic, atunci $H$ ar trebui să fie imposibil de calculat. Din punct de vedere tehnic, există o astfel de funcție pentru fiecare $g$, dar toți sunt multipli unul celuilalt.

De obicei, am numi aceasta doar o funcție, mai degrabă decât o funcție hash. Cu siguranță nu este o funcție hash criptografică, deoarece poate fi inversată $O(\log p)$ operațiuni în $G$.

ETA: Rețineți că prin proprietatea homomorfă $H(h^a)=aH(h)$ si deci valoarea de $H(g)$ determină complet funcția. Cu alte cuvinte, funcția logaritm discret și multiplii ei reprezintă toate posibile funcţii homomorfe din $G$ la $(\mathbb Z/p\mathbb Z)^+$. Nu sunt altele.