# constructing QR-like one way function

I am wondering whether the following form is a one way function with collision resistance: $$ax^2+by^2 \mod p$$ where $a$ and $b$ are given, and $p$ is a prime number.

Since the QR (quadratic residue) $x^2 \mod p$ is one way, $ax^2 \mod p$ is also one way. The same goes for $by^2$.

So, my guess is that the form $ax^2+by^2 \mod p$ is one way. Is that correct?

A few more follow-up questions:

1. How to formalize a proof that a numeric equation is one way?
2. Does anyone know an archive collecting all of known one way functions?
3. If $ax^2+by^2 \mod p$ is not one way, how about $a^2x+b^2y \mod p$?
4. What is instead of a prime $p$ we have a composite number (possibly with certain assumptions on its factorization)?
• I think you made a mistake, $x^2 \mod p$ is not (generally) one-way, there are efficient algorithms to take modular square roots modulo prime numbers (it's much harder for composites, though). Did you mean $a^{\frac{p - 1}{2}} = \binom{a}{p}$ which then obviously lacks collision resistance.. Jul 3 '13 at 16:10
• you are right, i made a mistake, all of the boave modulos are mod N, N is a composite Jul 3 '13 at 16:28
• Take care. As the special case, we can consider $x^2+hy^2 \bmod{n}$. The Ong-Schnorr-Shamir signature is based on $x^2+hy^2 \equiv m \pmod{n}$. Pollad and Schnorr cryptanalyzed this scheme without factoring $n$. Jul 3 '13 at 22:51

From your comment, I replace $p$ with a composite $n$. The answer is no.
The problem is determining whether $f(x,y) = a x^2 + b y^2 \bmod{n}$ is one-way or not. We want to find $(x',y')$ such that $f(x',y') = z$, given $a, b, n$ and $z = a x^2 + b y^2 \bmod{n}$.
Let us consdier $f'(x,y) = x^2 + h y^2 \bmod{n}$, where $h = b a^{-1} \bmod{n}$. The problem is now finding $(x',y')$ satisfying $f'(x',y') = m$, given $m = z a^{-1} \bmod{n}$, $h = b a^{-1} \bmod{n}$, and $n$.
The problem is a basis of the Ong-Schnorr-Shamir signature (STOC 1984, CRYPTO 1984). We already know that Pollad and Schnorr (1987) cryptanalyzed this scheme without factoring $n$. The algorithm and example is available in a short note written by Jeffrey Shallit.