Предположение о сокрытии фи - Phi-hiding assumption

В предположение о сокрытии фи или же Φ-скрытие предположения это предположение о сложности поиска малых факторы из φ (м) куда м это число, чье факторизация неизвестно, а φ равно Функция Эйлера. Безопасность многих современных криптосистемы происходит из-за воспринимаемой сложности определенных проблем. С Проблема P против NP до сих пор не решена, криптографы не могут быть уверены в существовании вычислительно неразрешимых проблем. Таким образом, криптографы делают предположения относительно того, какие проблемы жесткий. Принято считать, что если м это продукт двух больших простые числа, то вычисляя φ (м) в настоящее время невозможно с вычислительной точки зрения; это предположение требуется для безопасности Криптосистема RSA. Предположение Φ-сокрытия является более сильным предположением, а именно, что если п1 и п2 - маленькие простые числа, ровно одно из которых делит φ (м), здесь нет полиномиальное время алгоритм, который может различать, какое из простых чисел п1 и п2 делит φ (м) с вероятностью значительно больше половины.

Это предположение было впервые высказано в статье 1999 г. «Вычислительный поиск частной информации с полилогарифмической связью».[1], где он использовался в Получение частной информации схема.

Приложения

Предположение о сокрытии фи нашло применение при построении нескольких криптографических примитивов. Некоторые конструкции включают:

Рекомендации

  1. ^ Качин, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). Стерн, Жак (ред.). «Вычислительный поиск частной информации с полилогарифмической связью». Конспект лекций по информатике. Springer. 1592: 402–414. Дои:10.1007 / 3-540-48910-X. ISBN  978-3-540-65889-4. S2CID  29690672.