One-way function

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. This has nothing to do with whether the function is one-to-one; finding any one input with the desired image is considered a successful inversion. (See § Theoretical definition, below.)

The existence of such one-way functions is still an open conjecture. Their existence would prove that the complexity classesP and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.^{[1]:ex. 2.2,page 70} The converse is not known to be true, i.e. the existence of a proof that P ≠ NP would not directly imply the existence of one-way functions.^[2]

In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any malicious agents". One-way functions, in this sense, are fundamental tools for cryptography, personal identification, authentication, and other data security applications. While the existence of one-way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most telecommunications, e-commerce, and e-banking systems around the world.

A function f : {0, 1}^* → {0, 1}^* is one-way if f can be computed by a polynomial-time algorithm, but any polynomial-time randomized algorithm${\displaystyle F}$ that attempts to compute a pseudo-inverse for f succeeds with negligible probability. (The * superscript means any number of repetitions, see Kleene star.) That is, for all randomized algorithms ${\displaystyle F}$, all positive integers c and all sufficiently large n = length(x),

${\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}$

where the probability is over the choice of x from the discrete uniform distribution on {0, 1} ⁿ, and the randomness of ${\displaystyle F}$.^[3]

Note that, by this definition, the function must be "hard to invert" in the average-case, rather than worst-case sense. This is different from much of complexity theory (e.g., NP-hardness), where the term "hard" is meant in the worst-case. That is why even if some candidates for one-way functions (described below) are known to be NP-complete, it does not imply their one-wayness. The latter property is only based on the lack of known algorithms to solve the problem.

It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function that outputs the string of n zeros on any input of length n is not a one-way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm F that just outputs any string of length n on input f(x) will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.

A one-way permutation is a one-way function that is also a permutation—that is, a one-way function that is bijective. One-way permutations are an important cryptographic primitive, and it is not known if their existence is implied by the existence of one-way functions.

A trapdoor one-way function or trapdoor permutation is a special kind of one-way function. Such a function is hard to invert unless some secret information, called the trapdoor, is known.

A collision-free hash functionf is a one-way function that is also collision-resistant; that is, no randomized polynomial time algorithm can find a collision—distinct values x, y such that f(x) = f(y)—with non-negligible probability.^[4]

المسند الأساسي لدالة أحادية الاتجاه f هو مسند (أي بت واحد) b بحيث يكون من السهل حساب b(x) بمعلومية x ولكن من الصعب حسابه بمعلومية f(x) فقط .

إذا كانت f دالة أحادية الاتجاه، فإن إيجاد معكوسها يُعدّ مسألةً يصعب حساب ناتجها (بحكم التعريف) ولكن يسهل التحقق منه (بمجرد حساب f عليها). وبالتالي، فإن وجود دالة أحادية الاتجاه يستلزم أن FP  ≠ FNP ، مما يستلزم بدوره أن P ≠ NP. مع ذلك، فإن كون P ≠ NP لا يستلزم بالضرورة وجود دوال أحادية الاتجاه.     

إن وجود دالة أحادية الاتجاه يستلزم وجود العديد من المفاهيم المفيدة الأخرى، بما في ذلك:

• مولدات الأرقام العشوائية الزائفة
• عائلات الدوال شبه العشوائية
• مخططات الالتزام بالبت
• أنظمة التشفير بالمفتاح الخاص آمنة ضد هجوم النص المشفر المختار التكيفي
• رموز مصادقة الرسائل
• أنظمة التوقيع الرقمي (آمنة ضد هجوم الرسائل المختارة التكيفي)

فيما يلي بعض الدوال المرشحة لتكون دوال أحادية الاتجاه (حتى أبريل 2009). من الواضح أنه ليس من المعروف ما إذا كانت هذه الدوال أحادية الاتجاه بالفعل؛ ولكن الأبحاث المكثفة لم تسفر حتى الآن عن خوارزمية عكس فعالة لأي منها.

توجد دالة صريحة f ثبت أنها أحادية الاتجاه، إذا وفقط إذا وُجدت دوال أحادية الاتجاه. ^{[ 5 ]} بعبارة أخرى، إذا كانت أي دالة أحادية الاتجاه، فإن f كذلك . ولأن هذه الدالة كانت أول دالة أحادية الاتجاه كاملة توافقيًا يتم إثباتها، تُعرف باسم "الدالة أحادية الاتجاه الشاملة". وبالتالي، فإن مشكلة إيجاد دالة أحادية الاتجاه تُختزل إلى إثبات - ربما بطريقة غير بنائية - وجود دالة واحدة من هذا النوع.

توجد أيضًا دالة أحادية الاتجاه إذا كان تعقيد كولموغوروف المحدود زمنيًا متعدد الحدود صعبًا نوعًا ما في المتوسط. وبما أن وجود الدوال أحادية الاتجاه يستلزم أن تعقيد كولموغوروف المحدود زمنيًا متعدد الحدود صعب نوعًا ما في المتوسط، فإن هذه الدالة تُعدّ دالة أحادية الاتجاه شاملة. ^{[ 6 ]}

• وظيفة الضغط أحادي الاتجاه
• دالة التجزئة المشفرة
• التشفير الهندسي
• وظيفة الباب المصيدة

• جوناثان كاتز ويهودا ليندل (2007). مقدمة في علم التشفير الحديث . دار نشر سي آر سي. رقم ISBN 1-58488-551-3.
• مايكل سيبسر (1997). مقدمة في نظرية الحوسبة . دار نشر PWS. رقم ISBN 978-0-534-94728-6.القسم 10.6.3: الدوال أحادية الاتجاه، الصفحات  374 - 376.
• كريستوس باباديميتريو (1993). التعقيد الحسابي (  الطبعة الأولى). أديسون ويسلي. ISBN 978-0-201-53082-7.القسم 12.1: الدوال أحادية الاتجاه، الصفحات  279 – 298.