Cryptography
pairings bilinear-pairing
Updated Fri, 02 Sep 2022 04:20:53 GMT

Why the definition of bilinearity property is different in cryptography compared to mathematics?


Background:

In Wikipedia (bilinear map definition), a condition listed as the following:

For any $\lambda \in F, {\displaystyle B(\lambda v,w)=B(v,\lambda w)=\lambda B(v,w)}$


In a math.stackexchange post, i saw this comment:

which defines bilinearity in the same way as the Wikipedia link. So I assume, the above definition of bilinearity is correct.


Now, the problem:

in the pairing-based cryptography setting:

the bilinearity is defined as such: ${\displaystyle \forall a,b\in F_{q}^{*},\ \forall P\in G_{1},Q\in G_{2}:\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}}$

The question:

in math: bilinearity is: $e\left(aP,bQ\right)=e\left(P,Q\right)ab$ (a and b have become coefficients)

in crypto: bilinearity is: $e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}$ (a and b have become exponents)

Why is this difference? Aren't the definitions conflicting with each other? In wicktionary I saw the following explanation:

Linear (preserving linear combinations) in each variable.

How come $e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}$ is preserving the linear combinations? Isn't exponent and coefficients are very different and not linear with each other?

Obviously, math is correct, and crypto is also correct. So, I really appreciate if someone can point out to me where am I missing the details or misinterpreting them?

P.S: someone in crypto.stackexchange defined the bilinearity as:

Bilinear: for all g 1 and a; b $Z_{q}^{*}, e(g^a, g^b) = e(g,g)^{a,b}$

I haven't seen this notation at all. Is the definition of bilinearity loose? So there can be multiple definitions? If so, why and how?




Solution

Why is this difference?

The difference between $e(P, Q)ab$ and $e(P, Q)^{ab}$ is entirely notational; there is no real difference at all.

There are two traditional ways to express the group operation:

  • As an analogue with addition; in this notation, the operation is expressed as $P + Q$; hence scalar multiplication is denoted as $\underbrace{P+P+...+P}_{n \text{ times}} = nP$ (or $Pn$)

  • As an analogue with multiplication; in this notation, the operation is expressed as $P \times Q$ (or $P \cdot Q$ or $PQ$); hence the scalar operation is denoted as $\underbrace{P \times P \times ... \times P}_{n \text{ times}} = P^n$

Both ways of writing things mean exactly the same thing; the difference is solely in how we choose to spell it.

Now, for some groups, we typically write them in additive form, and that's what the mathematical formulii do. In cryptography, the result of pairing operations that we use in practice is an element of a finite field group, and for those groups, we almost always write them in multiplicative notation; that's what the formulii you see reflect.





Comments (5)

  • +0 – Thank you very much. However your answer raised another question in my mind. In crypto-pairing: e(G1 x G2 -> Gt), both G1 and G2 are also in finite field, and also Gt is in finite field. Yet G1 and G2 are mostly in additive, but Gt is in multiplicative notation. Why is that? — Aug 02, 2022 at 17:26  
  • +1 – @ÖzgünÖZERK: actually, for the pairings we use in crypto, $G1$ and $G2$ are typically elliptic curve groups, and those groups are usually written in additive notation. — Aug 02, 2022 at 17:27  
  • +0 – Yes, I thought since elliptic curves are utilizing finite fields for their elements, it would be the same. Let me rephrase my question, what is separating $Gt$ from $G1$ and $G2$ then? AFAIK, $Gt$ shares the same properties with $G2$, and $Gt$ is also an elliptic curve. — Aug 02, 2022 at 17:31  
  • +0 – @ÖzgünÖZERK: while $G1, G2$ and $Gt$ have subgroups with the same order (they have to, in order for the pairing to be nontrivial), they don't necessarily have the same properties. And, in crypto, $Gt$ is typically $GF(p^k)$, where $p$ is the characteristic of $G1, G2$, and $k$ is a modest integer (e.g. 12) — Aug 02, 2022 at 17:42  
  • +1 – @ÖzgünÖZERK: correction to what I said: $Gt$ is typically the multiplicative group from the field $GF(p^k)$ (and that may be the reason it is usually written multiplicatively). As for $G1$ and $G2$, well, in crypto, $G1, G2$ are elliptic curve groups, and the tradition for writing those groups additively long predates the use of elliptic curves in crypto... — Aug 02, 2022 at 17:55