2
$\begingroup$

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)?
Improve this question
$\endgroup$
3
  • $\begingroup$ 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.. $\endgroup$
    – Thomas
    Commented Jul 3, 2013 at 16:10
  • $\begingroup$ you are right, i made a mistake, all of the boave modulos are mod N, N is a composite $\endgroup$
    – user4478
    Commented Jul 3, 2013 at 16:28
  • $\begingroup$ 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$. $\endgroup$
    – xagawa
    Commented Jul 3, 2013 at 22:51

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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