Заседание Московского математического общества 11/04/2006
Докладчик: Е. А. Гирш (СПб.; совместно с Д. Ю. Григорьевым и К. В. Первышевым)
Тема доклада: СЛОЖНОСТНАЯ КРИПТОГРАФИЯ: ПОЛНЫЕ КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ
Многие традиционные для теории сложности понятия отсутствуют в криптографии. В частности, во многих сложностных классах существует “полная задача”: задача, к решению которой сводится решение любой другой задачи из данного класса. Иными словами, полная задача – это “самая трудная” задача из данного класса. До сих пор не было известно криптосистемы с открытым ключом, про которую было бы известно аналогичное утверждение, т. е. криптосистемы, которая была бы “самой трудной для взлома”. (Хотя подобная односторонняя функция известна с 1980-х годов: Л. А. Левин). В докладе будет сконструирована полная криптосистема в классе криптосистем с открытым ключом, допускающих с небольшой вероятностью ошибку раскодирования. Для понимания доклада специальных знаний не требуется.
