# Collision resistance of hash function built on modular exponentiation

Consider the following hash function family for hashing integers:

$Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$.

$H_{(n,y)}(x) = y^x \bmod n$

My question is this hash function collision resistant if the RSA assumption holds?

• Comments are not for extended discussion; this conversation has been moved to chat. Commented May 11, 2018 at 12:02

# Reduction to RSA

Let $$\mathcal C\colon \mathbb Z \times \mathbb Z \to \mathbb Z \times \mathbb Z$$ be a collision-finding oracle giving $$(x, x') = \mathcal C(n, y)$$ such that $$x \ne x'$$ and $$y^x \equiv y^{x'} \pmod n$$, with some probability $$p$$ given some distribution on RSA moduli $$n$$ and integers $$y$$. For any positive odd $$e$$, define $$\mathcal R_e\colon \mathbb Z \times \mathbb Z \to \mathbb Z$$, a root-finding algorithm giving $$m = \mathcal R_e(n, c)$$ whenever $$\gcd(e, \lambda(n)) = 1$$, which succeeds if $$\mathcal R_e(n, m^e \bmod n) = m$$, as follows:

1. If $$c \in \{0,1\}$$, return $$c$$.
2. If $$\gcd(c, n)$$ is a nontrivial factor of $$n$$, exploit it for ordinary RSA private-key computations and stop here.
3. Compute $$(x, x') = \mathcal C(n, c)$$ with $$x \ne x'$$, $$c^x \equiv c^{x'} \pmod n$$. (If not, fail.)
4. Compute $$\delta = (x - x')/e^i$$ so that $$\gcd(\delta, e) = 1$$. (I.e., divide off all factors of $$e$$.)
5. Compute $$d \equiv e^{-1} \pmod \delta$$ with the extended Euclidean algorithm.
6. Compute and yield $$c^d \bmod n$$.

Why does this work? Let $$c = m^e \bmod n$$. If $$c$$ is neither zero nor a nontrivial factor of $$n$$, then $$c \in (\mathbb Z/n\mathbb Z)^\times$$. Since $$c^x \equiv c^{x'} \pmod n$$, we know $$\operatorname{ord}_n c \mid x - x'$$. Further, since $$\operatorname{ord}_n c \mid \lambda(n)$$ and $$\gcd(e, \lambda(n)) = 1$$, we must have $$\gcd(e, \operatorname{ord}_n c) = 1$$, and thus $$\operatorname{ord}_n c \mid \delta = (x - x')/e^i$$. Now $$\gcd(e, \delta) = 1$$, so that $$e$$ is invertible modulo $$\delta$$, with inverse $$d$$. Since $$ed \equiv 1 \pmod \delta$$, we can conclude $$\operatorname{ord}_n c \mid \delta \mid ed - 1$$, i.e. $$ed \equiv 1 \pmod{\operatorname{ord}_n c}$$. Thus $$c \equiv c^{ed} \equiv (c^d)^e \pmod n$$, and since $$u \mapsto u^e \bmod n$$ is a permutation of $$\mathbb Z/n\mathbb Z$$, $$c^d \equiv m \pmod n$$. (Note that $$d$$ is not the inverse of $$e$$ modulo $$\lambda(n)$$, or even modulo the order of $$m$$: we may need to use a different $$d$$ for each ciphertext $$c$$.)

This root-finding algorithm $$\mathcal R_e$$ succeeds with the same probability as the collision-finding oracle $$\mathcal C$$, and handful of arithmetic: a GCD with $$n$$, a few divisions by $$e$$, an extended Euclidean algorithm, and a modular exponentiation. If the collision-finding oracle works uniformly on all elements of $$\mathbb Z/n\mathbb Z$$, then the root-finding algorithm works uniformly to decrypt all RSA ciphertexts in $$\mathbb Z/n\mathbb Z$$. But if it is restricted to quadratic residues, which appear with probability $$(p + 1)(q + 1)/4pq$$ in a uniform distribution on $$\mathbb Z/n\mathbb Z$$ for $$n = pq$$, then so is the root-finding algorithm.

So it's not clear to me why this is restricted to quadratic residues: the reduction works better if not restricted!

# Reduction to factoring

Let's take a simpler case first.

Suppose for $$n = pq$$ that $$p = 2p' + 1$$ and $$q = 2q' + 1$$ are safe primes, i.e. $$p'$$ and $$q'$$ are prime too. Then $$\lambda(n) = 2p'q'$$ for primes $$p'$$ and $$q'$$ nearly the size of $$p$$ and $$q$$, so the only possible orders modulo $$n = pq$$ are $$\{1,2,p',q',2p',2q',p'q',2p'q'\},$$ and for a quadratic residue $$y$$, the only possible orders of $$y$$ are $$\{1,p',q',p'q'\}.$$ Thus, except for $$1$$, the order of every quadratic residue is either $$p' = (p - 1)/2$$, $$q' = (q - 1)/2$$, or $$p'q' = \lambda(n)/2 = \phi(n)/4$$. A collision $$x \ne x'$$ implies $$\operatorname{ord}_n y \mid x - x'$$. As long as $$(x - x')/\operatorname{ord}_n y$$ is not too large, it is merely a small combinatorial search to factor $$n$$ from there.

But it's still not clear to me why you need the base $$y$$ to be a quadratic residue. The combinatorial search is a little larger, but not much larger, if $$y$$ is an arbitrary element. Indeed, for any modulus, as long as $$y$$ has large enough order, a collision is practically guaranteed to reveal factorization of $$n$$ either directly or via $$\lambda(n)$$. Pick $$y$$ to attain the maximal order $$\lambda(n)$$, and factorization of $$n$$ from a collision $$x \ne x'$$ is even easier because $$\lambda(n) \mid x - x'$$, for any $$p'$$ and $$q'$$ whether prime or not.

Maybe picking maximal-order elements uniformly at random is not trivial in general—but quadratic residues never have maximal order, and when $$p$$ and $$q$$ are safe primes, any uniform random element works except with negligible probability ($$\pm1$$).

# Related constructions

A nearly more general theorem was proven by Pointcheval (Thm. 4, p. 117) for any modulus $$n$$ where the prime factors of $$p'$$ and $$q'$$, and the order of $$y$$, all exceed $$\alpha$$—with the caveat that $$y$$ must be asymmetric, meaning that its order has opposite parity modulo $$p$$ and $$q$$, so it is not quite a generalization. This leaves open the question of what the distribution of the order of $$y$$ or $$y^2$$ is under uniform random $$y \in (\mathbb Z/n\mathbb Z)^\times$$, and whether it is below $$\alpha$$ with negligible probability.

Shamir and Tauman proposed a similar collision-resistant hash function for a base $$y$$ of maximal order modulo a product of safe primes, although it is defined on $$\mathbb Z/n\mathbb Z \times \mathbb Z/\lambda(n)\mathbb Z$$ rather than on $$\mathbb Z/\lambda(n)\mathbb Z$$: specifically, it sends $$(m, r) \mapsto y^{2^{\lceil\lg\lambda(n)\rceil}m + r} \bmod n.$$

But none of these involves quadratic residues, and in two minutes of skimming I couldn't find any relevant literature that does involve quadratic residues, other than the seminal GMR signature scheme (paywall-free link) that works rather differently.

In an answer to an earlier related question on the difficulty of finding high-order elements, poncho concludes that an oracle to compute the order of an arbitrary element $$y$$ modulo $$n$$ is enough to factor $$n$$, by finding a nontrivial square root of unity using the odd part of the order of $$y$$. But there is a gap in applying it here: if the order of $$y$$ is odd, as it must be if (e.g.) $$p$$ and $$q$$ are safe primes and $$y$$ is a quadratic residue, the attack doesn't work, because we cannot necessarily construct such an order-finding oracle from a collision oracle in case the collision oracle always returns $$x$$ and $$x'$$ differing by an odd integer.

(On the other hand: maybe it works to test, for $$i = 0, 1, 2, \dots$$ until you pass $$2^i > n$$, whether $$z^{2^i (x - x')} \not\equiv \pm 1 \pmod n$$ and $$z^{2^{i+1} (x - x')} \equiv 1 \pmod n$$, in which case you have a nontrivial square root of unity so that $$n \mid (z^{2^i (x - x')} + 1)(z^{2^i (x - x')} - 1)$$ from which $$\gcd(n, z^{2^i (x - x')})$$ recovers a nontrivial factor of $$n$$.)

• Uh, I forgot again to ask in advance. Chelsea, any chance you can verify this answer? Otherwise I'll just assign a bounty if an answer gets a good amount of upvotes - or if I can verify correctness myself. Commented May 12, 2018 at 15:37
• @Maarten There is no way I can verify this now. I am not in contact with the person who gave me this. This was posted 6 months back. Commented May 13, 2018 at 4:53
• No problem, it is a good question that just sat there so I decided to offer a bounty. Yeah it's late I hope you got some help from the comment s below the question. Commented May 13, 2018 at 10:27
• @Maarten Yes I have got more than what I expected. Thank you :) Commented May 13, 2018 at 13:49
• A toy example with n=35 , QR=y=11 , r=4 and t=7, ${ y^r = y^t }$
– SSA
Commented Jan 3, 2021 at 6:51