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?
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:
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!
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$).
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$.)
