2023/2024
Односторонние функции и их применения
Статус:
Маго-лего
Когда читается:
1, 2 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
6
Контактные часы:
56
Программа дисциплины
Аннотация
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону,
по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел,
схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.
Необходимы предварительные знания: знакомство с основными вычислительными
моделями: машинами Тьюринга, вероятностными машинами Тьюринга
и схемами из функциональных элементов.