3
$\begingroup$

In vitalik's post here the below is mentioned,

This is the pairing. Mathematicians also sometimes call it a bilinear map; the word “bilinear” here basically means that it satisfies the constraints:

  • $e(P, Q + R) = e(P, Q) * e(P, R)$
  • $e(P + S, Q) = e(P, Q) * e(S, Q)$

Whereas the textbook definition of linearity (as mentioned on wikipedia) requires

A function $f: V \to W$ is said to be a linear map if for any two vectors $\mathbf{u}, \mathbf{v} \in V$ and any scalar $c \in K$ the following two conditions are satisfied:

  • Additivity $f(\mathbf{u} + \mathbf{v}) = f(\mathbf{u}) + f(\mathbf{v})$
  • Homogeneity $f(c \mathbf{u}) = c f(\mathbf{u})$

Bilinear maps are linear in both variables if the other one is kept constant, then shouldn't $e(P, Q + R) = e(P, Q) + e(P, R)$ ?

  1. What am I missing here?
  2. Does the multiplicative linearity shown in the case of pairings because of the pairing function itself. If so, can that multiplication be broken down and shown as addition?
$\endgroup$
1
  • 2
    $\begingroup$ Can you please link to Vitalik's post so we can read the context? Thanks! $\endgroup$ Mar 28 at 8:13

2 Answers 2

7
$\begingroup$

For any group, we can write the operation either additively or multiplicatively.

If we decide to write it additively, we write the operation as $a + b = c$

If we decide to write it multiplicatively, we write the operation as $ab = c$ or $a \cdot b = c$

Some groups are traditionally written additively, while other groups are traditionally written multiplicatively.

  1. What am I missing here?

Well, with the pairing operations we use in practice in cryptography:

  • the "inner" groups are elliptic curve groups, which are traditionally written additively.
  • the "outer" group is the multiplicative group of a finite field, which is traditionally written multiplicatively.

That's it; we just happened to pick different conventions for the two types of groups. Vitalik's post reflected those conventions, while the textbook quote from Wikipedia reflected a more general understanding (where the bilinear operation might be something other than what's cryptographically interesting).

If we wanted to, we could write the outer group additively. It would be a bit like writing the multiplicative group in the reals (that is, $\mathbb{R}^\times$) additively, as $4 + 7 = 28$ (which we would normally express as $4 \cdot 7 = 28$), but there's nothing other than tradition stopping us.

$\endgroup$
1
$\begingroup$

Poncho's answer gets to the point in that in this context (say Weil pairing on elliptic curves) the values of the pairing are in multiplicative group of a field. We could write the right hand side of that particular pairing additively also. But to do that we need to, in advance, decide which torsion group we are looking at!

If $P,Q,R,\ldots$ are all $n$-torsion points, we know that the values of the pairing are roots of unity of order (a divisor of) $n$. If we further select, once and for all, a primitive $n$th root of unity $\zeta\in K^*$ ($K$ is the field we work in), then an additive bilinear pairing $e_{additive}$ can be defined by $$ e(P,Q)=\zeta^{e_{additive}(P,Q)}. $$ So the values of the pairing would then be in the group $\Bbb{Z}/n\Bbb{Z}$ rather than the multiplicative group $\mu_n$ of roots of unity. There are at least two potential problems doing it this way:

  • Choice of $\zeta$. We need to make a pick. And also, when $n$ is large (often the case in cryptographically interesting cases), determining a value of $e_{additive}(P,Q)$ may require solving an instance of a discrete logarithm problem. I dare say I don't need to explain to this crowd, why avoiding that is a good idea.
  • Choice of $n$. We may want to change this somewhere along the treatment. Or not.
$\endgroup$
2
  • $\begingroup$ May be this should be a comment to either the question or Poncho's answer? For the record, I have only ever looked at exactly the Weil pairing on elliptic curves, and it's been a while. HNQ brought me here :-) $\endgroup$ Mar 28 at 12:37
  • $\begingroup$ Actually, there are easier to compute bilinear operations. For example, take any ring, where "addition" is the ring addition operation (both inner and outer) and the blinear operation $e(A, B) = A \cdot B$ is the ring multiplication operation. It is easy to show that it meets the criteria for bilinearity, and both inner and outer operations are naturally expressed in additive form. On the other hand, it is not cryptographically interesting (as the 'hard problems' associated with this bilinear operation aren't that hard) $\endgroup$
    – poncho
    Mar 28 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.