Протокол Голдвассер-Сипсера для оценки размера множества

Определение

Рассмотрим множество [math]S \subseteq \left\{ 0, 1 \right\} ^m[/math], для которого существует сертификат проверки на принадлежность. Протоколом Голдвассера-Сипсера является двухуровневый интерактивный протокол, в котором [math]V[/math] старается принять множество [math]S[/math], если [math]|S| \ge K[/math], и отвергнуть, если [math]|S| \le \frac{K}{2}[/math].

Протокол устроен следующим образом:

Выберем [math]k[/math] так, чтобы [math]2^{k - 2} \le K \le 2^{k - 1}[/math].

[math]V:[/math] Отправляет [math]P[/math], случайным образом выбиранные [math]h : \left\{ 0, 1 \right\} ^ m \rightarrow \left\{ 0, 1 \right\} ^ k[/math] из семейства универсальных попарно независимых хеш-функций [math]H_{m, k}[/math] и [math]y[/math] из [math]\left\{ 0, 1 \right\} ^ k[/math].

[math]P:[/math] Пытается [math]x \in S[/math], такой что [math]h(x) = y[/math]. Отправляет [math]V[/math] найденный [math]x[/math] и сертификат [math]c[/math] принадлежности [math]x[/math] множеству [math]S[/math].

[math]V:[/math] Если верно, что [math]x \in S[/math] и [math]h(x) = y[/math], то множество [math]S[/math] принимается. В противном случае [math]V[/math] отвергает множество [math]S[/math].

Источники

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach