Zero knowledge proof

A zero-knowledge-proof (also a knowledge-free proof ) or a zero-knowledge-protocol (also a knowledge-free protocol ) is a protocol from the field of cryptography . In a zero-knowledge protocol, two parties (the prover and the verifier) communicate with each other. There is a certain probability that the prover convinces the verifier that he knows a secret without disclosing information about the secret itself. A well-known procedure is the Feige-Fiat-Shamir Protocol . The Schnorr identification requires only three steps to communicate and the prover can convince them to know a secret that he does not know the verifier with only minimal probability.

Applications

Zero-knowledge protocols are used, among other things. a. of authentication . Some crypto currencies as Zcash, they increase the anonymity of payments.

properties

In practice, however, they are rarely used for authentication because they usually require a high level of interaction, i.e. H. the exchange of many messages, and are prone to replay attacks . The standardized authentication protocols used in practical applications are instead based on digital signatures . However, there are also constructions which convert certain zero-knowledge protocols into non-interactive variants.

Zero-knowledge protocols represent an extension of interactive evidence systems . In addition to the completeness and reliability of the interactive evidence systems, there is also the zero-knowledge property, which ensures that the verifier does not obtain any information about the secret.

A zero-knowledge protocol should always show that an input belongs to a formal language . To do this, a zero-knowledge protocol must meet three conditions: ${\ displaystyle x}$ ${\ displaystyle L}$

completeness: If the input is an element of language , then a verifier should almost always accept it after the protocol has expired. ${\ displaystyle x}$ ${\ displaystyle L}$
reliability: If the input is not an element of the language , i.e. if the prover is dishonest, then the verifier should reject it after the protocol has expired. However, a low probability of errors is allowed. ${\ displaystyle x}$ ${\ displaystyle L}$
Zero knowledge property: No more knowledge than the (in) validity of the statement to be proven may be gained from the interaction between the prover and the verifier. A third party who follows the interaction between prover and verifier does not even find out whether the prover even knows the secret (or whether the interaction between B and V was discussed).

Classic example

The following illustrative example of a zero-knowledge protocol was developed by Jean-Jacques Quisquater et al. (see literature ).

Peggy wants to prove to Viktor that she knows a secret that can be used to open a door in a cave without opening the door in front of his eyes (and thus showing him and others how to open the door). Furthermore, Peggy only wants to convince Viktor that she knows the secret and not third parties.

Viktor stands at 4 and sees Peggy going into the cave. He doesn't see if Peggy goes to 1 or 2. Then Viktor goes to 3 and demands that Peggy come out of the cave on the side he has specified. If Peggy isn't on the right side, she'll have to open the red door to do it. If Peggy can open the door, she can always come out on the side Viktor asked. If she can't open the door, 50% of the time she has to come back on the wrong side.

If Peggy comes out of the cave after n attempts every time on the side Viktor requested, Viktor can assume with a probability that Peggy knows the secret of the door, but has still not gained any new knowledge about the door, such as how exactly to close it open is whether it can only be opened from one side etc. ${\ displaystyle 1-2 ^ {- n}}$

However, this proof only works for Viktor: If a third party observes the process, he is not convinced that Peggy knows the secret of the door, as Viktor and Peggy may have agreed which side Viktor will ask for in each of the passages.

Peggy could also prove to Viktor directly that she knows the secret without having to reveal it: Viktor and Peggy both go to 3, from where Viktor sees Peggy going into the cave in one direction and coming out the other. To do this, she has to go through the red door. Viktor doesn't see how this happens from 3 and doesn't learn the secret, but still knows for sure that Peggy can open the door. The problem with this approach is that this practice could be recorded or observed by a third party. This means that Peggy can no longer deny knowing the secret by claiming to have worked with Viktor and can no longer determine who will find out that she knows the secret of the red door.

Example of a zero knowledge protocol

A zero knowledge log with ISOGRAPH

A zero knowledge authentication between two instances can take place with the help of the graph isomorphism problem . ultimately wants to prove to know the "secret" . This is obvious if knowing the decision can make plausible (and therefore always being able to give correct answers). To do this, the prover must first create a public key pair: ${\ displaystyle B}$ ${\ displaystyle V}$ ${\ displaystyle \ pi}$ ${\ displaystyle B}$ ${\ displaystyle a}$

The prover creates a very large graph .

{\ displaystyle B}

{\ displaystyle G_ {0}}

${\ displaystyle B}$ renumbered with a randomly and uniformly chosen permutation function . So let the resulting graph be . ${\ displaystyle G_ {0}}$ ${\ displaystyle \ pi}$ ${\ displaystyle G_ {1}: = \ pi (G_ {0})}$

The couple is published, the permutation is kept secret.

{\ displaystyle (G_ {0}, G_ {1})}

{\ displaystyle \ pi}

{\ displaystyle B}

For example, suppose a person called a "verifier" wants to verify the identity of ; H. determine whether the private key belonging to the public key is actually in possession . Then this fact can be proven with the help of the following zero-knowledge protocol without disclosing the private key to the verifier or a third person : ${\ displaystyle B}$ ${\ displaystyle B}$ ${\ displaystyle (G_ {0}, G_ {1})}$ ${\ displaystyle \ pi}$ ${\ displaystyle B}$ ${\ displaystyle \ pi}$

The prover selects at random . In addition, the graph is renumbered by the randomly selected permutation function . The resulting graph is . finally sends to the verifier . In this step, the prover fixes himself on one of the graphs (commitment or witness). ${\ displaystyle B}$ ${\ displaystyle a \ in \ {0.1 \}}$ ${\ displaystyle G_ {a}}$ ${\ displaystyle \ rho}$ ${\ displaystyle H: = \ rho (G_ {a})}$ ${\ displaystyle B}$ ${\ displaystyle H}$ ${\ displaystyle V}$
The verifier receives the graph and chooses one at random . Then he asks to send him a permutation with the property (challenge). ${\ displaystyle V}$ ${\ displaystyle H}$ ${\ displaystyle b \ in \ {0.1 \}}$ ${\ displaystyle B}$ ${\ displaystyle \ sigma}$ ${\ displaystyle H = \ sigma (G_ {b})}$
A distinction must now be made between three cases:

${\ displaystyle \ sigma: = {\ begin {cases} \ rho & {\ text {falls}} a = b \\\ rho \ circ \ pi ^ {- 1} & {\ text {falls}} a = 0 {\ text {and}} b = 1 \\\ rho \ circ \ pi & {\ text {falls}} a = 1 {\ text {and}} b = 0 \ end {cases}}}$

${\ displaystyle B}$ sends the appropriately designed permutation of return (response). ${\ displaystyle \ sigma}$ ${\ displaystyle V}$
${\ displaystyle V}$ receives the sent by and checks whether it really applies. ${\ displaystyle B}$ ${\ displaystyle \ sigma}$ ${\ displaystyle H = \ sigma (G_ {b})}$

We now consider the three necessary conditions for a zero-knowledge protocol:

The above protocol is obviously complete because it is being constructed to satisfy the required equation . ${\ displaystyle \ sigma}$ ${\ displaystyle H = \ sigma (G_ {b})}$
A dishonest prover or a third person who wants to pretend to be can convince without knowledge of the verifier only with a probability of 0.5 (by correctly guessing the value in the first step). If the protocol is sufficiently often repeated and on the assumption that the provision of out is hard, the protocol is so reliable. ${\ displaystyle B}$ ${\ displaystyle \ pi}$ ${\ displaystyle a}$ ${\ displaystyle \ pi}$ ${\ displaystyle (G_ {0}, G_ {1})}$
The communication between prover and verifier in a round (steps 1 to 4) is of the form . If a simulator now generates random and uniform and thus calculates the graph , then the resulting probability distribution is identical to the distribution which is implied by the real protocol instances. Consequently, no secret knowledge (here the permutation ) can have been transferred (zero knowledge). ${\ displaystyle (H, b, \ sigma)}$ ${\ displaystyle S}$ ${\ displaystyle b '}$ ${\ displaystyle \ sigma '}$ ${\ displaystyle H '= \ sigma' (G_ {b '})}$ ${\ displaystyle \ {(H ', b', \ sigma ') \}}$ ${\ displaystyle \ pi}$

"Zero Knowledge" as an advertising term

Based on the zero knowledge proof, the term zero knowledge is used by some cloud computing providers to make it clear that the providers have no insight into the stored files of the users.

Since the term "zero knowledge" is already an established term in the field of cryptography and IT security, some cloud providers who have previously advertised their services with "zero knowledge cloud" have decided to no longer use this term .

literature

Jean-Jacques Quisquater, Louis Guillou: How to explain zero-knowledge protocols to your children . Advances in Cryptology - CRYPTO '89, Lecture Notes in Computer Science 435, pp. 628–631, 1990. ( PDF )
Comment: Extremely entertaining and theoretical introduction based on a now classic example .
Ivan Damgard, Jesper Buus Nielsen: Commitment Schemes and Zero-Knowledge Protocols , 2008, PDF
Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter: Modern methods of cryptography , 7th edition, p. 43ff, 2010, ISBN 978-3-8348-1228-5

Web links

Applied Kid Cryptography - A vivid representation of a zero-knowledge protocol using a game.
Zero-Knowledge Tutorial - Introduction by Oded Goldreich (English)

Individual evidence

↑ Christof Paar, Jan Pelzl: Cryptography Understandable: A Textbook for Students and Users Restricted Preview in Google Book Search
↑ Ian Stewart : Professor Stewart's Mathematical Detective Stories, limited preview in Google Book Search
↑ What are zk-SNARKs? | Zcash. Retrieved June 7, 2019 (American English).
↑ https://www.boxcryptor.com/de/blog/post/zero-knowledge-cloud-security/
↑ https://medium.com/@SpiderOak/why-we-will-no-longer-use-the-phrase-zero-knowledge-to-describe-our-software-ddef2593a489

[1] Christof Paar, Jan Pelzl: Cryptography Understandable: A Textbook for Students and Users Restricted Preview in Google Book Search

[2] Ian Stewart : Professor Stewart's Mathematical Detective Stories, limited preview in Google Book Search

[3] What are zk-SNARKs? | Zcash. Retrieved June 7, 2019 (American English).

[4] ttps://www.boxcryptor.com/de/blog/post/zero-knowledge-cloud-security/

[5] ttps://medium.com/@SpiderOak/why-we-will-no-longer-use-the-phrase-zero-knowledge-to-describe-our-software-ddef2593a489