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

Материал из Википедии — свободной энциклопедии

Односторонняя функция (англ. one-way function) эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает нашу функцию с более чем экспоненциально малой вероятностью.

Существование таких функций не доказано. Современная асимметричная криптография основывается на предположении, что они все-таки существуют.

[править] См. также

• Trapdoor function (en)

[править] Ссылки

• Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
• Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography. CRC Press. ISBN 1-58488-551-3.
• Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN ISBN 0-534-94728-X Section 10.6.3: One-way functions, pp.374—376.
• Computational Complexity. — 1st edition. — Addison Wesley, 1993. — ISBN ISBN 0-201-53082-1 Section 12.1: One-way functions, pp.279—298.