2
$\begingroup$

What is the exact computational complexity in absolute operation numbers (multiplications, exponentiations, etc) of a bilinear map evaluation both for symmetric and asymetric groups. And how this is comparable with exponentiation?

$\endgroup$
5
$\begingroup$

This question can't be answered exactly, because it depends on a lot of the actual details of the realization. But as a rule of thumb: They cost a lot. In fact they cost so much, that in any protocol they are the sole determinator of the computation time and you can neglect the other operations.

First, keep in mind that usually bilinear maps are realized with elliptic curves. There is no straight forward bilinear maps in $\mathbb{F}_p$, which can be used for cryptographic tasks. Currently the only known constructions for (cryptographically useful) pairings are:

So first we need to consider the elliptic group operation, where the number of operations (addition, multiplication, etc.) can vary. Looking at the definition of the Weil pairings, we soon get to the following conclusion:

  • There is an integer $n$, which is chosen at the setup, but its role isn't that clear to begin with.
  • There is a function $F$ (on values $P,Q$), which just has to fulfill some property, but isn't specified any further. But the definition of the divisor has a sum, where the number of addends are linear in $n$, so the compuational complexity of $F$ will depend somehow on the choice of $n$.
  • The function definition $w(P,Q):= F/G$ has the $n$-th roots of unity as its image. Thinking of the bilinear map, this is the target group. And for cryptographic purposes we need a group where the discrete logarithm is hard in the target group, so we can conclude that $n$ has to be large.

This already shows, that unless you specify exactly what kind of elliptic curve and which kind of Weil pairing (or Tate pairing) you have, you can't state an explicit number of operations.

For further information I would suggest reading Pairings for beginners from Craig Costello, which also has plenty of examples with numbers.

$\endgroup$
  • 1
    $\begingroup$ well still this is not clear to me. For example with PBC library you can evaluate a paring in terms of microseconds $\endgroup$ – curious Oct 4 '16 at 16:10
  • $\begingroup$ If you want to evaluate any specific implementation, I'd suggest testing it and measuring the timing, possibly with different parametrizations. But with all the possibilities for different implementations and optimizations, I don't think you can state a general rule for exact numbers. $\endgroup$ – tylo Oct 4 '16 at 16:48
  • $\begingroup$ I want to evaluate the computational cost in terms of algebraic operations $\endgroup$ – curious Oct 4 '16 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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