Заседание Московского математического общества 11 апреля 2006 года

Во вторник, 11 апреля 2006 года, в 18:10 в аудитории 16-24 Главного здания МГУ состоится заседание Московского математического общества: Сложностная криптография: полные криптосистемы с открытым ключом. Лектор – Э. А. Гирш (Санкт-Петербург, совместно с Д. Ю. Григорьевым и К. В. Первышевым).

Многие традиционные для теории сложности понятия отсутствуют в криптографии. В частности, во многих сложностных классах существует «полная задача»: задача, к решению которой сводится решение любой другой задачи из данного класса. Иными словами, полная задача – это «самая трудная» задача из данного класса. До сих пор не было известно криптосистемы с открытым ключом, про которую было бы известно аналогичное утверждение, т.е. криптосистемы, которая была бы «самой трудной для взлома». Хотя подобная односторонняя функция известна с 1980-х годов: Л.А.Левин.

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

Московское математическое общество