https://t.me/turings_crossword/520
екция Льва Суханова в это воскресенье, 22 октября, в 17:00

Лев Суханов - выпускник матфака ВШЭ и исследователь в PSE, Ethereum Foundation. Он расскажет про очень важную область криптографии, в которой он работает - быстрые проверки доказательств.

???? Верифицируемые вычисления при помощи sumcheck-протокола

???? Давайте рассмотрим следующую ситуацию: Алиса посчитала на известных публичных данных X функцию f(X), и хочет убедить Боба в том, что ответ, который она говорит - правильный. Боб, однако, ограничен в вычислительных ресурсах, и не хочет повторять всё вычисление Алисы.

Выясняется, что (при условии что Боб допускает небольшую вероятность ошибки, скажем $2^{-128}$), такую задачу можно решить намного быстрее. Такую постановку вопроса называют "interactive proof of knowledge".

Я расскажу про довольно старый протокол из 90х - sumcheck (проверка суммы), в последние год-два получивший второе дыхание в контексте делегированных вычислений и блокчейна, и построенный на этом аргументе протокол GKR (Голдвассер-Калаи-Ротблюма).

Пререквизиты: знать что такое конечное поле и уметь раскрывать скобки, если дойдём до приложений то ещё понадобится (наверное) знать что такое хэш