Modern computational cryptography probes what is possible in our universe, and I think the results of this exploration may be interesting to people who wouldn’t normally be exposed to it.
All of our algorithms will have a “security parameter” k. Our goal is to make it so that an honest participant in the algorithm needs to spend only about k time for each operation, while anyone trying to break the scheme needs to use a super-polynomial amount of time in k. These assumptions are specifically engineered such that they don’t really depend on the type of computers being used.
When I say that a participant has a function in mind to evaluate, we are going to imagine that this function is described by its code in some programming language. It doesn’t matter which language if you are willing to accept constant factor slowdowns; you can translate from any reasonable programming language into any other.
Now onto the results, stated very imprecisely and given roughly in increasing order of surprisingness. I have chosen a really random selection based on my own interests, so don’t think this is an exhaustive list.
One-Way Function (OWF): A function is one-way if given x it is easy to compute f(x), but given f(x) it is hard to find either x or any other x’ such that f(x’) = f(x). For example, if I give you randomly chosen k-bit integers x, y, it is easy to compute their product x*y. But if I give you their product x*y, it is hard to recover x and y (or another pair of k-bit integers with the same product). We have many more explicit candidates for one-way functions, some of which are believed to be secure against quantum adversaries. Note that basically every other result here implies OWF, and OWF implies P != NP (so for the forseeable future we are going to have to make assumptions to do computational cryptography).
Pseudorandom Generator (PRG): Suppose I want to run a randomized algorithm that requires 1000000 bits of randomness, but I only have 1000 bits of randomness. A psuedorandom generator allows me to turn my 1000 bits of randomness into a 1000000 bits of psuedorandomness, and guarantees that any efficient randomized algorithm works just as often with a psuedorandom input as with a random input. More formally, a psuedorandom generator takes k random bits to k+1 psuedorandom bits in such a way that it is very difficult to distinguish its output from random. A PRG exists iff a OWF exists.
Private Key Cryptography: Suppose that Alice and Bob share a secret of length k, and would like to send a message so that an eavesdropper who doesn’t know the secret can’t understand it. If they want to send a message of length at most k, they can use a one time pad. Private key encryption allows them to send a much longer message in a way that is indecipherable to someone who doesn’t know the secret. Private key cryptography is possible if a OWF exists.
Psuedorandom Function Family (PRF): A psuedorandom function family is a small family of functions (one for each k bit string) such that a black box for a randomly chosen function from the family looks exactly like a black box which chooses a random output independently for each input. A PRF exists iff a OWF exists.
Bit Commitment: If Alice and Bob meet in person, then Alice can put a message into an envelope and leave this envelope in plain view. Bob can’t see the message, but if at some later time the envelope is opened Bob can guarantee that Alice wasn’t able to change what was in the envelope. Bit commitment allows Alice and Bob to do the same thing when they only share a communication channel. So for example, Alice could take a proof of the Riemann Hypothesis and commit to it. If someone else were to later give a proof of the Riemann Hypothesis, she could “open” her commitment and reveal that she had a proof first. If she doesn’t ever choose to open her commitment, then no one ever learns anything about her proof. Bit commitment is possible if a OWF exists.
Public Key Cryptography: Just like private key cryptography, but now Alice and Bob share no secret. They want to communicate in such a way that they both learn a secret which no eavesdropper can efficiently recover. Public key cryptography is not known to be possible if a OWF exists. We have a number of candidate schemes for public key cryptography schemes, some of which are secure against quantum adversaries. RSA is used in practice for this functionality.
Zero-Knowledge Proofs (ZKP): Suppose I know the solution to some hard problem, whose answer you can verify. I would like to convince you that I really do have a solution, but without giving you any other knowledge about the solution. To do this I can’t just give you a static proof; we need to talk for a while. We say that an interactive proof is zero knowledge if the person verifying the proof can guess how the conversation will go before having it (if he can effectively sample from the distribution over possible transcripts of the conversation), but it will only be possible for the prover to keep up his end of the conversation if he really has a solution. ZKPs exist for NP problems if OWFs exist.
Non-Interactive Zero-Knowledge Proofs (NIZKP): Naively, zero-knowledge requires interaction. But we can make it non-interactive if we make use of a common random beacon. So for example, I am going to prove to you that I have a proof of the RH. In order to prove it to you, I say “Consider the sequence of solar flares that were visible last night. Using that as our random data, here is a verification that I really have a proof of the RH.” Now we say that a protocol is zero-knowledge if the verifier can construct a non-interactive proof for apparently random strings of their own choice, but such that the prover can construct a proof for truly random strings if and only if he really has a solution. We have some candidate schemes for NIZKPs, but I know of none which are secure against quantum adversaries.
Digital Signatures: Modern law uses signatures extensively. This use is predicated on the assumption that I can obtain Alice’s signature of a document if and only if Alice has signed it. I very much doubt this is true of real signatures; a digital signature scheme makes the same guarantee—there is no efficient way to compute Alice’s signature of any document without having someone with Alice’s private key sign it. Digital signature schemes exist which are secure against classical adversaries if claw-free permutation pairs exist. I don’t know what the status of digital signatures against quantum adversaries is (they exist in the random oracle model, which is generally interpreted as meaning they exist in practice). RSA can also be used for this function in practice.
Homomorphic Public-Key Encryption: Just like public key cryptography, but now given an encryption of a message M I can efficiently compute the encryption of any function f(M) which I can compute efficiently on unencrypted inputs. There is a candidate scheme secure against quantum adversaries, but under pretty non-standard assumptions. There are no practical implementations of this scheme, although people who care about practical implementations are working actively on it.
Secure Function Evaluation: Suppose Alice and Bob have their own inputs A and B, and a function f(A, B) they would like to compute. They can do it easily by sharing A, B; in fact they can do it without sharing any information about their private input except what is necessarily revealed by f(A, B). If Alice cheats at any point, then the computational effort Bob needs to exert to learn f(A, B) is at most twice the computational effort Alice needs to exert to learn anything at all about B (this is a weaker assumption than usual in cryptography, but not that bad). There are no practical implementations of this functionality except for very simple functions.
And some random things I find interesting but which are generally considered less important:
Computationally Secure Arguments: Suppose that I am trying to prove an assertion to you. You only have a polynomial amount of time. I personally have an exponential amount of time, and I happen to also have a proof which is exponentially long. Conventional wisdom is that there is no possible way for me to prove the statement to you (you don’t have time for me to tell you the whole proof—its really extraordinarily long). However, suppose you know that I only have an exponential amount of time in terms of the message size. There is a proof protocol which isn’t perfectly secure, but such that faking a proof requires a super-exponential amount of time (in the random oracle model, which may correspond to a realistic cryptographic assumption in this case or may not).
Run-Once Programs: if I give you a program, you can copy it as much as you want and run it as often as you want. But suppose I have a special sort of hardware, which holds two messages but only gives one to the user (once the user asks for either message 0 or message 1, the hardware gives the specified message and then permanently destroys the other message). A run-once version of a program uses such hardware, and can be run once and only once. Run-once programs exist if public key encryption exists.
What is Cryptographically Possible
Modern computational cryptography probes what is possible in our universe, and I think the results of this exploration may be interesting to people who wouldn’t normally be exposed to it.
All of our algorithms will have a “security parameter” k. Our goal is to make it so that an honest participant in the algorithm needs to spend only about k time for each operation, while anyone trying to break the scheme needs to use a super-polynomial amount of time in k. These assumptions are specifically engineered such that they don’t really depend on the type of computers being used.
When I say that a participant has a function in mind to evaluate, we are going to imagine that this function is described by its code in some programming language. It doesn’t matter which language if you are willing to accept constant factor slowdowns; you can translate from any reasonable programming language into any other.
Now onto the results, stated very imprecisely and given roughly in increasing order of surprisingness. I have chosen a really random selection based on my own interests, so don’t think this is an exhaustive list.
One-Way Function (OWF): A function is one-way if given x it is easy to compute f(x), but given f(x) it is hard to find either x or any other x’ such that f(x’) = f(x). For example, if I give you randomly chosen k-bit integers x, y, it is easy to compute their product x*y. But if I give you their product x*y, it is hard to recover x and y (or another pair of k-bit integers with the same product). We have many more explicit candidates for one-way functions, some of which are believed to be secure against quantum adversaries. Note that basically every other result here implies OWF, and OWF implies P != NP (so for the forseeable future we are going to have to make assumptions to do computational cryptography).
Pseudorandom Generator (PRG): Suppose I want to run a randomized algorithm that requires 1000000 bits of randomness, but I only have 1000 bits of randomness. A psuedorandom generator allows me to turn my 1000 bits of randomness into a 1000000 bits of psuedorandomness, and guarantees that any efficient randomized algorithm works just as often with a psuedorandom input as with a random input. More formally, a psuedorandom generator takes k random bits to k+1 psuedorandom bits in such a way that it is very difficult to distinguish its output from random. A PRG exists iff a OWF exists.
Private Key Cryptography: Suppose that Alice and Bob share a secret of length k, and would like to send a message so that an eavesdropper who doesn’t know the secret can’t understand it. If they want to send a message of length at most k, they can use a one time pad. Private key encryption allows them to send a much longer message in a way that is indecipherable to someone who doesn’t know the secret. Private key cryptography is possible if a OWF exists.
Psuedorandom Function Family (PRF): A psuedorandom function family is a small family of functions (one for each k bit string) such that a black box for a randomly chosen function from the family looks exactly like a black box which chooses a random output independently for each input. A PRF exists iff a OWF exists.
Bit Commitment: If Alice and Bob meet in person, then Alice can put a message into an envelope and leave this envelope in plain view. Bob can’t see the message, but if at some later time the envelope is opened Bob can guarantee that Alice wasn’t able to change what was in the envelope. Bit commitment allows Alice and Bob to do the same thing when they only share a communication channel. So for example, Alice could take a proof of the Riemann Hypothesis and commit to it. If someone else were to later give a proof of the Riemann Hypothesis, she could “open” her commitment and reveal that she had a proof first. If she doesn’t ever choose to open her commitment, then no one ever learns anything about her proof. Bit commitment is possible if a OWF exists.
Public Key Cryptography: Just like private key cryptography, but now Alice and Bob share no secret. They want to communicate in such a way that they both learn a secret which no eavesdropper can efficiently recover. Public key cryptography is not known to be possible if a OWF exists. We have a number of candidate schemes for public key cryptography schemes, some of which are secure against quantum adversaries. RSA is used in practice for this functionality.
Zero-Knowledge Proofs (ZKP): Suppose I know the solution to some hard problem, whose answer you can verify. I would like to convince you that I really do have a solution, but without giving you any other knowledge about the solution. To do this I can’t just give you a static proof; we need to talk for a while. We say that an interactive proof is zero knowledge if the person verifying the proof can guess how the conversation will go before having it (if he can effectively sample from the distribution over possible transcripts of the conversation), but it will only be possible for the prover to keep up his end of the conversation if he really has a solution. ZKPs exist for NP problems if OWFs exist.
Non-Interactive Zero-Knowledge Proofs (NIZKP): Naively, zero-knowledge requires interaction. But we can make it non-interactive if we make use of a common random beacon. So for example, I am going to prove to you that I have a proof of the RH. In order to prove it to you, I say “Consider the sequence of solar flares that were visible last night. Using that as our random data, here is a verification that I really have a proof of the RH.” Now we say that a protocol is zero-knowledge if the verifier can construct a non-interactive proof for apparently random strings of their own choice, but such that the prover can construct a proof for truly random strings if and only if he really has a solution. We have some candidate schemes for NIZKPs, but I know of none which are secure against quantum adversaries.
Digital Signatures: Modern law uses signatures extensively. This use is predicated on the assumption that I can obtain Alice’s signature of a document if and only if Alice has signed it. I very much doubt this is true of real signatures; a digital signature scheme makes the same guarantee—there is no efficient way to compute Alice’s signature of any document without having someone with Alice’s private key sign it. Digital signature schemes exist which are secure against classical adversaries if claw-free permutation pairs exist. I don’t know what the status of digital signatures against quantum adversaries is (they exist in the random oracle model, which is generally interpreted as meaning they exist in practice). RSA can also be used for this function in practice.
Homomorphic Public-Key Encryption: Just like public key cryptography, but now given an encryption of a message M I can efficiently compute the encryption of any function f(M) which I can compute efficiently on unencrypted inputs. There is a candidate scheme secure against quantum adversaries, but under pretty non-standard assumptions. There are no practical implementations of this scheme, although people who care about practical implementations are working actively on it.
Secure Function Evaluation: Suppose Alice and Bob have their own inputs A and B, and a function f(A, B) they would like to compute. They can do it easily by sharing A, B; in fact they can do it without sharing any information about their private input except what is necessarily revealed by f(A, B). If Alice cheats at any point, then the computational effort Bob needs to exert to learn f(A, B) is at most twice the computational effort Alice needs to exert to learn anything at all about B (this is a weaker assumption than usual in cryptography, but not that bad). There are no practical implementations of this functionality except for very simple functions.
And some random things I find interesting but which are generally considered less important:
Computationally Secure Arguments: Suppose that I am trying to prove an assertion to you. You only have a polynomial amount of time. I personally have an exponential amount of time, and I happen to also have a proof which is exponentially long. Conventional wisdom is that there is no possible way for me to prove the statement to you (you don’t have time for me to tell you the whole proof—its really extraordinarily long). However, suppose you know that I only have an exponential amount of time in terms of the message size. There is a proof protocol which isn’t perfectly secure, but such that faking a proof requires a super-exponential amount of time (in the random oracle model, which may correspond to a realistic cryptographic assumption in this case or may not).
Run-Once Programs: if I give you a program, you can copy it as much as you want and run it as often as you want. But suppose I have a special sort of hardware, which holds two messages but only gives one to the user (once the user asks for either message 0 or message 1, the hardware gives the specified message and then permanently destroys the other message). A run-once version of a program uses such hardware, and can be run once and only once. Run-once programs exist if public key encryption exists.