Hàm băm đồng hình từ nhóm thứ tự cơ bản $G$ đến $Z_p$

Để cho $G$ là một nhóm tuần hoàn với máy phát điện $g$ và theo thứ tự chính $p$ sao cho bài toán logarit rời rạc gặp khó khăn trong $G$.

Một hàm băm là đồng hình nếu $H(a\ast b)=H(a)\cdot H(b)$ (nơi hoạt động $\ast$ và $\cdot$ phụ thuộc vào nhóm). Ở đây, chúng tôi không mong đợi hàm băm sẽ được nén, mà là khả năng chống va chạm (CR) và có thể tính toán hiệu quả.

Bây giờ câu hỏi là, nếu tồn tại hàm băm đồng hình như vậy từ nhóm $G$ đến $Z^+_p$?

Đúng. Hàm này thường được gọi là hàm logarit rời rạc. Nó được định nghĩa bởi $$H:G\to(\mathbb Z/p\mathbb Z)^+$$ $$H(g^X)=X$$

Hàm luôn tồn tại, nhưng nếu $G$ là một nhóm mật mã, sau đó $H$ nên không thể tính toán được. Về mặt kỹ thuật, có một chức năng như vậy cho mỗi $g$, nhưng chúng đều là bội số của nhau.

Chúng tôi thường chỉ gọi đây là một hàm chứ không phải là hàm băm. Nó chắc chắn không phải là hàm băm mật mã vì nó có thể đảo ngược với $O(\log p)$ hoạt động trong $G$.

ETA: Lưu ý rằng theo thuộc tính đồng hình $H(h^a)=aH(h)$ và do đó giá trị của $H(g)$ xác định hoàn toàn chức năng. Nói cách khác, hàm logarit rời rạc và các bội số của nó biểu thị tất cả các chức năng đồng cấu có thể từ $G$ đến $(\mathbb Z/p\mathbb Z)^+$. Không có những người khác.