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

[barzel]

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

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

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

Чтобы это сделать можно использовать несколько способов. Дима пишет всё решение на обратной стороне. Петя выбирает строчки, столбцы или блоки. Согласно петяному выбору все нарезается. Потом берется случайный элемент из 9 членов, все это нарезается на отдельные квадратики, тасуется и проверяется, что все 9 чисел имеются в стопке. У Димы нет почти способа обмануть. Кроме того, что Петя не можнт быть уверен в правильном порядке следования чисел.

Есть более изящный способ для Димы доказать Пете, что он знает решение.
Петя кладет на известные поля три одинаковые карты рубашкой вниз, Дима кладет на закрытые поля тоже по три, но только рубашкой вверх. Теперь Петя собирает по случайной карте с каждого столбца, кладет внизу от поля.Тоже делает с каждой строчки. И осташиеся собирает по блокам. Тасует. И должен убедиться, что в любой кучке есть все девять карт. Таким макаром Дима может показать Пете, что он знал решение без раскрытия последнего.

Это один из способов, которым пользуется криптогрфия.

Демонстрация метода