Общий вход: $ p$ и $ q$ - простые числа такие, что $ q\vert p-1$, $ p\geq 2^{512}$, $ q\geq 2^{140}$, $ g \in Z_n$, порядок по модулю $ p$ которого равен $ q$, $ y=g^{-z} \pmod p$ для некоторого $ z\in Z_q$.

1) Первый шаг доказывающего. $ P$ выбирает случайным образом $ k \in_U Z_n$ и вычисляет число $ c = g^k \pmod p$. $ P$ отправляет $ c$ проверяющему.

2) Первый шаг проверяющего. $ V$ выбирает наугад $ b\in \{0,1\}$ и отправляет его доказывающему.

3) Второй шаг доказывающего. $ P$ получает $ b$. $ P$ вычисляет $ r = k+zb\pmod p$ и отправляет его проверяющему.

4) Второй шаг проверяющего. $ V$ проверяет выполнение условия $ c=g^r y^b$. Если оно не выполняется, $ V$ останавливает проверку и отвергает доказательство.

5) $ P$ и $ V$ повторяют шаги 1) - 4) $ log_2 log_2 p$ раз.

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