Функція одностороння - Криптографія

Говорячи неформально, односторонньою називається поліноміально обчислювана чесна функція $f\colon\^*\to\^*$, завдання інвертування якої нерозв'язне за поліноміальний час. Нині одностороння функція – гіпотетичний об'єкт.

Іноді у визначенні односторонньої функції не вимагають чесності і припускають, що на вхід алгоритму $\mathcal A$ за умови 2 разом з $f(\widetilde u_n)$ подається $1^n$ (див. [1]). Тоді очевидно, що й функція $f\colon\^*\to\^*$ задовольняє умовам визначення 1, вона задовольняє також умовам даної модифікації цього визначення. Навпаки, якщо ця функція задовольняє умов цієї модифікації визначення 1, то функція $x\mapsto\left(1^\rvert>,f(x)\right)$ ($x\in\^*$) задовольняє умовам визначення 1.

Визначення 1 очевидно переноситься на випадок, коли $f$ визначена лише на $\bigcup_\^i$, де $I$ - нескінченне підмножина $\mathbb N$. Нехай $I$ - поліноміально перерахована множина, а $f\colon\bigcup_\^i\to\^*$ - одностороння функція. Тоді $f$ може бути продовжена на всі безліч $\^*$ зі збереженням односторонності (див. [1]).

Теоретично складності обчислень відомо поняття односторонньої функції, формализующей труднощі інвертування у разі. Це поняття не має значення для математичної криптографії, і тому в цьому довіднику не розглядається.

У цьому довіднику згадується поняття односторонньої функції неоднорідної моделі обчислень. Це визначення виходить з визначення 1 заміною умови 2 наступне:

Наступна пропозиція (див. [1]) показує, що у конструкціях, які використовують довільну односторонню функцію, без обмеження спільності вважатимуться, що ця функція зберігає довжину.

---