This section covers the mathematics behind zero knowledge cryptography, which has been studied for a few decades. A basic number theory background will be helpful for understanding this section.

### Readings

Zero-Knowledge Proofs for discrete logs (first section)

Zero-Knowledge Proofs – full formal definition of ZKPs, including quadratic residue example. You probably don’t need to go through this whole thing.

Fiat-Shamir Heuristic – a technique that can be used to make interactive zero-knowledge protocols into non-interactive protocols.

### Quests

- Implement a non-interactive ZKP for discrete log in code! Specifically, you should implement:
- a function
`dlogProof(x, g, p)`

that returns (1) a residue`y`

, evaluated as`g^x (mod p)`

and (2) a proof of knowledge`pf`

that you know`x`

that is the discrete log of`y`

. - a function
`verify(y, g, p, pf)`

that evaluates to`true`

if`pf`

is a valid proof of knowledge, and`false`

otherwise. The prover should only be able to compute a valid proof with non-negligible probability if they do indeed know valid`x`

. **if you need help, a reference implementation in Javascript with comments can be found here.**

- a function
- Complete these Understanding Questions