Изменения
→Доказательство
Мы умеем определять, верно ли, что <tex>s \in S</tex>.
Выберем <tex>k</tex> так, чтобы <tex>2^{k-2} \le 2K \le 2^{k-1}</tex>.
Далее, <tex>h \in H_{m,k}</tex>; <tex>y \in 2^k</tex>. Отправляем запрос <tex>P</tex> на получение <tex>s \ in S</tex>: <tex>h(s) = y</tex>, и проверяем, верно ли в действительности, что <tex>s \ in S</tex>.
