Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)?
share|improve this question
    
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.. –  Thomas 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 –  user4478 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$. –  xagawa Jul 3 '13 at 22:51
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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