Zero-Knowledge Proofs: keeping a secret a secret.

in

Certain situations in our lives require us letting people know we have the authority, or capability to do something, however we don't always want to disclose the details. When you apply for an appartment, how do you let the landlord know you can afford the rent without sharing your salary? When participating in a secret auction, how do the owners announce the winner without revealing any bids? This would be simple if everybody could be perfectly trusted, but when dealing with finances, reputation, and security, all parties want to ensure everything is truthful and fair. In some cases, proving you know a secret is equivalent to proving your identity; for example, if you had a recipe with a secret ingredient that only you knew, proving to others you know the secret ingredient would prove the dish you shared is indeed yours. In these cases, it is crucial that this information does not leak.

A solution to this problem became the basis for Zero-Knowledge Proofs (ZKP), techniques and protocols used in cryptographic proofs of authentication or knowledge without revealing any details. The original definitions of ZKP were based on an interaction between a pair of verifier and prover [1]. In many of these situations, a secret is known that grants a user authentication or verification. If this secret is stolen, others could pose as the original user and gain access to cryptographic systems.

The most essential properties of a zero-knowledge procedure is that an interaction between a verifier and prover can only end with the prover claiming its knowledge of a value x if the prover does in fact know x. The crucial result of this is that a prover who does know the secret cannot trick anybody into thinking otherwise; these two properties are known as completeness and soundness respectively. This is paramount for trustless systems; without the existence of a safeguard, a non-authenticated user could lie about its credentials in the hopes of fool others. The protocol should yield zero-knowledge to the verifier, meaning the verifier learns no new information from its interaction with the prover. Our last property is that of computational efficiency; in any cryptographic system, the time complexity taken for this verification should be quick [1].

Other use cases for ZKP include proving you have enough money for a transaction, proving you are a member of a group without revealing your identity, proving you know the location of a hidden object without revealing the location, and proving you know the solution to a puzzle without sharing it [2].

Example - Discrete Log Problem [3]:

Consider the key value y = gx \mod p for large prime number $p$, a value often used in public-private key cryptography [4]. In this case, the values of g and p are publicly known, but x is a secret known only to those authenticated in the public-private key cryptographic system. For large values g and p, finding this value x such y = gx mod p can be very difficult and not possible to do by brute force in a reasonable time.

Suppose user A chose a random value of x, calculated y=gx mod p, and distributed y to parties with whom A wishes to connect cryptographically. If a new member B arrives and is given y, B wants to verify if y actually came from A as claimed, and thus that there exists encrypted communication with A. How does A prove this fact to B without sharing any more details than is already known, in this case the values g, p and y.

The following protocol repeats T>1 times:

  • Step 1: A chooses a random value r in {1,...,p-1} and sends c = yr to B.
  • Step 2: B send back a random binary value b to A.
  • Step 3: A will return d = r + bx mod (p-1) to B.
  • Step 4: B will verify if gd mod p = c yb mod p.

This procedure is executed multiple times because it is possible for A to guess the value of b and fake an answer. If A guesses correctly that b=0, then A would be able to convince B with a random r and the appropriate c; however, if A knows b=1 will be requested, A can compute c' = gr/y mod p to give to B followed by d=r'. From Step 4, this verification would yield gr' mod p = c' y mod p = gr'/y y mod p. By requesting different values of b over several iterations, this ensures A can only pass every test if the value *x is known.

Example - Undeniable Signature [5]:

Similar to the previous example, suppose the public key y=gx is known however x is known only to A. Using x, A can sign a message m to communicate that the message was approved and sent by A; this signature is z=mx. The following protocol proves the valid signature of A without revealing x when g, y=gx, m and z are public:

  • Step 1: A chooses a random value r in {1,...,p-1}, B chooses two random values a, b in {1,...,p-1}. Each party does not yet reveal their values.
  • Step 2: B sends the value c = ma gb to A.
  • Step 3: A send the pair {ma gb+r, (ma gb+r)x} = {c gr, cx grx} to B.
  • Step 4: B sends values a and b to A to reconstruct Step 2.
  • Step 5: Once the reconstruction is successful, A sends value r to B to reconstruct Step 3:
    {ma gb+r, (ma gb+r)x} ={ma gb+r, za yb+r}
    .

Once this last step is verified, B has confirmed that the signature z is valid and came from A without A ever having to share the secret key x.

Zero-Knowledge Range Proofs

Zero-Knowledge Range Proofs(ZKRP) allow for flexibility in the value claimed. For a user A with secret x and a verifier B, a ZKRP suffices to prove to B that the value x is within a certain range of numbers, without ever specifying x. This can be useful with credit checks for an apartment for A to say its salary is enough without stating it. Geographically, A could make a claim about in which country the user resides, without pinpointing a location. Cryptographically, both ZKP and ZKRP have seen prototypes for use in blockchain technologies [2] as well as the fully private cryptocurrency Zcash [6].

ZKP can serve as a powerful tool in modern cryptography to prove without doubt one's authentication, signature, or credibility without the need to divulge any secrets. Privacy and security are of the utmost importance to many users and applications, and ZKP contribute to the verification and concurrent hiding of absolute truths in a trustless system.

References

[1] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity ofinteractive proof systems,”SIAM Journal on computing, vol. 18, no. 1,pp. 186–208, 1989.

[2] T. Koens, C. Ramaekers, and C. Van Wijk, “Efficient zero-knowledge rangeproofs in ethereum,”ING, blockchain@ ing. com, 2018.

[3] D. Chaum, J.-H. Evertse, and J. Van De Graaf, “An improved protocol fordemonstrating possession of discrete logarithms and some generalizations,”inWorkshop on the Theory and Application of of Cryptographic Techniques,pp. 127–141, Springer, 1987.

[4] W. Diffie and M. Hellman, “New directions in cryptography,”IEEE trans-actions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.

[5] D. Chaum, “Zero-knowledge undeniable signatures,” inWorkshop on theTheory and Application of of Cryptographic Techniques, pp. 458–464,Springer, 1990.

[6] “Zcash.” http://z.cash. Accessed: 2020-04-19.

Combinatorial design theory and how it applies to cryptography

in

While I was writing my NSERC Proposal for grad school, I came across the field of combinatorial design theory (CDT). Specifically,  I came across it's application of Block Design in CDT to deterministic key pre-distribution schemes (KPS) in wireless sensor network. In other words, cryptographic networks with very small computer nodes with little storage where you don't know they're configuration to each other beforehand. Although I am choosing to pursue network optimization for my grad studies, I find this field of CDT quite interesting, especially in the way it can be turned into a cryptography problem. I want to break down the basics of Block Design, and how this can be viewed in cryptography.

In Block Design, we work with a set system (I, B), where I is a set of v elements, and B is a collection of subsets of the elements in I. The elements in I are called points and the subsets in B are called blocks. As an example, if I has 100 numbered points, and each block in B has 20 elements, then you could have one blocks (1,2,3,4,...,20), and a second block (1,3,4,5,...,21). In other words, these blocks could have overlapping. For any element x in I, we say the degree r of x is the number of blocks in which x appears. If all x in I have the same degree r, then (I, B) is called regular. The rank k of (I,B) is the largest sized block in B. If all blocks are the same size k, we say (I,B) is uniform.

Let's put all the above information together. A regular, uniform set system with |I| = v and |B| = b is known as a (v, b, r, k)-design. In such designs, it must be the case that bk = vr. Note, that b is the number of blocks in B whereas k is the number of points in each block.  Taking it one step further, a (v, b, r, k)-design where every t points appears in precisely λ blocks is known as a t-(v, b, r, k, λ)-design. Since r and b can be derived from the other variables, we usually just call it a t-(v, k, λ)-design

How does this all relate to cryptography?! First, note that we're talking about a KPS system for sensor node - tiny computers with limited storage space. We want to assign a set of keys to each node such that two nodes that are within talking range that have the same key can securely communicate: this is the basis of cryptography. Going back to Block Design, we can call I the set of total possible keys we have to distribute, and B the collection of sensor nodes. v would be size of I, or the total number of possible keys, k would be the maximum number of keys any sensor node could have, and t and λ would represent a cluster of t keys showing up in λ sensor nodes.

It turns out that by turning this problem in cryptography into a CDT problem, we can make a lot of headway into finding a deterministic way of solving the KPS problems while balancing all the trade-offs such a network faces. Up until this was researched, probabilistic KPS was the main research done in this field, which essentially came down to randomly assigning keys to each sensor node in hopes two with the same key would fall near each other. With the deterministic approach, we take the guess work out of it and get a more stable solution to this problem.

Reference

K. M. Martin, On the Applicability of Combinatorial Designs to Key Predistribution for Wireless
Sensor Networks, In: Chee Y.M., Li C., Ling S., Wang H., Xing C. (eds) Coding and Cryptology.
IWCC 2009. Lecture Notes in Computer Science, vol 5557. Springer, Berlin, Heidelberg (2009).