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?

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi May 11 '18 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$.)

  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes May 12 '18 at 15:37
  • $\begingroup$ @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. $\endgroup$ – chelsea May 13 '18 at 4:53
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes May 13 '18 at 10:27
  • $\begingroup$ @Maarten Yes I have got more than what I expected. Thank you :) $\endgroup$ – chelsea May 13 '18 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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