Talk:One-way function: Difference between revisions

Revision as of 21:33, 15 August 2018

Latest revision as of 19:27, 6 January 2025

(19 intermediate revisions by 14 users not shown)

Line 1:

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

{{WikiProject Cryptography Mathematics|classpriority=Start |importance=HighMid}}

{{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 148 ⟶ 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 212 ⟶ 219:

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)