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

Одностороння функція (one-way function) - центральне поняття теоретичної криптографії. Обгрунтування цієї тези становить основне завдання даного розділу. Наводяться також формальні визначення, розглядаються різні типи односторонніх функцій і обговорюється сучасний стан справ у дослідженнях з одностороннім функцій.

Говорячи неформально, односторонньою функцією називається функція, що легко обчислюється та для якої не існує ефективного алгоритму інвертування, тобто, обчислення за значенням функції будь-якого (хоча б одного) значення з прообразу. Ми використовуємо термін інвертування, а не обернення, щоб підкреслити відмінність наступних двох завдань. Під оберненням даної функції ми розуміємо задачу відшукання оберненої функції. Наприклад, щоб звернути лінійне перетворення, задане невироджених квадратною матрицею, потрібно обчислити обернену матрицю. Під інвертуванням розуміється масова завдання обчислення за заданим значенням функції значення з прообразу. При цьому зворотнього функції може не існувати. Крім того, зазвичай вважається, що даний алгоритм успішно інвертує функцію, якщо він робить це на деякій, досить великий частці значень.

В історичному аспекті походження поняття односторонньої функції неясно. У криптографічного літературі часто вказують на Діффі і Хеллмана як на авторів і відсилають до їх відомій роботі [DH]. Однак, поняття односторонньої функції було відомо і раніше [Wilk].

 

Моделі обчислень

Під ефективними алгоритмами, відповідно до тези Едмондс, ми будемо розуміти Поліноміальні алгоритми. Останні, згідно з підходом, прийнятим в теоретичній криптографії, можна визначити в двох моделях обчислень.

У однорідної (uniform) моделі обчислень поліноміальний алгоритм - це ймовірнісна машина Тьюринга, час роботи якої обмежена поліномом від довжини вхідного слова.

У неоднорідною (nonuniform) моделі під алгоритмом розуміється сімейство бульових схем  . Схема  має  входів і побудована, скажімо для визначеності, з функціональних елементів І, АБО та НЕ. Без обмеження спільності можна вважати, що всі елементи І і АБО двухвходові. Алгоритм  називається поліноміальних, якщо існує поліном, що обмежує зверху кількість елементів у схемі  для всіх досить великих  .

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

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