Общий вход: $ p$ и $ q$ - простые числа, $ y^{(j)}, g_1^{(j)} , g_2^{(j)} , ..., g_k^{(j)} \in G_q$ для некоторых $ j$.

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

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

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

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

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

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