Is $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ with $p$ prime (strongly) collision-free?

Iwan5050

3/23/23, 11:00 AM

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.

0 + 0

hash

discrete-logarithm

collision-resistance

fgrieu

3/23/23, 12:54 PM

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)?

Iwan5050

3/23/23, 1:49 PM

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.

SSA

3/23/23, 3:37 PM

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?

fgrieu

3/23/23, 5:34 PM

@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$).

SSA

3/24/23, 1:40 PM

@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.

Score:1

Crypto

Iwan5050

3/23/23, 3:46 PM

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.

0 + 0

fgrieu

3/23/23, 5:27 PM

You should be able to accept this answer in a few days. I will then try to remove that comment.

fgrieu

3/23/23, 6:08 PM

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".

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ with $p$ prime (strongly) collision-free?

TH: $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ และ $a \mapsto g^a\bmod p$ กับ $p$ ไพรม์ (อย่างยิ่ง) ปราศจากการชนกันหรือไม่

RO: Este $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ și $a \mapsto g^a\bmod p$ cu $p$ prim (puternic) fără coliziuni?

RU: Является ли $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ и $a \mapsto g^a\bmod p$ с $p$ простым (сильно) свободным от коллизий?

VI: $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ và $a \mapsto g^a\bmod p$ với $p$ nguyên tố (rất mạnh) không bị va chạm?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.