The Existence of One-Way Functions

04 January 2022, Version 1
This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.

Abstract

Under the assumption that there exist one-way functions, then we obtain a contradiction following a solid argumentation and therefore, one-way functions do not exist by contraposition. Hence, function problems such as the integer factorization of two large primes can be solved efficiently. In this way, we prove that is not safe many of the encryption and authentication methods such as the public-key cryptography. It could be the case that $P = NP$ or $P \neq NP$, even though there are no one-way functions. However, this result proves that $P = UP$.

Keywords

complexity classes
one-way function
polynomial time
exponential time

Supplementary weblinks

Comments

Comments are not moderated before they are posted, but they can be removed by the site moderators if they are found to be in contravention of our Commenting and Discussion Policy [opens in a new tab] - please read this policy before you post. Comments should be used for scholarly discussion of the content in question. You can find more information about how to use the commenting feature here [opens in a new tab] .
This site is protected by reCAPTCHA and the Google Privacy Policy [opens in a new tab] and Terms of Service [opens in a new tab] apply.