Криптография и судоку.

Вчера в Тель-Авиве проходил фестиваль науки "наука за барной стойкой". Я из более 40 тем выбрал кафешку на Фришман, 38. В ней лектор говорил про криптографию и судоку. Скажем так, про криптографию я имею общее представление, всякие ключи, защищенные каналы. Тема интересна с учетом развития информационных технологий, объемов передаваемой информации. Постоянно идет вечная война между личной информацией и расширением социальных связей (фэйсбук, одноклассники). Так криптография говорит, что чтобы быть подключенным ко всему миру, не обязательно делиться со всеми личной информацией. Все время криптографические способы совершенствуются. Начиналось все с чего-то элементарного типа Решётки Кардано и вплоть до кватновой криптографии, в которой любое внешнее вмешательство приводит к разрушению картины.

Чтобы объяснение было более-менее наглядно и демонстративно, лектор выбрал отдельную тему, известную под названием Доказательство с нулевым разглашением. Это такое сочетание карт, таблицы судоко, криптографии и ножниц.

Допустим один человек обладает решением судоко(Дима), как он может доказать своему опоненту(Петя), что он рещил кроссворд без того, чтобы показать полностью решение, то есть передав ноль информации?
( Read more... )