Одностороння функція

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

Існування таких односторонніх функцій досі є відкритою проблемою. З їхнього існування випливає твердження, що класи складності P та NP не рівні. Сучасна асиметрична криптографія ґрунтується на припущенні, що односторонні функції все-таки існують.

У прикладному контексті, терміни «легко» і «складно», як правило, інтерпретуються як «досить дешево для легітимних користувачів» і «занадто витратно для будь-яких несанкціонованих агентів». Односторонні функції, в цьому сенсі, є основними інструментами криптографії, ідентифікації особистості, аутентифікації, та інших складових безпеки даних. Хоча наявність таких функцій також є відкритою проблемою, є кілька кандидатів, які витримали десятиліття пильного розгляду. Деякі з них є необхідними елементами телекомунікаційних систем і, систем електронної комерції і Інтернет-банкінгу по всьому світу.

Теоретичне визначення

Функція f: {0, 1}ⁿ → {0, 1}^* є односторонньою, якщо f може бути обчислена алгоритмом поліноміальної складності, але для кожного довільного, поліноміальної складності, алгоритму A виконується:

$Pr[f(A(f(x)))=f(x)]<{\frac {1}{p(n)}}$

для будь-якого позитивного многочлену р(n) і достатньо великих n, вважаючи, що x обирається за рівномірним розподілом з {0, 1} ⁿ та випадковості A.

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

Відзначимо знову, що просто зробити функцію не бієкцією не робить її односторонньою функції. У цьому контексті, обернення функції означає визначення хоч якогось одного прообразу заданого значення, що не вимагає існування оберненої функції. Наприклад, f(x) = x² не є оборотньою (наприклад, f(2) = f(-2) = 4), але також не є односторонньою, бо для будь-якого значення можна обчислити один з елементів його прообразу за поліноміальний час, взявши його квадратний корінь.

Пов'язані поняття

trapdoor-одностороння функцію або trapdoor-перестановка — особливий вид односторонньої функції. Такі функції важко обернути не знаючи певну секретну інформацію — trapdoor (англ. люк).

Одностороння перестановка — одностороння функція, яка є перестановкою. Односторонні перестановки є важливим криптографічним примітивом, і не відомо, чи їхнє існування випливає з існування односторонніх функцій.

Хеш-функція без колізій f є односторонньою функцією, яка також стійка до колізій, тобто жоден довільний поліноміальночасовий алгоритм не може знайти колізію — значення x, y, що f(x) = f(y) — з не незначною ймовірністю.

Теоретичні наслідки односторонніх функцій

Якщо f є односторонньою функцією, то обернення f буде задачею, вихід якого важко обчислити (за означенням), але легко перевірити (шляхом обчислення f від нього). Таким чином, з існування односторонньої функції випливає, що P ≠ NP. Однак, невідомо, чи з P ≠ NP випливає існування односторонніх функцій.

З існування односторонньої функції випливає існування багатьох інших корисних концепцій, у тому числі:

• Псевдовипадкових генераторів;
• сімей Псевдовипадкових функції;
• Бітова схема зобов'язання;
• Приватний ключ шифрування схем, безпечний проти адаптивної атаки з вибором шифрованого тексту;
• MAC підпис;
• Схема цифрового підпису (безпечна проти адаптивної атаки з вибором повідомлень).

Кандидати на звання односторонньої функції

Є численна кількість кандидатів на звання односторонньої функції (станом на квітень 2009 року). Ясно, що невідомо, чи є ці функції дійсно односторонніми, але значні дослідження досі не змогли створити ефективний алгоритм обернення для хоч однієї з них.

Множення і факторизація

Функція f приймає на вхід два прості числа p і q в двійковому вигляді і повертає їхній добуток. Ця функція може бути обчислена за час O(n²), де n є сумарною довжиною (кількістю цифр) аргументів. Обернення цієї функція вимагає факторизацію заданого цілого числаN. Найкращі алгоритми факторизації, відомі для цієї задачі, працюють час $2^{O({(\log N)^{1/3}(\log \log N})^{2/3})}$, який є всього-лише псевдо-поліноміальний у $\log N$, число бітів, необхідних для поданняN.

Ця функція може бути узагальнена покладанням p і q у підходящому наборі напівпростих чисел. Відзначимо, що f не одностороння для довільних p, q>1, так як добуток буде мати 2 як дільник з імовірністю 3/4.

Модульне піднесення у квадрат і знаходження квадратного кореня

Функція f приймає два натуральних числа x і N, де N — добуток двох простих p іq. На виході — остача від ділення x² на N. Знаходження оберненої функції вимагає обчислення квадратного кореня за модулем N, тобто x, якщо відомо y і x² mod N = y. Можна показати, що останнє завдання таке ж складне, як і розкладання N на множники.

Криптосистема Рабіна ґрунтується на припущенні, що функція Рабіна (тобто, ця) є односторонньою.

Дискретне експоненціювання і логарифмування

Функція f приймає просте число p і ціле x між 0 і p−1; і повертає залишок частини 2^x поділеного на p. Ця функція дискретного експоненціювання може бути легко обчислена за час O(n³), де n — кількість біт у p. Обернення цієї функції вимагає обчислення дискретного логарифма за модулем p; якщо дано просте p і ціле y між 0 і p−1;, знаходимо таке x, що 2^x = y. Станом на 2009, немає опублікованих алгоритмів цієї задачі, які працюють за поліноміальний час. Схема ElGamal заснована на цій функції.

Криптографічні хеш-функції

Є ряд криптографічних хеш-функцій, які швидко обчислюються (наприклад, SHA 256). Деякі простіші версії не проходили складний аналіз, але найсильніші версії продовжують пропонувати швидкі, практичні рішення для розрахунку в один бік. Більшу частину теоретичної підтримки складають методи зриву деяких раніше успішних атак.

Інші претенденти

Інші претенденти в односторонні функції ґрунтуються на складності декодування випадкових лінійних кодів та інших завданнях.

Універсальна одностороння функція

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