Один из результатов, который упоминали на церемонии вручения премии Абеля — это Zero Knowledge Proof, доказательство с нулевым разглашением. И это действительно очень красивая идея (восходящая к работе Goldreich-Micali-Rackoff, "The Knowledge Complexity of Interactive Proof-Systems").

Как мне это когда-то рассказывали — вот представьте себе, что математик X доказал гипотезу Римана. Естественно было бы написать статью или рассказать результат на семинаре — но X опасается, что его результат украдут. Может ли X убедить коллег, что у него действительно есть доказательство — не рассказав его? И оказывается, что да, есть способ это сделать — о доказательстве вообще ничего не рассказав, кроме его длины. (Можно считать, что X потрясает пачкой бумаги со словами, "этого хватит, чтобы доказательство записать".)

Более того, — это возможно для вообще любой NP-задачи. И вот тут алгоритм придумали Oded Goldreich, Silvio Micali и Avi Wigderson: см. "How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design" (1986; https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_11.pdf )

В двух словах (я уточню ближе к концу этого рассказа) — нас интересуют ситуации, когда уже предъявленный ответ можно быстро проверить, но вот сам поиск этого ответа, возможно, безумно сложен. Например, если Вася хочет доказать, что он знает гамильтонов (посещающего каждую вершину ровно один раз) путь в графе. Как раз — проверить, что путь по 1000 вершин графа действительно проходит через каждую вершину, ровно один раз, и каждый раз переходит по ребру — легко. А вот найти такой путь (если он есть) для заданного графа — слоожно...

Тот пример, из которого всё выводится в работе Goldreich, Micali, Wigderson — это задача трёхцветной раскраски: раскрасить вершины графа в 3 цвета так, чтобы соседние вершины были бы раскрашены в разные цвета.
(Кстати: если граф планарный, то в четыре цвета его вершины правильным образом раскрасить всегда можно — и это и утверждает теорема о четырёх красках.)

Понятно, что это задача как раз такого класса: найти раскраску может быть очень сложно — но вот когда раскраска уже предъявлена, проверить, что это действительно правильная раскраска, занимает вполне разумное время.

Так вот — допустим, что X знает правильную трёхцветную раскраску данного графа. Как ему убедить в этом Y, не раскрывая никакой информации?