Гомоморфный хэш из группы простого порядка $G$ в $Z_p$

Позволять $G$ – циклическая группа с образующей $г$ и первого порядка $р$ так что проблема дискретного логарифмирования сложна в $G$.

Хеш-функция гомоморфна, если $H(a\ast b)=H(a)\cdot H(b)$ (где операции $\аст$ и $\cdot$ зависит от группы). Здесь мы не ожидаем, что хэш-функция будет сжимающей, но устойчивой к коллизиям (CR) и эффективно вычисляемой.

Теперь вопрос в том, существуют ли такие гомоморфные хеш-функции из группы $G$ к $Z^+_p$?

Да. Эту функцию обычно называют функцией дискретного логарифма. Это определяется $$H:G\to(\mathbb Z/p\mathbb Z)^+$$ $$H(g^X)=X$$

Функция всегда существует, но если $G$ является криптографической группой, то $Ч$ должно быть невозможно вычислить. Технически, есть одна такая функция для каждого $г$, но все они кратны друг другу.

Обычно мы просто называем это функцией, а не хэш-функцией. Это, конечно, не криптографическая хэш-функция, поскольку ее можно инвертировать с помощью $ О (\ журнал р) $ операции в $G$.

ETA: Обратите внимание, что по гомоморфному свойству $Ч(ч^а)=аЧ(ч)$ и поэтому значение $Ч(г)$ полностью определяет функцию. Другими словами, функция дискретного логарифма и ее кратные представляют все возможные гомоморфные функции из $G$ к $(\mathbb Z/p\mathbb Z)^+$. Других нет.