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

Односторонньої називається функція F: X → Y. володіє двома властивостями:

а) існує поліноміальний алгоритм обчислення значень F (x);

б) не існує поліноміальною алгоритму інвертування функції F. тобто рішення рівняння F (x) = y щодо x.

Говорячи неформально, клас P складається із завдань з поліноміальною складністю. Більш строго, клас P - це клас мов. розпізнаються за поліноміальний час на детермінованою машині Тьюринга. Якщо таку машину Тьюринга доповнити гіпотетичної здатністю «вгадування», виходить більш сильна модель - недетермінірованного машина Тьюринга. Клас NP - це клас мов, які розпізнаються за поліноміальний час на недетермінованої машині Тьюринга. Проблема збігу класів P і NP - це проблема співвідношення можливостей двох моделей обчислень: детермінована і недетермінірованного машина Тьюринга.

Іншим поняттям, ближчим до традиційної криптографії, в якій є секретний ключ, є поняття односторонньої функції з секретом. Іноді ще вживаються терміни функція з пасткою. функція опускний двері (англійська назва: one # 8209; way trap # 8209; door function).

Односторонньої функцією з секретом K називається функція F K. X → Y. залежна від параметра K і володіє трьома властивостями:

а) при будь-якому K існує поліноміальний алгоритм обчислення значень F K (x);

б) при невідомому K не існує поліноміальною алгоритму інвертування F K;

в) при відомому K існує поліноміальний алгоритм інвертування F K.

Про існування односторонніх функцій з секретом можна сказати те ж саме, що було сказано раніше про односторонні функції. Для практичних цілей криптографії було побудовано кілька функцій, які можуть виявитися односторонніми. Це означає, що для них властивість б) поки строго не доведено, але відомо, що завдання инвертирования еквівалентна деякій давно вивчається важкою математичної задачі. Приклади таких функцій наводяться в етюдах 3.5, 3.6, 3.7. Варто зазначити, що для деяких кандидатів на звання односторонньої функції були знайдені поліноміальні алгоритми инвертирования і тим самим доведено, що ці функції не є односторонніми.

Схожі статті