Talk:One-way function: Difference between revisions

Revision as of 07:28, 18 June 2011

Latest revision as of 19:27, 6 January 2025

(37 intermediate revisions by 29 users not shown)

Line 1:

{{mathsWikiProject ratingbanner shell|class=Start|priority=Mid|field=discrete}}

{{WikiProject Mathematics|priority=Mid}}

{{CryptographyProject}}

{{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 106 ⟶ 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 123 ⟶ 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 140 ⟶ 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 178 ⟶ 193:

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)