John Napier’s Legacy Lives on Within Privacy and Cybersecurity: Meet NI-ZKPs with Discrete Logs

I am privileged to walk past John Napier almost every time I go to work. Well, I walk through John Napier’s Tower, but I think about his legacy in this modern world each time I walk through it. With this, we see discrete logs used in the Diffie-Hellman method and in Zero Knowledge Proofs (ZKPs). While we have mainly replaced discrete log methods with elliptic curves, we still retain the formal proofs within discrete logs.

Some basics

Before we start, let’s do some simple logarithm rules. Two basic rules that were defined by John Napier are:

In discrete logarithms, with then perform a (mod p) operation and where p is a prime number. And so we have:

Discrete Log Proof of Equality (DLEQ) with discrete logs

We can use Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the ‘Prover’) just has to prove that she still knows her secret. In an interactive version, Victor (the ‘Verifier’) sends Peggy a challenge, and Peggy can prove that she can provide a solution for it. In a non-interactive version, Peggy can create her own challenge.