Отсюда я читаю доказательства и наткнулся на техническую (хотя и крайне важную) проблему. Я знаю, что это довольно специфично, и контекст проблематичен, но я не мог понять это сам.
На страницах 51 и 55 после представления «стандартных» верификаторов они поворачиваются, чтобы модифицировать верификаторы для проверки разделенных назначений.
В первом случае (стр. 51) они проверяют, что являются близкими к полиномиальному коду, а затем они используют алгебраизацию (+ тестеры нулей) для построения семейства полиномов (с суммой -Check свойство , относящееся к входной формуле) , что каждый из них может быть оценен в точке , заданной 3 значение каждого из (кодовые слова полинома кода к шкафу ).
Во втором случае (стр. 55) они проверяют , что в -близких к линейной, а затем они определяют функцию , чтобы быть специальной суммой таким что может быть оценена в точке , заданной величины каждого из (линейные функции шкафу ).
Тогда в обоих случаях они выполняют тесты (Sum-Check или Tensor + Адамара) на значения случайного полинома в семье / .
Моя проблема заключается в том , что процедура восстановления требуемых значений каждого из могу предоставить неправильные значения с некоторым пренебрежимо малой вероятностью постоянной . Более того, вероятность того, что все значения восстановлены правильно, очень мала, только для некоторой константы . И это верно для обоих случаев.
Это может быть плохо, так как некоторые из этапов верификаторов требуют получения значений целевой функции / многочлена из семейства whp
Это проблема, или я что-то упустил (что я, вероятно, я)?
источник
Ответы:
источник