WikiDer > Предположение о сокрытии фи
В предположение о сокрытии фи или же Φ-скрытие предположения это предположение о сложности поиска малых факторы из φ (м) куда м это число, чье факторизация неизвестно, а φ равно Функция Эйлера. Безопасность многих современных криптосистемы происходит из-за воспринимаемой сложности определенных проблем. С Проблема P против NP до сих пор не решена, криптографы не могут быть уверены в существовании вычислительно неразрешимых проблем. Таким образом, криптографы делают предположения относительно того, какие проблемы жесткий. Принято считать, что если м это продукт двух больших простые числа, то вычисляя φ (м) в настоящее время невозможно с вычислительной точки зрения; это предположение требуется для безопасности Криптосистема RSA. Предположение Φ-сокрытия является более сильным предположением, а именно, что если п1 и п2 - маленькие простые числа, ровно одно из которых делит φ (м), здесь нет полиномиальное время алгоритм, который может различать, какое из простых чисел п1 и п2 делит φ (м) с вероятностью значительно больше половины.
Это предположение было впервые высказано в статье 1999 г. «Вычислительный поиск частной информации с полилогарифмической связью».[1], где он использовался в Получение частной информации схема.
Приложения
Предположение о сокрытии фи нашло применение при построении нескольких криптографических примитивов. Некоторые конструкции включают:
- Вычислительный поиск частной информации с полилогарифмической связью (1999)
- Эффективные частные торги и аукционы с неявной третьей стороной (1999)
- Поиск частной информации из одной базы данных с постоянной скоростью обмена данными (2005)
- Обмен ключами с аутентификацией паролем с использованием скрытых гладких подгрупп (2005)
Рекомендации
- ^ Качин, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). Стерн, Жак (ред.). «Вычислительный поиск частной информации с полилогарифмической связью». Конспект лекций по информатике. Springer. 1592: 402–414. Дои:10.1007 / 3-540-48910-X. ISBN 978-3-540-65889-4. S2CID 29690672.