Общий вход: $ p$ и $ q$ - простые числа, $ y, g_1 , g_2 , ..., g_k \in G_q$.

1) Первый шаг доказывающего. $ P$ выбирает наугад $ r_1, r_2, ..., r_n \in Z_q$ и вычисляет $ h\equiv g_1^{r_1}\cdot g_2^{r_2}\cdot ... g_n^{r_n} \pmod p$. $ P$ отправляет $ h$ проверяющему.

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

3) Второй шаг доказывающего. $ P$ вычисляет $ k_i \equiv r_{i}+\alpha_{i} b \pmod q$ $ i=1,2,...,n$ и отправляет его проверяющему.

4) Второй шаг проверяющего. $ V$ проверяет выполнение условия $ g_1^{k_1}\cdot g_2^{k_2}\cdot ... \cdot g_n^{k_n}\equiv y^b\cdot h \pmod p$. Если оно не выполняется $ V$ останавливает проверку и отвергает доказательство.

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

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