Общий вход: Граф $ G=(V,E)$. Пусть $ n=\vert V \vert$ и $ V=\{N_1,N_2,...,N_n\}$.

Дополнительный вход доказывающего: Гамильтонов цикл графа $ G$.

1) Первый шаг доказывающего. Доказывающий шифрует граф $ G$ с помощью ящиков. Для этого он наугад инъективно отображает $ n$ маркированных вершин в $ n$ маркированных ящиков $ B_1$, $ B_2$, ..., $ B_n$ таким образом, что каждая из $ n!$ перестановок вершин в ящики равновероятна. Для каждой пары ящиков $ (B_i,B_j)$ подготавливает ящик $ B_{i,j}$. Этот ящик должен содержать $ 1$, если вершина, содержащаяся в ящике $ B_i$, смежна с вершиной, содержащейся в ящике $ B_j$, и 0 в противном случае. Затем все $ n+ {n\choose 2}$ ящиков запирает и отправляет проверяющему.

2) Первый шаг проверяющего. Проверяющий получает $ n+ {n\choose 2}$ маркированных ящиков. Теперь ему предоставлен выбор:

(1) Если он пожелает, доказывающий откроет все ящики. В этом случае проверяющий может проверить, что ящики содержат описание графа $ G$. (Например, если вершина $ N_1$ смежна с вершиной $ N_2$ и с вершиной $ N_5$, но но не смежна ни с какими другими вершинами графа $ G$, и вершина $ N_1$ содержится в ящике $ B_i$, $ N_2$ вершина в ящике $ B_j$, $ N_5$ вершина в ящике $ B_k$, то $ 1$ должна содержаться в ящиках $ B_{i,j}$ и $ B_{i,k}$, и 0 в ящике $ B_{i,x}$ для любого другого значения $ x$).

(2) С другой стороны, если проверяющий пожелает, доказывающий откроет в точности $ n$ ящиков $ B_{i,j}$, $ B_{j,k}$, $ B_{k,l}$, ..., $ B_{l',i}$, которые содержат гамильтонов цикл графа $ G$, и показать, что они все содержат $ 1$. Это доказывает существование гамильтонова цикла (в любом графе, представленном в ящиках). Так как $ B_i$ не открыты, последовательность вершин, определяющих гамильтонов цикл в графе $ G$ не раскрывается.

Проверяющий наугад выбирает один из этих 2 вариантов (граф или гамильтонов цикл), и таким образом, оба варианта равновероятны.

3) Второй шаг доказывающего. Доказывающий открывает соответствующие ящики.

Шаги 1)-3) повторяются $ k$ раз.

4) Заключительный шаг проверяющего. Проверяющий принимает доказательство, если доказывающий выполняет и в каждом случае правильно демонстрирует либо запрашиваемый граф $ G$, либо запрашиваемый гамильтонов цикл. В противном случае, отвергает.