Hellman, Pedersen and Chaum: ZKPs with the Decisional Diffie–Hellman (DDH) assumption
One of my highlights of the academic year is when two of the greats of computer science came to talk to our students. These were Marty Hellman (the ‘Hellman’ in the Diffie-Hellman key exchange method [3]) and Torben P Pedersen (the ‘Pedersen’ in the Pedersen Commitment [2]) [interview]. Torben remembers keenly working with the mighty David Chaum, so let’s look at a method that combines the DH method with the Chaum-Pedersen method [3] to implement a Zero Knowledge Proof (ZKP).
The Diffie-Hellman part
A typical thing we must prove is that we still hold a secret (private) key. So, how can we bind Victor and Peggy into a proof infrastructure that Peggy can prove to Victor that she still holds a private key? For this, we will bind Victor and Peggy through a Diffie-Hellman key exchange.
Within Decisional Diffie–Hellman (DDH) we have a tuple of ⟨g,g^a,g^b,g^{ab}⟩ and where a and b are secrets. The values of g^a and g^b are exchanged between two parties, and after this, they should both be able to generate g^{ab}:
