PERFECT ONLINE PRIVACY
Early on, information sent over the internet such as emails, can be snatched in transit and information embedded in it compromised. But as important online transactions such as online banking took off, the need for security and encryption which led to sites and applications using secure socket layer (SSL) arose.
Even with the SSL, data sent over the internet still stands some risk of been compromised as the company who hosted your HTTPS can have access to data sent. This need for a perfect online security led to the use of end-to-end encryption such as advanced encryption standard (AES), data encryption standard (DES) where only the communicating users can read the messages. In principle, it prevents potential eavesdroppers including telecom providers, internet providers, and even the provider of the communication service from being able to access the cryptographic keys needed to decrypt the conversation.
Endpoints are the weakest link
For the moment at least, we do have good, easy-to-use solutions for secure communication between computers, including end-to-end encryption of our messages.
End-to-end is important, but security experts have warned over the years that the most vulnerable place for your data is not during transit from place to place, but rather when it’s stored or displayed at one end or the other, on a screen, on a disk, in memory or on some device in the cloud.
If someone can gain control of a device, they can read the messages without needing to decrypt them. And compromising endpoints, both smartphones and personal computers is getting easier day by day.
Why are we most vulnerable at the endpoint? Because we don’t like to be inconvenienced, and because adding more protection makes our devices harder to use, the same way putting multiple locks on a door makes it harder to get in, for both the homeowner and the burglar. That’s why a lot of people prefers that their login details is stored on their smartphones or personal computers, than having to retype it each time they want to access applications such as yahoo mail, Gmail, etc.
We think our communications are private mostly. Our next-door neighbor can’t hear us send an angry email or a saucy text, and even talking on a cellphone is more secure than using the century old tech in a landline telephone. But when it comes to keeping a lid on the details of your communication, who you communicate with, and when and how you do it, perfect privacy just seems unattainable.
In the wake of the NSA spying scandal, and the subsequent closure of two notable “secure” email services, even privacy experts seem to have given up.
“Our computing and communications infrastructure is fragile,” Seth Schoen, the Electronic Frontier Foundation’s senior staff technologist, told NBC News. “And people who want to spy on us have made it their business to understand the vulnerabilities and to figure out how to exploit them.”
The fact remains that what is not known, not revealed or shared, cannot be compromised. This is where perfect online privacy comes to play.
What is Perfect Online Privacy?
Perfect online privacy is an emerging aspect of online privacy that intends to limit the risk of a privacy breach or identity theft while working or performing transactions online.
Now that so much of normal life revolves around the internet, the privacy of each and every one of us is at risk. Social media users, service providers, internet banking users and governments all around the world are increasingly interested in tracking every single movement we make online.
This true internet privacy could finally become possible thanks to a new tool that can for instance let you prove you’re over 18 without revealing your date of birth, or prove you have enough money in the bank for a financial transaction without revealing your balance or other details. That limits the risk of a privacy breach or identity theft.
The tool is an emerging cryptographic protocol called a zero-knowledge proof. Though researchers have worked on it for decades, interest has exploded in the past year, thanks in part to the growing obsession with cryptocurrencies, most of which aren’t private.
Much of the credit for a practical zero-knowledge proof goes to Zcash, a digital currency that launched in late 2016. Zcash’s developers used a method called a zk-SNARK (for “zero-knowledge succinct non-interactive argument of knowledge”) to give users the power to transact anonymously.
That’s not normally possible in Bitcoin and most other public blockchain systems, in which transactions are visible to everyone. Though these transactions are theoretically anonymous, they can be combined with other data to track and even identify users. Vitalik Buterin, creator of Ethereum, the world’s second-most-popular blockchain network, has described zk-SNARKs as an “absolutely game-changing technology.”
For banks, this could be a way to use blockchains in payment systems without sacrificing their clients’ privacy. Last year, JPMorgan Chase added zk-SNARKs to its own blockchain-based payment system.
For all their promise, though, zk-SNARKs are computation-heavy and slow. They also require a so-called “trusted setup,” creating a cryptographic key that could compromise the whole system if it fell into the wrong hands. But researchers are looking at alternatives that deploy zero-knowledge proofs more efficiently and don’t require such a key. – Mike Orcutt
Zero-Knowledge Proofs
Zero-knowledge proofs (Goldwasser, Micah and Rackoff [1985]) provide a means for a prover A to convince a verifier B that some claim is true and nothing more. The prover holds some kind of “evidence” that “proves” its claim in the traditional sense (for example, the prover might hold an NP-witness); however, throughout its conversation with the verifier, the prover will reveal neither this evidence nor any nontrivial information about it. Nonetheless, as a “proof of knowledge”, the conversation must still, somehow, convince the verifier beyond doubt that the prover’s claim holds.
What makes a zero-knowledge proof of knowledge special, therefore, is what the verifier learns from it: nothing beyond the veracity of the prover’s claim.
As defined in the original GMR paper, the proofs refer to language membership problems (is input I a member of language L?), and their applicability to any language L in NP was demonstrated in Goldreich, Micah and Wigderson [1986]. Additional properties of zero knowledge proofs were investigated in Goldwasser and Sipser [1986], Brassard and Crepeau [1986], Chaum [1986], and many other papers.
If proving the statement requires knowledge of some secret information on the part of the prover, the definition implies that the verifier will not be able to prove the statement in turn to anyone else, since the verifier does not possess the secret information. Notice that the statement being proved must include the assertion that the prover has such knowledge (otherwise, the statement would not be proved in zero-knowledge, since at the end of the protocol the verifier would gain the additional information that the prover has knowledge of the required secret information). If the statement consists only of the fact that the prover possesses the secret information, it is a special case known as zero-knowledge proof of knowledge, and it nicely illustrates the essence of the notion of zero-knowledge proofs: proving that one has knowledge of certain information is trivial if one is allowed to simply reveal that information; the challenge is proving that one has such knowledge without revealing the secret information or anything else.
For zero-knowledge proofs of knowledge, the protocol must necessarily require interactive input from the verifier, usually in the form of a challenge or challenges such that the responses from the prover will convince the verifier if and only if the statement is true (i.e., if the prover does have the claimed knowledge). This is clearly the case, since otherwise the verifier could record the execution of the protocol and replay it to someone else: if this were accepted by the new party as proof that the replaying party knows the secret information, then the new party’s acceptance is either justified—the replayer does know the secret information—which means that the protocol leaks knowledge and is not zero-knowledge, or it is spurious—i.e. leads to a party accepting someone’s proof of knowledge who does not actually possess it.
Some forms of non-interactive zero-knowledge proofs exist, but the validity of the proof relies on computational assumptions (typically the assumptions of an ideal cryptographic hash function).
A zero-knowledge proof must satisfy three properties:
- Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
- Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
- Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulatorthat, given only the statement to be proved (and no access to the prover), can produce a transcript that “looks like” an interaction between the honest prover and the verifier in question.
The first two of these are properties of more general interactive proof systems. The third is what makes the proof zero-knowledge.
Examples
Table of Contents
The Ali Baba cave
There is a well-known story presenting the fundamental ideas of zero-knowledge proofs, first published by Jean-Jacques Quisquater and others in their paper “How to Explain Zero-Knowledge Protocols to Your Children”. It is common practice to label the two parties in a zero-knowledge proof as Peggy (the prover of the statement) and Victor (the verifier of the statement).
In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general.
They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path.
However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor’s requests would become vanishingly small (about one in a million).
Thus, if Peggy repeatedly appears at the exit Victor names, he can conclude that it is very probable—astronomically probable—that Peggy does in fact know the secret word.
One side note with respect to third-party observers: even if Victor is wearing a hidden camera that records the whole transaction, the only thing the camera will record is in one case Victor shouting “A!” and Peggy appearing at A or in the other case Victor shouting “B!” and Peggy appearing at B. A recording of this type would be trivial for any two people to fake (requiring only that Peggy and Victor agree beforehand on the sequence of A’s and B’s that Victor will shout). Such a recording will certainly never be convincing to anyone but the original participants. In fact, even a person who was present as an observer at the original experiment would be unconvinced, since Victor and Peggy might have orchestrated the whole “experiment” from start to finish.
Further notice that if Victor chooses his A’s and B’s by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy’s stated wishes. However, digital cryptography generally “flips coins” by relying on a pseudo-random number generator, which is akin to a coin with a fixed pattern of heads and tails known only to the coin’s owner. If Victor’s coin behaved this way, then again it would be possible for Victor and Peggy to have faked the “experiment”, so using a pseudo-random number generator would not reveal Peggy’s knowledge to the world in the same way using a flipped coin would.
Notice that Peggy could prove to Victor that she knows the magic word, without revealing it to him, in a single trial. If both Victor and Peggy go together to the mouth of the cave, Victor can watch Peggy go in through A and come out through B. This would prove with certainty that Peggy knows the magic word, without revealing the magic word to Victor. However, such a proof could be observed by a third party, or recorded by Victor and such a proof would be convincing to anybody. In other words, Peggy could not refute such proof by claiming she colluded with Victor, and she is therefore no longer in control of who is aware of her knowledge.
Two balls and the colour-blind friend
This example requires two identical objects with different colours, such as two coloured balls, and it is considered one of the easiest explanations of how interactive zero-knowledge proofs work. It was first demonstrated live by software engineers Konstantinos Chalkias and Mike Hearn at a blockchain related conference in September 2017 and is inspired by the work of Prof. Oded Goldreich, who used two differently coloured cards.
Imagine your friend is colour-blind and you have two balls: one red and one green, but otherwise identical. To your friend they seem completely identical and he is skeptical that they are actually distinguishable. You want to prove to him they are in fact differently-coloured, but nothing else, thus you do not reveal which one is the red and which is the green.
Here is the proof system. You give the two balls to your friend and he puts them behind his back. Next, he takes one of the balls and brings it out from behind his back and displays it. This ball is then placed behind his back again and then he chooses to reveal just one of the two balls, switching to the other ball with probability 50%. He will ask you, “Did I switch the ball?” This whole procedure is then repeated as often as necessary.
By looking at their colours, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same colour and hence indistinguishable, there is no way you could guess correctly with probability higher than 50%.
If you and your friend repeat this “proof” multiple times (e.g. 128), your friend should become convinced (“completeness”) that the balls are indeed differently coloured; otherwise, the probability that you would have randomly succeeded at identifying all the switch/non-switches is close to zero (“soundness”).
The above proof is zero-knowledge because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.
Applications
Authentication systems
Research in zero-knowledge proofs has been motivated by authentication systems where one party wants to prove its identity to a second party via some secret information (such as a password) but doesn’t want the second party to learn anything about this secret. This is called a “zero-knowledge proof of knowledge“. However, a password is typically too small or insufficiently random to be used in many schemes for zero-knowledge proofs of knowledge. A zero-knowledge password proof is a special kind of zero-knowledge proof of knowledge that addresses the limited size of passwords.
Ethical behavior
One of the uses of zero-knowledge proofs within cryptographic protocols is to enforce honest behavior while maintaining privacy. Roughly, the idea is to force a user to prove, using a zero-knowledge proof, that its behavior is correct according to the protocol.[8] Because of soundness, we know that the user must really act honestly in order to be able to provide a valid proof. Because of zero knowledge, we know that the user does not compromise the privacy of its secrets in the process of providing the proof.
Nuclear disarmament
In 2016, the Princeton Plasma Physics Laboratory and Princeton University demonstrated a novel technique that may have applicability to future nuclear disarmament talks. It would allow inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing or revealing the internal workings which might be secret.[9]
Blockchains
ZKPs can be used to guarantee that transactions are valid despite the fact that information about the sender, the recipient and other transaction details remain hidden.
Conclusion
I believe we all can agree that what is not known cannot be shared, and if the zero-knowledge proof can be effectively implemented as a way of ensuring that banking transaction are carried out without revealing our bank details, or getting online platforms to confirm if we have attained the age to use certain service without having to input our age. Then we can say we are heading towards a world where perfect online privacy is attainable.
References
https://www.technologyreview.com/lists/technologies/2018/
Efficient Zero-Knowledge Proofs and Applications by Ryan Henry
Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). “Non-Interactive Zero-Knowledge and Its Applications”. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988): 103–112. doi:10.1145/62212.62222
Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). “How to Explain Zero-Knowledge Protocols to Your Children” (PDF). Advances in Cryptology – CRYPTO ’89: Proceedings. 435: 628–631.
