Content deleted Content added
→Generalization: new section |
|||
| (15 intermediate revisions by 10 users not shown) | |||
Line 1:
{{
{{WikiProject
{{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 219 ⟶ 224:
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">— 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)
| |||