Wednesday, August 5, 2015

Chapters from Cryptography - We Love Secrets!

Chapter One


Digital signatures like RSA, DSA, ECDSA are widely spread and used for securing communication and information systems. These can be used also for using pseudonyms and hiding an identity, however, they are monitored and it is possible to find out the user's identity. There are other ways of coding communication however with no need of hiding an identity. In this article I am going to write a little bit about cryptography and then introduce one very interesting topic. People love secrets and even more they love revealing secrets, right? So we're going to discuss Zero-Knowledge Proof today.


Cryptography

Cryptography (C.) is study of techniques for secure communication in the presence of third parties. C. also includes building and analyzing protocols blocking the third parties, aspects of security i.e. data integrity or authentication. Nowadays is becoming more popular to talk also about reputation and trust in connection with security where hiding an identity is unacceptable.

C. is based on pairing (pairing-based cryptography, PBC). Pairing might reduce the complexity of problems. This activity can be expressed in algebraic terminology where there are two groups and the operation between them (bilinear pairing) affect the result which is an element of the third group.

Group signatures are based on usage of one group key. Two members of one group own different keys and anonymity is ensured by using the secret member signature. Verification is based on using public group key.

Zero- knowledge proof

Zero- knowledge proof concept in cryptography is a method (or protocol) wherein the first party (the prover) can prove the second party (the verifier) that the statement is true without revealing a "secret". What a Wikipedia-like definition, right? Let's see something more handy, an example.

George Danezis's example from Cyber Security Summer School was clear. I give you a sealed envelope and I'd like to proove to you that I know the secret inside. The result of the protocol is that you are convinced that I know the secret but you don't know the secret in the envelope. Question whether is that even possible is surely in place.

Public keys are based on basic mathematical operations. Using modulo % is useful and may cause hackers serious problems with revealing the code even they know the pattern. Let's say that you are asked to enter your password that is a random number calculated with a pattern that the verifier and the prover know. Even if your guess was correct, you are asked to provide some steps of your computing, a number you used in the calculation of your password using the pattern.

This is called Schnorr Identification Protocol. It uses some shared parameters for both, the prover and the verifier; group and generator. We know, that there is some private x on the provers side and public p = g^x. In the first step the prover send a message M = g^r where M is the message, also called commitment, g is a generator and r is a random number. The second step means sending a random c called also a challenge to the prover. After receiving c, the prover sends the third and last message (the response) s = r - cx (mod q). The verifier accepts, if (g^s)*(p^c) = M.

So again, we have:
private x
public generator g, group G
public p; p = g^x

Steps:
  1. The prover sends message M; M = g^r where g is the generator and r is random number
  2. The verifier sends random c called challenge
  3. The prover's response is s; s = r - cx (mod q)
  4. The verifier accepts is M = (g^s)*(p^c)
Let's check why it works.
We are trying to compare two results: M and (g^r)*(p^c), M received from the prover and the second one expression from the verifier. Why are those two equal?

Proof:

We know that M = g^r and try to prove that (g^s)*(p^c) = M
Regarding following expressions;
s = r - cx (mod q)
p = g^x
M = g^r
Let's do some algebra here;
(g^s)*(p^c) = (g^(r-cx))*(g^cx) = (g^r)(g^cx-cx) = g^r = M
And we're done here.

Sources:

Rivest, Ronald L. (1990). "Cryptography". In J. Van Leeuwen. Handbook of Theoretical Computer Science 1. Elsevier

Schnorr, Claus-Peter (1989). Efficient Identification and Signatures for Smard Cards.