1
$\begingroup$

Are there any homomorphic cryptographic hash functions that satisfy $\text{H(A + B)} = \text{H(A)} + \text{H(B)}$ which maintaining pre-image resistance

$\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
  • 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$ Mar 15, 2019 at 18:42

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.