The Existence of One Way Functions? Here is a Million Dollar Math Problem!
Can you solve it?
Introduction:
The existence of one-way functions is one of the most important problems in computer theory. If you don’t know what a one-way function is or why its existence is so significant, fear not. We will be exploring one-way functions together by starting with the fundamental concepts and then building our way up to understanding some of the advanced functions and try to answer the question in the title. But in order to understand one-way functions and their applications, you need to have basic knowledge about sets and mathematics which I’m assuming you have. To put it simply, for now, a one-way function is a function that is computationally easy to compute in one direction but hard to invert, hard in a sense that there are no efficient methods to solve them. Let’s leave the second part of the title for later.
Basic Concepts:
Let’s start at the very beginning. Over a century ago, George Cantor, a German mathematician presented the concepts of sets and derived all the mathematical theorems from just one axiom scheme, the Cantor’s Postulate, which states that for each set-theoretical formula A(x), it assumes the existence of set those and only those x satisfying A. This axiom met with a lot of contradictions but other mathematicians pragmatically replaced Cantor’s Postulate with a collection of its restricted cases, limiting the types of allowed properties A. In 1904, Zermelo noticed that one more axiom is needed to derive all known mathematics, the Axiom of Choice, which states that every function f has an inverse g such that f(g(x))=x for x in the range of f. It was accepted reluctantly and proofs that are dependent on it are being singled out to this day. Furthermore, it bought paradoxes. Let me break this down for you.
· The range of f is known and does not depend on any other information.
· If we have x, we can easily compute f(x)
· If y is in the range of f, it is hard to find x such that f(x)=y.
This forms the basis of what is known as a one-way function.
P versus NP Problem:
Now that you know informally what one-way functions and its basics are, we have to understand the famous and most discussed P versus NP problem. In simple terms, P stands for problems that are easy for computers to solve and NP stands for problems that are not easy for computers to solve but are easy for them to check. For example, a man wants to pack 100 watermelons into boxes. Each box can hold 20 kilograms without breaking. The man needs to know if 10 boxes will be enough to pack all 100 watermelons.
It may look easy, but it is not easy. It would require you to go through every possible combination. But checking the final answer is, however, easy. The question remains open; Are P problems and NP problems the same types of problem? Or, are there some problems that are easily verified but not easily solved? In mathematical terms, If P = NP, then it would make all the real world problems pretty easy to solve. And if you could prove it, you’ll get a million dollars. Yes, you read that right. Now here’s a million dollar statement, The existence of one-way functions if proven true, would imply P ≠ NP. It would mean that no general, fast ways to solve NP problems can exist, no matter how hard we look. There is much more into P versus NP problem, but that’s it for now. Our purpose is to just give you an idea of how one-way functions are related to the P versus NP problem. (Yep! If you can solve this, you are entitled to a million dollars for solving one of the Millennium Prize Problems!)
Past Attempts To Solve The Problem:
Now that you have developed an understanding of the problem statement, let’s look at some of the previous attempts that were made to solve this problem pertaining to one-way functions. Again, you have to have some basic knowledge of algebra, sets, and polynomials. But before diving into these attempts, there is one minor but useful concept that you have to understand, i.e time complexity.
There are a number of solutions to any given problem. For example, if I discuss the same problem with 10 different friends, then all of them would provide 10 different solutions to that one problem and I would, of course, choose the best solution. Same is the case with algorithms. A computer takes some time to solve a problem by using a certain algorithm. We want our machines to solve the problem in the quickest way possible using an efficient algorithm. An efficient algorithm is one that takes minimal amount of time to solve a problem. So, the time complexity of an algorithm signifies the total time required by the program to run until its completion. It is denoted by O and it’s usually called Big O.
First Attempt:
Let’s define a function f :{0:1}n à{0,1}* to be (t1,t2). It would be a one-way function if and only if it can be computed in time t1 and for all algorithms A that run in time t2 and for all x € {0,1}, A(f(x) ≠ x. But, this definition is quite problematic since the second requirement is too strong because for every function f and every x ∈{0,1}n, we can construct an algorithm that will always output x and thus A( f (x)) = x. So there is no function satisfying this definition. It is a failed attempt but it gives us a clue that one way functions may exist.
Second Attempt:
Let’s try to make a probabilistic statement — we will allow A to invert f on some very small fraction of the points.A function f : {0,1}n → {0,1}* is (t1 , t2 ,ε ) would be a one way function if and only if it can be computed in time t1 and for all algorithms A that run in time t2 , Prx∈{0,1}n ,c( A) [ A( f (x)) = x] < ε .
This definition is also problematic, since it’s too easy to satisfy: For example let’s take f ≡ 0 , it’s definitely easy to compute, also given a random x there is no way to guess a pre‐image of f (x) since every point is a pre‐image of 0 = f (x) . So this function satisfies the definition, but it doesn’t seem to capture any notion of computational hardness. It is, again, a failed attempt.
Third Attempt:
A function f : {0,1}n → {0,1}* is a one way function if it can be computed using an “efficient” algorithm (i.e. in time polynomial in the input length) for all polynomial‐time algorithms A,
p(n) = Pr x {0,1} ,c( A) ∈ [ f ( A( f (x))) = f (x)] is a negligible function. Transfer to asymptotic formulation has introduced a new problem: if f (x) is much shorter than x then A won’t have enough time to work on f (x) (its input and it must run in time polynomial to the length of its input), so once again it’s too easy to satisfy the definition.
All these attempts had something in common: all these functions are behaving as one-way functions only if the given values are of reasonable size. If we increase the values, let’s say exponentially, these algorithms would fail. So, we can get the gist that perhaps one-way functions exist.
Public Key Cryptography:
Now that you’ve got a basic understanding of one-way functions and how they work, It’s time for us to learn about some real world one-way functions that are conjectured but not proved. However, they are widely used in commerce and industry. One of the prime applications of a conjectured one-way function is public key cryptography. We will discuss cryptography in detail to get a sound understanding of one-way functions and how they work in the real world. Also, it would give you clues that can hint at a proof of the existence of one-way functions.
What is cryptography? To put it in simple terms, Cryptography is the process of converting ordinary information into abstract or unrecognizable data and vice versa. It’s main purpose is to store and transmit data securely such that only those for whom it is intended can access it.
Let’s take an example of two persons named Alice and Bob. Bob wants to send a love letter to his girlfriend Alice but he doesn’t want the postman or anyone else to read it except for Alice. So what Bob does is, he writes the letter in an encrypted form, meaning, he encrypts the information with the help of a secret set of instructions called a key. The contents of the letter can only be deciphered with the special key that was used for encryption. So, Bob writes the letter in encrypted form and then posts the letter to Alice. Now the catch here is that he needs to somehow share his secret key to Alice so that she could decipher the letter easily. Somehow, we assume that Bob successfully shared the key with Alice without letting anyone know and now she can easily decipher the letter.
We “assumed” that Bob somehow shared the key with Alice, but how? How keys can be securely transmitted from the sender to receiver was a major problem that baffled computer scientists for quite some time. However, Diffie and Helman in 1976, proposed the idea of public key cryptography systems, an encryption system where the key that is used to encrypt is different from the key that is used to decrypt (fancy word for deciphering). Several one-way functions have been found and are used in public key cryptography.
Let’s go back to our previous example of Alice and Bob and modify our story to understand the general idea of public key cryptography. Bob places his encryption key in a public directory where everybody, including the postman, can see it. And Bob has a decryption key different from the public key that only he knows. If Alice wants to send a love letter to Bob, she checks the public directory for Bob’s public key, encrypts the message using EB (M) = C, where M is the message and C is the text and EB is the public key, and sends the ciphertext C to Bob. If the postman tries to intercept, he will not be able to decipher it. Mind you, even Alice herself cannot decrypt the message. If you think that if she reverses the encryption process then she can decipher it, then you’re wrong. Remember one-way functions? Yes, she can encrypt but she cannot decrypt as only Bob holds the secret information to decrypt the key. So, you can see that Bob and Alice do not need any prior communication for key exchange. They do not need to share any secret key. Only Bob can decrypt messages encrypted with his public encryption key and vice versa. The secret key that Bob had for decryption is called a trapdoor information or a trap door function, a function that holds the key to decrypt the information. These trapdoor functions are the conjectured one-way functions. There are several conjectured one-way functions that are used in the public key cryptography, but we would discuss the most important one, the RSA algorithm.
RSA:
RSA stands for Rivest, Shamir, Adelman. They were the inventors of the public key cryptographic systems. A little bit of complex math ahead, but fear not if can’t make any sense of it. We have provided some reference links at the end for you to explore further. In the RSA algorithm, we have a public key, let’s suppose (a,b) and a private key d. To encrypt a message M (create ciphertext c), the message is raised to ath and to decrypt a ciphertext C (go back to message M), the ciphertext is raised dth power modulo n:
C ≡ E(M) ≡ Ma (mod b), encrypt the message
M ≡ D(C) ≡ Cd (mod n), decipher the message
This is a general description of the RSA algorithm. But how can we generate an RSA key that can be used for encryption and decryption? Following are the steps to generate an RSA key.
· Compute p as a product of two very large random prime numbers a and b. Although p is a part of a public key, factors of p, a and b are kept secret.
P = a *b
· Pick a decryption key d as a large random integer that is relatively prime to
(a — 1) * (b — 1). Their greatest common divisor must be 1. The inventors of RSA encryption suggested that any prime number greater than max (a,b) would suffice for decryption key d, but it is important that d is chosen from a large enough set so that it cannot be found by direct search.
Gcd(d,(a — 1)*(b — 1) = 1
· The encryption (public key) is computed to the multiplicative inverse of d modulo
(a — 1) * (b — 1)
e * d ≡ 1 (mod ( a — 1) * (p — 1))
It is very important to note that if p = ab and a,b are prime numbers, Euler’s totient function ⱷ (p) = ( a — 1) * (b — 1). ⱷ (p) is the number of numbers that are smaller than p and are co-prime with p. There is no efficient algorithm to factorize large integers and if the factors a and b of p are not known, there is also no efficient way to compute ⱷ (n). The security of the RSA lies in this property.
Conclusion:
We started with the informal definition of one-way functions and then defined the problem statement in question. We discussed some of the previous attempts that have been made to solve this problem and why they ended up as failures. After that, we saw some of the conjectured (meaning assumed without complete information) one-way functions and how they are put to use practically in industry. In the end, it’s still a mystery to us if one-way functions can be computed in polynomial time. It is a mystery that is still being tackled by computer scientists to this day. It is a mystery that seems impossible to be solved. But who knows? Maybe after reading this article, something must’ve clicked in your mind and you could be the one to solve this problem and earn yourself a million dollars! Ultimately, we cannot deny that the mystery surrounding one-way functions is still persistent and that the whole picture is waiting to be discovered.
Want to dive deep into this research? Visit this P vs NP web page which has a compilation of all the resources and research papers related to this to get started, truly a bible to those who want to focus on solving this.
To explore more about RSA algorithm, check this link, RSA Algorithm in Cryptography.
References:
- One-way function. (2018, June 11). Retrieved from https://en.wikipedia.org/wiki/One-way_function
- One-Way Function. (n.d.). Retrieved June 14, 2018, from http://mathworld.wolfram.com/One-WayFunction.html
- Bühler, P., Schlaich, P., & Sinner, D. (2018). PDF-Grundlagen. PDF Bibliothek Der Mediengestaltung,2–11. doi:10.1007/978–3–662–54615–4_1
- Tutorials Point. (2018, January 08). Public Key Encryption. Retrieved June 15, 2018, from https://www.tutorialspoint.com/cryptography/public_key_encryption.htm
- L., & A., L. (2003, August 17). The Tale of One-way Functions. Retrieved June 20, 2018, from https://arxiv.org/abs/cs/0012023
- What is Public-key Cryptography? (n.d.). Retrieved from https://www.globalsign.com/en/ssl-information-center/what-is-public-key-cryptography/
(This article was authored by Research Nest’s Technical Writer Zeeshan Mushtaq)
Clap and share if you liked this one, and do follow “The Research Nest” for more insightful content.
Interested in collaborating with The Research Nest in some revolutionary online research initiatives? Drop in an email at the.research.nest@gmail.com.
