# 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 $O$ 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 $P$ to a given
base $G$, i.e. finding $x$ such that $P=[x]G$, 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 $G,H∈G,$ where $G$ is a cryptographic group of order $q$. A random secret $r$ is chosen in $Z_{q}$, and the message to commit to $m$ is from any subset of $Z_{q}$. The commitment is

$c=Commit(m,r)=[m]G+[r]H.$

To open the commitment, the committer reveals $m$ and $r,$ thus allowing anyone to verify that $c$ is indeed a commitment to $m.$

Notice that the Pedersen commitment scheme is homomorphic:

$Commit(m,r)+Commit(m_{′},r_{′}) =[m]G+[r]H+[m_{′}]G+[r_{′}]H=[m+m_{′}]G+[r+r_{′}]H=Commit(m+m_{′},r+r_{′}). $

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

**hiding**: the adversary chooses messages $m_{0},m_{1}.$ The committer commits to one of these messages $c=Commit(m_{b},r),b∈{0,1}.$ Given $c,$ the probability of the adversary guessing the correct $b$ is no more than $21 $.**binding**: the adversary cannot pick two different messages $m_{0}=m_{1},$ and randomness $r_{0},r_{1},$ such that $Commit(m_{0},r_{0})=Commit(m_{1},r_{1}).$

### Vector Pedersen commitment

We can use a variant of the Pedersen commitment scheme to commit to multiple messages at once, $m=(m_{0},⋯,m_{n−1})$. This time, we'll have to sample a corresponding number of random public generators $G=(G_{0},⋯,G_{n−1}),$ along with a single random generator $H$ as before (for use in hiding). Then, our commitment scheme is:

$Commit(m;r) =Commit((m_{0},⋯,m_{n−1});r)=[r]H+[m_{0}]G_{0}+⋯+[m_{n−1}]G_{n−1}=[r]H+i=0∑n−1 [m_{i}]G_{i}. $

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:

- Alice and Bob publicly agree on two prime numbers, $p$ and $G,$ where $p$ is large and $G$ is a primitive root $(modp).$ (Note that $g$ is a generator of the group $F_{p}.$)
- Alice chooses a large random number $a$ as her private key. She computes her public key $A=[a]G(modp),$ and sends $A$ to Bob.
- Similarly, Bob chooses a large random number $b$ as his private key. He computes his public key $B=[b]G(modp),$ and sends $B$ to Alice.
- Now both Alice and Bob compute their shared key $K=[ab]G(modp),$ which Alice computes as $K=[a]B(modp)=[a]([b]G)(modp),$ and Bob computes as $K=[b]A(modp)=[b]([a]G)(modp).$

A potential eavesdropper would need to derive $K=[ab]g(modp)$ knowing only $g,p,A=[a]G,$ and $B=[b]G$: in other words, they would need to either get the discrete logarithm $a$ from $A=[a]G$ or $b$ from $B=[b]G,$ which we assume to be computationally infeasible in $F_{p}.$

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