Cryptographic groups

In the section Inverses and groups we introduced the concept of groups. A group has an identity and a group operation. In this section we will write groups additively, i.e. the identity is and the group operation is .

Some groups can be used as cryptographic groups. At the risk of oversimplifying, this means that the problem of finding a discrete logarithm of a group element to a given base , i.e. finding such that , is hard in general.

Pedersen commitment

The Pedersen commitment [P99] is a way to commit to a secret message in a verifiable way. It uses two random public generators where is a cryptographic group of order . A random secret is chosen in , and the message to commit to is from any subset of . The commitment is

To open the commitment, the committer reveals and thus allowing anyone to verify that is indeed a commitment to

Notice that the Pedersen commitment scheme is homomorphic:

Assuming the discrete log assumption holds, Pedersen commitments are also perfectly hiding and computationally binding:

• hiding: the adversary chooses messages The committer commits to one of these messages Given the probability of the adversary guessing the correct is no more than .
• binding: the adversary cannot pick two different messages and randomness such that

Vector Pedersen commitment

We can use a variant of the Pedersen commitment scheme to commit to multiple messages at once, . This time, we'll have to sample a corresponding number of random public generators along with a single random generator as before (for use in hiding). Then, our commitment scheme is:

TODO: is this positionally binding?

Diffie–Hellman

An example of a protocol that uses cryptographic groups is Diffie–Hellman key agreement [DH1976]. The Diffie–Hellman protocol is a method for two users, Alice and Bob, to generate a shared private key. It proceeds as follows:

1. Alice and Bob publicly agree on two prime numbers, and where is large and is a primitive root (Note that is a generator of the group )
2. Alice chooses a large random number as her private key. She computes her public key and sends to Bob.
3. Similarly, Bob chooses a large random number as his private key. He computes his public key and sends to Alice.
4. Now both Alice and Bob compute their shared key which Alice computes as and Bob computes as

A potential eavesdropper would need to derive knowing only and : in other words, they would need to either get the discrete logarithm from or from which we assume to be computationally infeasible in

More generally, protocols that use similar ideas to Diffie–Hellman are used throughout cryptography. One way of instantiating a cryptographic group is as an elliptic curve. Before we go into detail on elliptic curves, we'll describe some algorithms that can be used for any group.

Multiscalar multiplication

TODO: Pippenger's algorithm

Reference: https://jbootle.github.io/Misc/pippenger.pdf