Laboratory of Mathematical Logic at PDMI

Пятница, 4 декабря, комната 106. Начало в 18:00.

Докладчик: Д. Соколов.

Тема: Криптографическая стойкость односторонней функции Голдрейха.

Abstract

Доклад по статье A. Bogdanov, Y. Qiao, On the Security of Goldreich's
One-Way Function

В докладе будет рассказано о том, что функцию Голдрейха можно обратить
с большой вероятностью при следующих условиях:
1) Число выходов в достаточное число раз больше числа входов.
2) Предикат коррелирует с одним одним или с парой входов.

Будут рассказаны простые алгоритмы обращения (Majority Voting,
Pairwise), проведен анализ их работы, а также алгоритм Amplify.