Тезисы докладов

Математическая кибернетика

Предлагается подход к построению нового класса криптосистем. Условно говоря предлагаемые криптосистемы можно отнести к "практичным" в противовес "непрактичным" (термин К.Э. Шеннона, примененный им по отношению к некоторым криптосистемам и, в частности, к криптосистеме Вернама). В предложенном примере криптосистемы по секретному каналу передается малое количество информации (секретный ключ), но многократное использование этой информации позволяет передать по открытому каналу экспоненциально больший объем информации, при этом каждая переданная криптограмма с вероятностью сколь угодно мало отличающейся от 1 остается совершенно секретной (в смысле Шеннона).

Собственно криптосистема с секретным ключом может рассматриваться как бескоалиционная игра двух игроков (отправителя и криптоаналитика): отправитель формирует некоторую информацию (открытый текст), над которой осуществляется шифрующее преобразование, переводящее ее в криптограмму, криптограмма делается доступной для криптоаналитика. Задача криптоаналитика состоит в нахождении открытого текста.

Базовыми элементами предлагаемого подходя являются т.н. вырожденные задачи. В качестве наиболее распространенного примера вырожденной задачи можно рассмотреть задачу поиска фиксированного (отправителем) решения системы линейных уравнений с вырожденной матрицей над (вообще говоря, произвольным) полем. В качестве иллюстративного случая рассматривается поле вещественных чисел (континуальный случай). Из практических соображений наиболее удобным оказывается поле {0,1}. В этом случае объекты криптосистемы - булевские векторы и матрицы. Если в континуальном случае имеет место классическая совершенная секретность в шенноновском смысле (точнее имеет место самый ее сильный вариант, когда вероятность успеха криптоаналитика, как при известной криптограмме, так и без нее - нулевая), то в "булевском" случае получается "почти совершенная секретность" с точностью до вероятности, отличной от единицы на произвольную наперед заданную малую константу.

Предлагаемый подход дает еще одно полезное следствие: возможно определить эффективность криптосистем с секретным ключом использую установившиеся понятия теории вычислительной сложности: если криптосистема позволяет при ключе длины n отправлять секретный текст длины exp(сn), где с - фиксированная константа из ]0,1[ и при этом каждая криптограмма остается "почти" совершенно секретной (в указанном выше смысле), то такую криптосистему можно считать эффективной.

Дополнительные материалы:

HTML

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии

[Головная страница] [Конференции] [СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации 06-Jul-2012 (11:45:21)