1
$\begingroup$

I need a lightweight cryptographic hash function which is additive but not reversible, however I'm not sure such a function exists! (it would be better if it works in multisets as well)

By additive I mean: given such function f, another function g must exist, having the property g(f(X),f(Y))=f(X||Y), where || denotes concatenation of strings X and Y.

I have found a homomorphic hash function from facebook which is additive but it is reversible too.


EDIT:

By non-reversible, I'm not referring to pre-image resistance even tho I want to have that property in the overall function.

non-reversiblility: If we know f(X||Y) and that Y is an element used as the input, it would impossible to compute g-1(f(X||Y),f(Y)) to get the f(X)

PS. I'm trying to find a solution which is quantum resistant and lightweight enough to work in IoT devices

$\endgroup$
6
  • $\begingroup$ You might want to add what other properties you need; for additive and nonreversible, we have the function $f(x) = 0$ and $g(0, 0) = 0$; that satisfies both requirements, but I doubt it would be useful for your usecase (whatever that is). Somewhat less trivial ones can be derived by xor'ing the bytes of the input string together... $\endgroup$
    – poncho
    May 4, 2022 at 12:55
  • $\begingroup$ @poncho you are right! I meant cryptographic one $\endgroup$ May 6, 2022 at 13:28
  • $\begingroup$ By cryptographic, do you mean preimage resistant (baro77's answer does that), second preimage resistant or collision resistant? $\endgroup$
    – poncho
    May 6, 2022 at 13:32
  • $\begingroup$ If you do need second preimage or collision resistance, see my comment to baro77 which explores an idea (which needs to be fleshed out...) $\endgroup$
    – poncho
    May 6, 2022 at 14:22
  • $\begingroup$ @poncho I'm reading your helpful comments! And updated the question properly. Thank you both :) $\endgroup$ May 6, 2022 at 14:25

1 Answer 1

2
$\begingroup$

I'm in hurry now, but I want to share with you some ideas (which if needed I'll detail next days):

  • concatenation can be seen as $x||y = xk+y$ where $k=2^{|y|}$
  • so $f(x||y) = f(xk+y)$
  • if we assume $f$ being the multiplication for an EC generator $G$ (the common EC privkey/pubkey setting) we obtain:

$f(x) = Gx$

$f(y) = Gy$

$f(x||y) = G(xk+y) = G(xk) + Gy = G(x+x+...+x) + Gy = (Gx + Gx + ... + Gx) + Gy = kGx + Gy$

  • the last passage gives you $g$ (a relation symbolically equal to concatenation but now acting on EC points)

$f(x) = Gx$ of course isn't an hash, but it's not invertible (it's the common discrete logarithm problem), and with foregoing definitions it seems (if I'm not wrong) additive as you requested


EDIT: GENERALIZATION

As carefully pointed out by @poncho, the previous ideas work only when all $y$ have a fixed pre-known size, 'cause this guarantees that $k$ is constant and can be used in $g$ (which doesn't have "directly visibility" of $y$ to calculate its size). The clever workaround suggested by @poncho is to let $f$ pass its input size to "the next stage". So previous definitions are generalized in this way:

  • $x||y = xk+y$ where $k=2^{|y|}$ whichever the size of $y$ is
  • $f(x) = (Gx, |x|) = (X, |x|)$
  • $f(x||y) = f(xk+y) = (kX+Y,|x|+|y|) = (2^{|y|}X+Y,|x|+|y|)$
  • $g((X,s_x),(Y,s_y)) = (2^{s_y}X+Y, s_x+s_y)$

Still $f$ is not an hash but as previously said it's additive in your flavour and not invertible (first preimage resistant in hashes terminology).

$\endgroup$
7
  • 1
    $\begingroup$ One issue with this is how $g$ works depends on the length of $y$. Now, that can be addressed by including the length of the hashed string in the output of $f$, that is $f(x) = (xG, |x|)... $\endgroup$
    – poncho
    May 4, 2022 at 17:41
  • $\begingroup$ @poncho you are definitely right, in my mind I was thinking to strings length to be fixed and pre-known $\endgroup$
    – baro77
    May 4, 2022 at 17:45
  • 1
    $\begingroup$ "inclusion of the input size in its output also avoids second preimage and collision attacks"; nope (except for second preimage attacks on short inputs); the addition of the order of the generator will not change the point multiplication; if this addition doesn't change the length (because the value being hashed is already longer than the length, and the addition doesn't cause an 'overflow'), then the hash result will be the same. $\endgroup$
    – poncho
    May 6, 2022 at 13:31
  • $\begingroup$ On the other hand, if the OP needs second preimage or collision resistance, you can use the same idea, but instead of using an EC group, do it over a multiplicative ring modulo a composite of secret factorization ("an RSA modulus"); there, second preimage/collision is provably as secure as factoring (assuming a well-chosen generator, and with the caveat that there is a backdoor for someone who knows the factorization) $\endgroup$
    – poncho
    May 6, 2022 at 13:36
  • 1
    $\begingroup$ Actually, if $x > l$, then it is possible that $|x| = |x +l|$ $\endgroup$
    – poncho
    May 6, 2022 at 13:54

Your Answer

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

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