Д. Соколов (АФТУ)
Криптографическая стойкость функции Голдрейха

Функция Голдрейха - кандидат в односторонние функции. В докладе будут рассмотрены нижние оценки на время обращения функции Голдрейха при помощи подкласса DPLL алгоритмов - "пьяных" алгоритмов. Будет доказана нижняя экспоненциальная оценка на время работы любого DPLL алгоритма на невыполнимой булевой формуле, полученной по функции Голдрейха, а также показано, что после некоторого числа шагов "пьяного" алгоритма с большой вероятностью формула станет невыполнимой.
Также в докладе будет приведена явная конструкция функции Голдрейха, обеспечивающая указанные оценки.