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