Are there any homomorphic cryptographic hash functions that satisfy $\text{H(A + B)} = \text{H(A)} + \text{H(B)}$ which maintaining pre-image resistance
$\begingroup$
$\endgroup$
4
-
$\begingroup$ You can easily find a set of inputs whose images are a basis (over the field with two elements) of the range. Write the target hash value as sum of elements of the basis and use that $H$ is homomorphic. $\endgroup$– j.p.Mar 13, 2019 at 7:08
-
$\begingroup$ Realted Are there any practical implementation of a homomorphic hashing or signature scheme? and Are there cryptographic hash functions with homomorphic properties? $\endgroup$– kelalakaMar 13, 2019 at 8:40
-
1$\begingroup$ Maybe you could tell us what you mean with "+"? I thought of bitwise addition (xor), but it could be as well addition in any abelian group or even string concatenation. $\endgroup$– j.p.Mar 15, 2019 at 8:02
-
$\begingroup$ Hey sorry, in any abelian group operation. I don't think any basis over the field with two elements would work :\ $\endgroup$– Math is HardMar 15, 2019 at 18:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Fix a finite group $G$ of order $\ell$, written additively, in which discrete logarithms are difficult. Fix a standard base point $P \in G$ of large prime order. The function $H\colon \mathbb Z/\ell \mathbb Z \to G$ given by $$H(n) := [n]P = \underbrace{P + \cdots + P}_{\text{$n$ times}}$$ is a preimage-resistant homomorphism: $H(n + m) = H(n) + H(m)$, and finding preimages is exactly finding discrete logarithms.
Of course, if $\ell$ is prime, then $H$ is injective and so doesn't compress its input at all; while if $\ell$ is composite, then $H$ is not collision-resistant since $H(n + \operatorname{ord} P) = H(n)$ for all $n$. See the linked answers to address collision resistance.
answered Mar 15, 2019 at 2:25