Next: The inability to distinguish
Up: Probabilistic Encryption
Previous: Two versions of QRA
QRA talks about the ability to identify squares when only
is known.
In the proposed encryption system, a pseudo-square
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
and tries to
decide if
is a square. Assume
whenever
is a pseudo-square.
Choose
at random, then use the techniques from Section 7.4
to estimate
.
Since half the numbers in
are pseudo-squares,
you will quickly find a
for which
.
Translated from LaTeX by Scott Sutherland
1998-03-15