# BLS signatures and Kate commitments.

## Abelian groups
An abelian group is a set $H$ together with a map
$(\otimes): H \rightarrow H \rightarrow H$ so that:
$\forall a, b, c \in H, a \otimes (b \otimes c) = (a\otimes b) \otimes c$ (associativity)
$\forall a, b\in H, a\otimes b = b\otimes a$ (commutativity)
$\exists 1_H\in H, \forall a\in H, a\otimes 1_H = 1_H \otimes a = a$ (identity)
$\forall a\in H, \exists b\in H, a\otimes b = b \otimes a = 1_H$ (inverses)
### Examples:
* $\mathbb{Z}/n= \{0, \dots, n-1\}$ where $a\otimes b = a + b \pmod n$
* $U_n = \{a \in \{1, \dots, n-1\}\mid \gcd(n, a)=1\}$ where $a\otimes b = a \cdot b \pmod n$ (used in RSA)
* $GF(q)$ the field with $q$ elements where $\otimes$ is the addition in the field.
* $GF(q)^*$ the nonzero elements in $GF(q)$ with $\otimes$ the multiplication in the field.
* $\mu_n(q)=\{a \in GF(q)\mid a^n = 1\}$ where $\otimes$ is the field multiplication.
* $E(q)=\{(x,y) \in GF(q)^2 \mid y^2 = x^3+ ....\}$ the points in an elliptic curve where $\otimes$ is the addition in the elliptic curve.
### Notations/Properties:

If $H$ has $n$ elements and $a\in H$ then $a^n =1_H$ where by $a^n$ we mean $a\otimes \cdots \otimes a$ ($n$ times). Note that, sometimes we use the notation $n\cdot a$ instead of $a^n$, especially when the operation is addition, for example in elliptic curves or in $\mathbb{Z}/n$.

### Pairing.
Suppose $(G_1, \otimes_1), (G_2, \otimes_2),(G_T, \otimes_T)$ are 3 groups, each of order $r$ where $r$ is a prime. A bilinear pairing on is a function
$e: G_1 \rightarrow G_2 \rightarrow G_T$ so that
* $e(a \otimes _1 b, c) = e(a,c) \otimes_T e(b,c)$
* $e(a, b \otimes _2 c) = e(a,b) \otimes_T e(a,c)$
* $e(a,b)=1_{G_T}$ if and only if $a=1_{G_1}$ and $b =1_{G_2}$

Note that the above imply that
$e(a^k,b^l)=e(a,b)^{kl}$

That is the function is "linear" in both variables. In BLS $G_1, G_2$ are cyclic subgroups of $GF(q^n)$ points in elliptic curves and $G_T$ is $\mu_r(GF(q))$. For details see [Galbraight's book](https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html)

## BLS signatures

### Single signature
Let as above $G_1=<P>$, $G_2 =<S>$ and $G_T$ be groups of order $r$, $e$ a pairing and $s_k$ an integer (secret key). Consider also $PK=P^{s_k}$ and $SK= S^{s_k}$ the public keys associated to $s_k$. We use $P,S$ rather than $P_1, P_2$ so not to cause confussion for aggregated signatures.
Let $Q\in G_1$ be a message (in fact it will be the delinearisation of the message). In order to sign the message Alice sends $R= Q^{s_k}$. To verify the signature, Bob computes $C_1 = e(R, S)$ and $C_2 =e(Q, SK)$. Note that

$C_1 = e(R, S) = e(Q^{s_k}, S)=e(Q,S)^{s_k}= e(Q,S^{s_k})= e(Q,
SK)=C_2$

and so the verification of $C_1=C_2$ is a proof that Alice knows the secret $s_k$.

### Aggregation

Suppose $G_1, P,S, e$ as above and
$(s_{k_1},PK_1=P^{s_{k_1}},SK_1=S^{s_{k_1}})\dots (s_{k_n},PK_n=P^{s_{k_n}}, SK_n=S^{s_{k_n}})$ be $n$ private/public keys. Consider $Q_1, \dots , Q_n$ n different messages and $R_i= Q_i^{s_{k_i}}$ the corresponding signatures.
The aggregated signature will be $R = R_1\otimes_1 R_2\dots\otimes_1 R_n \in G_1$. The signature will be verified by computing $C_1=e(Q_1, SK_n)\otimes_T\dots e(Q_n, SK_n)$ and $C_2=e(R,S)$. $C_1=C_2$ will be aproof that the various signers's identities. This is less secure than the single signature verification because certain combination can verify accidentaly.

## Kate commitments.

### Commitment
In what follows, to simplify notation we will denote by $[s]_1=P^s$ and $[s]_2=S^s$. Therefore $[s]_i \in G_i$. Fix a sectret number $s\in \mathbb Z$ and compute and make availabe all the numbers $[s^k]_i$. Note that you can only do that if you know the number $s$, for example there is no way to get $[s^2]_i$ form the knowledge of $[s]_i$. Morteover, one can compute a polynomial in $s$, the point $a[s^k]_i =\sum _{j=1}{a} [s^k]_i$ (the sum is in the group $G_i$). You can also add two monomila the same way. Therefore if you are given a polynomial $f \in \mathbb Z[t]$ you can `evaluate` $[f(s)]_i$. Note that the value is not an integer but an element of $G_1$. This evaluation is available to both the producer and the verifier.
So, given a secret polynomial $p$ the Kate commitment is the resultin element $[p(s)]_1$.
Note also that the order of $G_1$ respectively $G_2$ is a very large prime $r$. An attacker would try to produce another polynomial $q$ so that $[q(s)]_i =[p(s)]_i$. This means that the integer $s$ is a root of the polynomial $p-q$ modulo $r$. This is a polynomial of degree $\le n$ and so it has at most $n$ roots. The number $n$ is `a lot` smaller than $r$ and so the probability that you will be able to guess the polynomial $q$ is rather trivial.
### Proof
The verifier now asks the commiter to prove that it knows the polinomial $p$. To do so it sents her a random point $x$. The prover computes $y=p(x)$ as well as the polinomial $q(t) = \frac{p(t)-y}{t-x}$.
Note that $p(t) = (t-x)q(t)$.
It then sends the verifier the values $([y]_1, [q(s)]_1)$.

The verifier uses the pairing $e$ above (recall that $e([a]_1, [b]_2)=e([1]_1,[1]_2)^{ab}$) to check that

$$e([q(s)]_1, [s-x]_2) = e([1]_1,[1]_2)^{q(s)(s-x)}=e([1]_1,[1]_2)^{(p(s)-y)} = e([p(s)-y]_1, [1]_2)$$

## Multiproofs:
You can do the same trick for multiple evaluation. That is if you want to prove that $p(x_i)=y_i$ then you
find theminimal polynomial $I$ that satisfies $I(x_i)=y_i$ and the polynomial $Z$ so that $Z(x_i) =0$. It follows that $p(t)-I(t)= q(t)\cdot Z(t)$. You then provide the proof $[q(s)]_1$. The verifier then just checks that:
$$ e([q(s)]_1, [Z(s)]_2) =e([p(s)-I(s)]_1, [1]_2)$$