Интернет магазин китайских планшетных компьютеров

Компьютеры - Односторонняя функция - Определение

Функция f: {0, 1} → {0, 1} является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью.

Существование

Существование односторонних функций не доказано. Если f является односторонней функцией, то нахождение обратной функции является трудновычислимой, но легкопроверяемой задачей. Таким образом, из существования односторонней функции следует, что P ≠ NP. Однако, не известно, влечет ли за собой P ≠ NP существование односторонних функций.

Существование односторонних функций повлечёт за собой существование многих других полезных криптографических объектов, в том числе:

• генераторов псевдослучайных чисел;
• Если существует OWF с тяжёлым битом , то существует;
• PRF-псевдо случайного генератора функций на основе односторонних функций;
• Message authentication code;
• Электронная цифровая подпись.