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

Одностороння функція з секретом (англ. trapdoor function) — це одностороння функція $f(x)$, для якої існують деякі секретні дані k, що з їх допомогою легко обчислити $x:\,y=f(x)$. А $y=f(x)$ можна обчислити і без k. Односторонні функції широко використовуються в криптографії.

Односторонні функції набули поширеності в криптографії в середині 1970-х з оприлюдненням асиметричних алгоритмів шифрування Діффі, Геллманом і Мерклом. Діффі і Геллман винайшли термін (Diffie and Hellman, 1976). Було запропоновано декілька класів, дуже швидко виявилось, що знайти односторонню функцію важче ніж видавалось на перший погляд. Наприклад, ранні припущення з використанням проблеми суми підмножини досить швидко виявились непідхожими.

Прикладом такої функції може слугувати одностороння функція RSA. Через наявність секрету, що дозволяє легко обчислити першовзір більшість цифрових підписів покладаються саме на RSA функцію.