ДОКАЗАТЕЛЬСТВО ПРИНАДЛЕЖНОСТИ ЧИСЛА МНОЖЕСТВУ КВАДРАТИЧНЫХ НЕВЫЧЕТОВ | Протокол QNR | |
Протокол интерактивного доказательства | Протокол доказательства с нулевым разглашением |
Постановка задачи |
Пусть Пусть
Пусть
где По определению считаем, что Пусть |
Описание протокола |
Общий вход: натуральные числа 1) Первый шаг проверяющего. Используя случайные биты,
и
2) Первый шаг доказывающего. 3) Второй шаг проверяющего. Для каждого
а если
4) Второй шаг доказывающего. 5) 6) Проверяющий принимает доказательство, если он завершит |
Основные сведения | |||
|
|
|
|