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

Неформално казано, еднопосочната е полиномиално изчислима честна функция $f\colon\^*\to\^*$, чийто проблем с инверсията е неразрешим за полиномиално време. В момента еднопосочната функция е хипотетичен обект.

Понякога не се изисква честност при дефиницията на еднопосочна функция и се приема, че $1^n$ е дадено като вход към алгоритъма $\mathcal A$ в условие 2 заедно с $f(\widetilde u_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]) показва, че в конструкции, използващи произволна еднопосочна функция, без загуба на общост, можем да приемем, че тази функция запазва дължината.

---