Мини-курс Андрея Ромащенко "Разделение секрета: теоретико-информационные и сложностные подходы"
С 03 апреля по 08 апреля 2019 года Андрей Ромащенко прочтет мини-курс "Разделение секрета: теоретико-информационные и сложностные подходы".
Видео лекций 1, 2
Место проведения: Факультет компьютерных наук, Кочновский проезд, 3.
Язык мини-курса: русский
Расписание мини-курса:
03 апреля, 12:10-15:00, ауд. 505
08 апреля, 12:10-15:00, ауд. 503
Приглашаются все желающие.
Заказ пропуска: dchernyshova@hse.ru
Аннотация:
Схемой разделения секрета (secret sharing) называют процедуру, которая позволяет распределить между участниками протокола "доли" секрета таким образом, что только заранее определенные авторизованные группы участников могут восстановить весь секрет. При этом неавторизованные группы участников не получают никакой информации о секрете. Разделение секрета является одним из классических инструментов в криптографии; его используют в качестве примитива (базового строительного блока) во многих более сложных криптографических протоколах.
В этом курсе мы опишем несколько важных типов схем разделения секрета и рассмотрим связь данной задачи с шенноновской теорией информации, матроидами, монотонными булевыми формулами и span programs.
Для многих вариантов задачи о разделении секрета зазор между известными верхними и нижними оценками для оптимального размера долей секрета остается экспоненциальным. Мы обсудим наилучшие известные нижние оценки для схем разделения секрета общего вида, а также для линейных схем. Мы также поговорим о связи эффективного разделения секрета с гипотезой NP=coNP.