1
$\begingroup$

Let $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ for $g \in \mathbb{Z}_{p}^{*}$ where $p$ is prime. Is this function (strongly) collision-free meaning we cannot find practically $x_1$,$x_2$ such that $H(x_1)=H(x_2)$?

I argue no with the following reasoning: Let $A$ be an Algorithm which generates $x_1 \neq x_2$ such that $H(x_1)=H(x_2)$ and define $A: \mathbb{N} \rightarrow (X_1,X_2)$ $A: n \mapsto (n,n+(p-1))=(x_1,x_2)$ we find indeed with Fermat's little theorem that $g^{x_2}=g^{n+(p-1)}=g^{n}g^{p-1}=g^{n}=g^{x_1}$

My big fear is here that I confused (weak) collision-free with strong collision free. If anything wrong any hints what to do better.

Improve this question
$\endgroup$
5
  • $\begingroup$ Hint: look again at the input set for $H$. If $p$ is prime (or more generally of known factorization), does that make it possible to exhibit a second preimage? Does that fit the definition of "(strongly) collision-free" that you are using (and should be part of the question BTW)? $\endgroup$
    – fgrieu ♦
    Nov 23, 2021 at 12:54
  • $\begingroup$ I see a mistake lol. No by our definition that we're using it is indeed not (strongly) collision-free. Because we can find such $x_1,x_2$ practically(even within seconds) with $H(x_1)=H(x_2)$ thus not (strongly) collision-free. $\endgroup$
    – Iwan5050
    Nov 23, 2021 at 13:49
  • $\begingroup$ your mapping is an surjective homomorphism, where x and x+p will map to same codomain element. ${x \equiv x+p}$, also the kernel of your mapping is ${<p>}$ i.e., multiples of p. But my question to @fgrieu is, what is p is 2048 bits? is it not good enough? $\endgroup$
    – SSA
    Nov 23, 2021 at 15:37
  • $\begingroup$ @SSA: if prime $p$ is public, then $p$ large is not good enough to make $H$ collision-resistant. In crypto, we consider intelligent adversaries (modeled by algorithms, in theory any algorithm, in practice algorithm designed by humans or AI), and they (adversaries, algorithms) are expected to make use of any public information, including parameters. They are not bound to generating collisions randomly (which would fail for large $p$). $\endgroup$
    – fgrieu ♦
    Nov 23, 2021 at 17:34
  • $\begingroup$ @fgrieu, Chaum-van Heijst-Pfitzmann Hash Function, is a similar to this. it satisfy all 3 properties which a hash function is needed, but not seen being use as it is slow in practice. $\endgroup$
    – SSA
    Nov 24, 2021 at 13:40

1 Answer 1

Reset to default
1
$\begingroup$

No by our definition that we're using it is indeed not (strongly) collison-free. Because with the Algorithm $A$ we've already constructed a very fast way to compute such $x_1,x_2$ with $H(x_1)=H(x_2)$ and virtually by definition this contradicts the condition collision-free.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You should be able to accept this answer in a few days. I will then try to remove that comment. $\endgroup$
    – fgrieu ♦
    Nov 23, 2021 at 17:27
  • $\begingroup$ I'd favor proof by example: "Inputs $a=1$ and $a=p$ of $H$ belong to the definition domain $\mathbb Z$, and by FLT the outputs collide since $p$ is prime" (and perhaps "Such colliding pair can be exhibited by an adversary since $p$ is a public parameter"), followed by "Thus $H$ is not collision-resistant". $\endgroup$
    – fgrieu ♦
    Nov 23, 2021 at 18:08

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.