Общий вход: $ p$ и $ q$ - простые числа такие, что $ q\vert (p-1)$, $ g\in Z^*_p$ и $ X$ - число.

1) Первый шаг доказывающего. $ P$ выбирает наугад $ r\in Z_q$ и вычисляет $ h\equiv g^r \pmod p$. $ P$ отправляет $ h$ проверяющему.

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

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

4) Второй шаг проверяющего. $ V$ проверяет выполнение условия $ g^k\equiv X^b\cdot h \pmod p$. Если оно не выполняется $ V$ останавливает проверку и отвергает доказательство.

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

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