ZK13 – a ZKP for authentication and key exchange

Now, we will look at the ZK13 protocol, which I patented in 2013. It’s a non-interactive protocol that solves an issue that is very important to the Crypto Search Engine (CSE) project explained in Chapter 8, Homomorphic Encryption and Crypto Search Engine. Essentially, the issue is this: we need authentication without requiring a public key.

In this section, we will analyze the ZKP that’s used for authentication; we could call this protocol a ZK-proof of authentication. To better understand the problem, imagine Alice and Bob want to share a common secret, something that only they know. Let’s say that the secret is the answer to the following question: how many birds were counted at the lake shoreline today? The answer is known only to Alice and Bob, unless they have revealed it to someone, but this is a problem we will take into consideration later. For now, nobody else can know the answer except Alice...