Общий вход: натуральные числа $ n$ и $ x$ в двоичном представлении, $ x \in Z_n^*$ $ \left(\frac{x}{n} \right)=1 $, $ \vert x\vert=m$, $ m=log_2 n$

1) Первый шаг проверяющего. Используя случайные биты, $ V$ выбирает наугад $ r_0 \in Z_n^*$ и бит $ \alpha \in {\{0,1\}}$. Если $ \alpha=0$, то $ V$ задает $ w\equiv r_0^2\pmod m$, если же $ \alpha=0$, то $ V$ задает $ w\equiv x\cdot r_0^2\pmod m$. $ V$ отправляет $ w$ доказывающему. Затем $ V$ выбирает два случайных множества, каждое мощности $ m$

$\displaystyle T=\{t_i \vert t_i\equiv r_i^2 \pmod n,\; i=1,...,m\}$

и

$\displaystyle S=\{t_i \vert t_i\equiv x\cdot r_i^2 \pmod n,\; i=1,...,m\}.$

$ V$ отправляет доказывающему $ P$ элементы множества $ T\cup S$ в случайном порядке.

2) Первый шаг доказывающего. $ P$ выбирает случайное подмножество $ Z \subseteq T\cup S$ мощности $ m$ и отправляет его обратно проверяющему.

3) Второй шаг проверяющего. Для каждого $ z \in Z$ $ V$ отправляет доказывающему $ P$ $ r$ такой, что $ z\equiv r^2\pmod n$ или $ z\equiv x\cdot r^2\pmod n$. Пусть разность мощностей множеств $ T-Z$ и $ S-Z$ равна $ d$. Тогда $ V$ выбирает $ d$ случайных элементов $ t_{i_1},...,t_{i_d}$ из большего множества и отправляет их соответствующих $ r_{i_1},...,r_{i_d}$ доказывающему $ P$ (т.е. $ t_{i_j}\equiv r_{i_j}^2 \pmod n$ или $ t_{i_j}\equiv x\cdot r_{i_j}^2 \pmod n$ для некоторых $ 1\leq i_j \leq 2n$). $ V$ задает $ X=T-Z-\{t_{i_1},...,t_{i_d}\}$ и $ Y=S-Z-\{t_{i_1},...,t_{i_d}\}$. Если $ w\equiv r_0^2\pmod n$ $ V$ полагает

$\displaystyle X'=\{r_0\cdot r_i\equiv \sqrt{w\cdot t_i} \pmod m\vert t_i \in X\},$

$\displaystyle Y'=\{x\cdot r_0\cdot r_i\equiv \sqrt{x\cdot w\cdot t_i} \pmod m\vert t_i \in Y\},$

а если $ w\equiv x\cdot r_0^2\pmod n$, то $ V$ полагает

$\displaystyle X'=\{x\cdot r_0\cdot r_i\equiv \sqrt{x\cdot w\cdot t_i} \pmod m\vert t_i \in X\},$

$\displaystyle Y'=\{x\cdot r_0\cdot r_i\equiv \sqrt{w\cdot t_i} \pmod m\vert t_i \in Y\}.$

$ V$ отправляет элементы множества $ X' \cup Y'$ в случайном порядке.

4) Второй шаг доказывающего. $ P$ проверяет, что $ X' \cup Y'$ такого вида как в 3) (т.е. для всех $ v \in X' \cup Y'$ $ v^2\equiv t_i\cdot w \pmod n$ или $ v^2\equiv t_i\cdot w\cdot x \pmod n$ для некоторого $ t_i \in X\cup Y$) и что $ \vert X' \cup Y'\vert > \dfrac{n}{3}$. Если это не так, то $ P$ останавливается, обнаруживая обман. В противном случае, $ P$ отправляет $ V$ значение $ \beta=Q_n(w)$.

5) $ V$ проверяет значение $ \beta=Q_n(w)$. Если $ \beta\neq\alpha$, то останавливается, обнаруживая обман.

6) $ P$ и $ V$ повторяют шаги 1) - 5) $ \geq m$ раз.

Проверяющий принимает доказательство, если он завершит $ \geq m$ итераций шагов 1) - 5). В противном случае, отвергает.