Однонаправленная (односторонняя) функция (one-way function)- отображение множества всех слов конечной длины п над конечным алфавитом, для которого существует такое , что образ любого слова длины п можно вычислить за операций, но ни для какого не существует алгоритма, вычисляющего для любого слова длины п его прообраз за операций Понятие о. ф. используется, в основном, при конкретизации определения криптографической стойкости асимметричных шифрсистем. Вопрос о существовании о. ф. является открытым. Доказательство односторонности какой-либо функции означало бы доказательство гипотезы в теории сложности алгоритмов. Различают сильные о. ф., слабые о. ф., функции дистрибутивно односторонние, подлинные и др. Иногда о. ф. называют эффективно вычислимую функцию, для которой не известен эффективный алгоритм обращения. |
|
