Сложностная криптография: полные криптосистемы с открытым ключом

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