next up previous contents
Next: The inability to distinguish Up: Probabilistic Encryption Previous: Two versions of QRA   Contents

Knowing a pseudo-square does not help much

QRA talks about the ability to identify squares when only $n$ is known. In the proposed encryption system, a pseudo-square $y$ is also announced. The paper shows (p. 295) that this does not make the problem easier.

Suppose we have an algorithm which takes as input $a,y$ and tries to decide if $a$ is a square. Assume $p_Z=.55$ whenever $y$ is a pseudo-square. Choose $y\in Z^1_n$ at random, then use the techniques from Section 7.4 to estimate $p_Z$. Since half the numbers in $Z^1_n$ are pseudo-squares, you will quickly find a $y$ for which $p_Z=.55$.

Translated from LaTeX by Scott Sutherland