Регистрация Войти
Рейтинг:2
Sheldon avatar Crypto

Что означает верификатор "ppt"? и зачем нам нужен верификатор ppt в Interactive Proof?

флаг nl
Sheldon

Я изучал доказательство с нулевым разглашением. Я обнаружил, что в определении интерактивного доказательства говорится, что Verifier — это ppt. И я нашел только в PP (сложность) Wikipedia Говорит, что пп:

Полиномиально связанные и вероятностные машины Тьюринга характеризуется как РРТ, что означает вероятностное полиномиальное время машины.[2] Эта характеристика машин Тьюринга не требует ограниченная вероятность ошибки. Следовательно, PP — это класс сложности содержащий все задачи, решаемые РРТ машина с ошибкой вероятность меньше 1/2.

Все еще очень запутанно о PPT, каково полное название PPT? нам нужно, чтобы верификатор был PPT для интерактивного доказательства?

Ресурс из: Доказательства с нулевым разглашением CS276: криптография, Калифорнийский университет в Беркли

54
0 + 0
Рейтинг:2
avatar Crypto
флаг et
user93353

PPT — вероятностный полиномиальный алгоритм времени.

Детерминированный верификатор всегда будет давать один и тот же вывод/ответ для любого ввода.

Возьмем интерактивную последовательность.

Доказывающий отправляет $p_1$.

Верификатор отвечает $f(p_1) = v_1$

Доказывающий отвечает $г(v_1) = p_2$

Функция $ф$ который использует верификатор, является детерминированным. то есть для определенного ввода он всегда отвечает одним и тем же ответом.

В вероятностном верификаторе $ф$ также имеет рандомизацию в качестве входных данных. то есть $г$ принимает 2 входа $f(v_i,r)$ куда $г$ является случайным значением. Следовательно $ф$ не является детерминированным, а верификатор является вероятностным верификатором. И если $ф$ работает за полиномиальное время, верификатор является верификатором вероятностного полиномиального времени (PPT).

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.