Talk:One-way function: Difference between revisions

Revision as of 19:51, 27 May 2014

Latest revision as of 19:27, 6 January 2025

(27 intermediate revisions by 21 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 109 ⟶ 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 126 ⟶ 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 145 ⟶ 153:

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 195 ⟶ 205:

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)