|
|
Заседания Московского математического общества
11 апреля 2006 г., г. Москва, ГЗ МГУ, аудитория 16-10
|
|
|
|
|
|
Сложностная криптография: полные криптосистемы с открытым ключом
Э. А. Гирш, Д. Ю. Григорьев, К. В. Первышев |
Количество просмотров: |
Эта страница: | 239 |
Фотогалерея
|
Аннотация:
Многие традиционные для теории сложности понятия отсутствуют в криптографии. В частности, во многих сложностных классах существует «полная задача»: задача, к решению которой сводится решение любой другой задачи из данного класса. Иными словами, полная задача — это «самая трудная» задача из данного класса. До сих пор не было известно криптосистемы с открытым ключом, про которую было бы известно аналогичное утверждение, т.е. криптосистемы, которая была бы «самой трудной для взлома». (Хотя подобная односторонняя функция известна с 1980-х годов: Л. А. Левин.)
В докладе будет сконструирована полная криптосистема в классе криптосистем с открытым ключом, допускающих с небольшой вероятностью ошибку раскодирования.
Для понимания доклада специальных знаний не требуется.
|
|