Talk:One-way function: Difference between revisions

Revision as of 06:40, 11 February 2007

Latest revision as of 19:27, 6 January 2025

(44 intermediate revisions by 35 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|

{{CryptographyProject}}

{{WikiProject Mathematics|priority=Mid}}

{{WikiProject Cryptography|importance=Top}}

}}

==Clarification==

I'd like some extra clarification introducing the topic. If a one-way-function means a function that is not reversible, it could be as simple as IsEven(int)->bool - you cannot recreate the input integer from it's output. Could someone please clarify how a one-way function differs from this? --[[Special:Contributions/198.160.96.7|198.160.96.7]] ([[User talk:198.160.96.7|talk]]) 21:15, 11 April 2013 (UTC)

:It is actually reversible but prohibitively so. It's an important detail because it means it can be used in cryptography as opposed to basically destroying the input but zero-ing it. [[User:Utopiah|Utopiah]] ([[User talk:Utopiah|talk]]) 08:01, 18 May 2023 (UTC)

::See https://en.wikipedia.org/wiki/Trapdoor_function [[User:Utopiah|Utopiah]] ([[User talk:Utopiah|talk]]) 08:02, 18 May 2023 (UTC)

==Bijection?==

Line 105 ⟶ 114:

:Erm . . . okay. You cryptographers can talk about that, and I'll just step to the side. Only, it doesn't really belong in a section about definitions being comprehensible to ''laymen''. :) —[[User:Simetrical|Simetrical]] ([[User talk:Simetrical|talk]] • [[Special:Contributions/Simetrical|contribs]]) 11:02, 3 January 2006 (UTC)

I agree. I studied a lot of mathematics courses at university level, and I can't seem to understand the definition. I'd like a little bit more clarification. What does the * mean? Is {0, 1} a set, and interval or something else? What does it mean to be "sufficently large"? Is there a formal definition of this? Does it mean the limit of some expression goes to zero when n goes to infinity? Maybe if we don't explain it in text we should at least have a few clickable links to other articles for further clarification. I really didn't understand the definition and feel it should be possible to explain it in an alterative way. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/78.72.135.178|78.72.135.178]] ([[User talk:78.72.135.178#top|talk]]) 09:32, 20 November 2017 (UTC)</small> <!--Autosigned by SineBot-->

== The formal definition is incomplete ==

Line 122 ⟶ 133:

[[User:John Baez|John Baez]] 09:47, 10 February 2006 (UTC)

:See [[Probabilistic Turing machine]]. Could be better named. [[User:Deco|Deco]] 11:59, 10 February 2006 (UTC)

:The auxiliary string isn't so much to inform the algorithm, it's simply to enforce a minimum length on the input. This is important because we defined the algorithm as working in polynomial time (implicitly tied to input length), but we actually just want the full f∘A'∘f to work in polynomial time, and the size of the input to f can dominate the size of the input to A'. I've removed the auxiliary string from the definition and added language instead, to reduce confusion. [[Special:Contributions/88.115.207.64|88.115.207.64]] ([[User talk:88.115.207.64|talk]]) 17:48, 29 October 2015 (UTC)

==Other types of function==

Line 139 ⟶ 151:

I'm a bit perplexed why the asymptotic time cited here is for elliptic curve factoring, rather than the [[number field sieve]]. Generally the sort of worst-case numbers used in cryptography are most efficiently factored with NFS, right? [[User:Deco|Deco]] 20:07, 11 June 2006 (UTC)

There is a mistake in the prime multiplication section, the complexity of the factorization algorithm is given as O(2^{(log N)^1/3(log log N)^2/3}), but log log N < log N, so 2^{(log N)^1/3(log log N)^2/3} < 2^{log N} = N^{log 2} < N², therefore O(2^{(log N)^1/3(log log N)^2/3}) is a subset of O(N²). Either O(2^{(log N)^1/3(log log N)^2/3}) is not the complexity of the factorization algorithm or else prime multiplication is not a one-way function. Wolfram<ref>{{cite web|title=One-Way Function|url=http://mathworld.wolfram.com/One-WayFunction.html|publisher=Wolfram}}</ref> gives prime multiplication as an example of a potential one-way function so I suspect that the factorization complexity is incorrect. Also, the [[integer_factorization|integer factorization]] page gives the complexity as O(exp((64/9 N)^1/3(log N)^2/3)) = O(2^{N^1/3(log N)^2/3}). [[User:Daspiffy|Daspiffy]] 23:26, 30 January 2013 (UTC).

{{reflist-talk}}

== Plagiarized ==

Line 158 ⟶ 174:

I am quite certain that having a constructive proof of P=NP would bring you no closer to reversing SHA-1 or SHA-256. --- Joshua

: Reading the pseudocode for SHA-256, I can tell you with absolute confidence that it would. In fact, if that code is accurate, I could write a program right now that could decrypt it in time polynomial in the length of the data and the computation time of kSAT's implementation, and I don't think I'd even need to open a book. [[User:Twin Bird|Twin Bird]] ([[User talk:Twin Bird|talk]]) 07:28, 18 June 2011 (UTC)

[[List_of_open_problems_in_computer_science#The_existence_of_one-way_functions]] says that P <math>\neq</math> NP does not imply the existence of a one-way function. This contradicts what is said in this article. [[Special:Contributions/192.87.139.139|192.87.139.139]] ([[User talk:192.87.139.139|talk]]) 12:16, 24 May 2011 (UTC)

:Where? It says "Existence of a proof that P and NP are not equal would not imply the existence of one-way functions" right in the article as it stands. It contradicts Pku_leehsin, but not the article. Are you confusing the assertion with its converse? Because a proof that one-way functions exist ''would'' imply P <math>\neq</math> NP, and a proof that P = NP (which is about as likely as the [[Riemann hypothesis]] being false) would imply their nonexistence. However, a proof that P <math>\neq</math> NP would not imply the existence of one-way functions, nor would their nonexistence imply P = NP. [[User:Twin Bird|Twin Bird]] ([[User talk:Twin Bird|talk]]) 05:32, 18 June 2011 (UTC)

== One-Time Pad? ==

This article says that the existence of a one-way function implies the existence of a private-key encryption scheme. Isn't this trivially true, due to the existence of the one-time pad? [[User:71.194.163.223|71.194.163.223]] 13:50, 24 July 2007 (UTC)

: I have clarified this in the article. OWF implies private-key encryption that is secure against chosen-plaintext and chosen-ciphertext attacks. One-time pad certainly doesn't meet this, as you need a fresh key for each new message sent. [[User:Blokhead|Blokhead]] 14:53, 24 July 2007 (UTC)

== Worst case vs average case ==

:Note that, by this definition, the function must be "hard to invert" in the average-case, rather than worst-case sense; while in most of complexity theory (e.g., NP-hardness) the term "hard" is meant in the worst-case.

This is just confusing concepts.

"Average case", as in taking mean time across all valid inputs, as in [[ZPP (complexity)|ZPP class]], is not what we want. We want something much stronger - we want inverting to be hard for overwhelming majority of cases.

For example, if we had a function f(x) which always took 4^(number of bits in x) time (under P!=NP and whatever other assumptions we need), then the function g(x) = 2*f(x) if x prime, g(x) = 2*x+1 otherwise, would still take exponential time on average to reverse (sum 4^log2(x)/ln(x)/N = sum x^2/ln(x)/N \in O(x)), but vast majority of cases would be trivially invertible, making such function useless as a one-way function. [[User:Taw|Taw]] ([[User talk:Taw|talk]]) 11:02, 16 September 2009 (UTC)

== Universal one-way function section makes almost no sense ==

It's very hard to understand... I get the general sense from this section that there exists a function that if proved to be one way, would prove that functions can be one way. But it doesn't explain much else... <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/69.117.26.39|69.117.26.39]] ([[User talk:69.117.26.39|talk]]) 00:33, 20 February 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

:I have edited the section to clarify its meaning, which is that there exists a function ''f'' such that if any function is one-way, then so is ''f''. --[[User:Joshua Issac|Joshua Issac]] ([[User talk:Joshua Issac|talk]]) 13:04, 29 August 2013 (UTC)

:: Still is probably the vaguest statement I have ever read on wikipedia. [[Special:Contributions/128.54.162.174|128.54.162.174]] ([[User talk:128.54.162.174|talk]]) 07:29, 11 December 2013 (UTC)

== One way function proven: ==

Here is a one-way function that is impossible to derive its input based on outputs: f(x)=0. What is this article or definition missing? [[User:Average64|Average64]] ([[User talk:Average64|talk]]) 19:51, 27 May 2014 (UTC)

: This example is discussed in the section "Theoretical definition". f(x)=0 is not a one-way function. Hence nothing is missing here. [[Special:Contributions/92.106.209.242|92.106.209.242]] ([[User talk:92.106.209.242|talk]]) 11:10, 29 May 2014 (UTC)

== Wrong integer multiplication upper bound ==

AFAIK, it's not O(n^2) as stated in the article.

See Fürer's algorithm, it can reach O(n\log n2^{3\log^* n}) [[User:Willrazen|Willrazen]] ([[User talk:Willrazen|talk]]) 19:27, 2 February 2016 (UTC)

== Explanation/Mention of Common Imprecise Usage of "One-Way Function" ==

I think it'd be a good idea to add one sentence to the header explaining that people often use the term "one-way function" to apply to functions that, while currently difficult to invert, may or may not be one-way functions under the formal definition of the term. (In fact, the articles for hash functions and cryptographic hash functions both describe them as being one-way functions.) There already is the section on "Candidates for one-way functions" but it's much further down and common alternate (albeit imprecise) usages of the term probably warrants some mention in the header. Thoughts? [[User:Jwuthe2|Jwuthe2]] ([[User talk:Jwuthe2|talk]]) 11:45, 2 November 2017 (UTC)

== Rabin function is "trapdoor" not "one way" ==

The "Rabin function" (squaring modulo some two-factor integer N) is one-way only if the factorization of N is not known. For any such N, that function is easy to invert. Thus it is not a "one-way function" but rather a "trapdoor function" (when N is included as the parameter of f and p,q as parameters of the inverse). It should be removed and discussed only in the trapdoor function article. --[[User:Jorge Stolfi|Jorge Stolfi]] ([[User talk:Jorge Stolfi|talk]]) 21:33, 15 August 2018 (UTC)

== Existence of one-way functions and implications to P and NP ==

On the one hand, the article states "[...] their existence would prove that the complexity classes P and NP are not equal [..]", but on the other hand also in an other section "The existence of one-way functions also implies that there is no natural proof for P≠NP".

Are both implications true? If yes, what is the point of ever presenting the second one without the first one? <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2A02:8070:8798:4000:80E4:FDE0:A138:9EB6|2A02:8070:8798:4000:80E4:FDE0:A138:9EB6]] ([[User talk:2A02:8070:8798:4000:80E4:FDE0:A138:9EB6#top|talk]]) 22:46, 7 February 2020 (UTC)</small> <!--Autosigned by SineBot-->

:I have removed the latter ("The existence of one-way functions also implies that there is no natural proof for P≠NP") because it is ambiguous. The existence of OWF implies that P≠NP directly which is stronger than saying no natural proof exists (the statement is relying on the fact that OWF implies the existence of PRF which in turn implies that no natural proof exists). [[User:PolyCreator|PolyCreator]] ([[User talk:PolyCreator|talk]]) 02:12, 10 April 2022 (UTC)

== Generalization ==

As defined here, one-way functions are defined so they are polynomial time, but their inverse is not. However, the same concept could be thought of more generally as functions with a strict upper bound that is a lower bound on their inverse. Is there any information about this more general problem, how it is formulated and described, it’s implications, and whether or not it has been solved?

== Half probability that prime is even? ==

In the section Candidates for one way functions, it is stated "...because the probability that an arbitrary p is odd is 1/2, and likewise for q(...)". But since 2 is the only even prime, that seems not correct? [[Special:Contributions/89.99.34.48|89.99.34.48]] ([[User talk:89.99.34.48|talk]]) 07:11, 24 July 2022 (UTC)

== "However, P≠NP does not imply the existence of one-way functions." ==

This statement implies P != NP and is therefore currently unknown. It should therefore be removed. (If P = NP, then P != NP is false and thus trivially implies anything.) --fiesh [[Special:Contributions/91.43.222.42|91.43.222.42]] ([[User talk:91.43.222.42|talk]]) 23:21, 15 November 2022 (UTC)

== Editor's note ==

I was reading the page, and in consulting the sources for the page noticed that the source for '''"Lecture Notes on Cryptography"''' '''is outdated'''. I don't have anything else to contribute just wanted to inform the lovely editors of this page. [[User:Zipore|Zipore]] ([[User talk:Zipore|talk]]) 19:27, 6 January 2025 (UTC)