The inability to distinguish two plaintexts

Theorem 5.1 of the paper addresses the issue we mentioned at the beginning of section 7. It shows that if we have an algorithm which can identify messages $m_1$ and $m_2$ and efficiently tell the difference between an encryption of $m_1$ and an encryption of $m_2$, then we could construct an algorithm which efficiently distinguishes squares from pseudo-squares. Thus (QRA) implies we cannot tell the difference between $m_1$ and $m_2$.

Proof:¹¹ Suppose we are trying to decide whether $a\in Z^1_n$ is a square and that the two distinguishable messages are

$$\begin{eqnarray*}m_1&=&01001011\ m_2&=&11101101 \end{eqnarray*}$$

Choose 8 $x_i$ randomly and consider the sequences

$$\vbox{\halign{&\hfil\quad$ ...$$

If $a$ is a pseudo-square, these will be randomly chosen encodings of $m_1$ and $m_2$. In this case, the performance of our assumed algorithm on the two sequences (averaged over repeated random choices of $x_i$) will be different. If $a$ is a square, both sequences will be randomly chosen encodings of the message consisting of all 0's, so the algorithm's response on average to the two sequences will be identical.

Footnotes

...Proof:¹¹

The argument we give is a simplification of the one in the paper, in that we do not use the ``sampling walk.'' The more complicated argument seems to be necessary to analyze encryption systems in general, as opposed to those based on squares and pseudo-squares.