Elliptic curves are used in cryptography mainly because of DLP i.e. it’s infeasible to calculate from .

Pairing helps to compute certain complicated equations on EC points. Traditional EC math lets anyone check linear constraints on the number (eg. checking ), but pairing lets you check quadratic constraints ( is checking **).

This makes DDH (Decision Diffie-Hellman) problem very easy to compute using pairings. Also DLog reduction becomes computably feasible if not done on extension fields of Finite Field as we want the target group to be sufficiently bigger so that it’s not possible to do DLog reduction.

is a function defined on EC points. This is the pairing. Also known as bilinear map. It is called as bilinear because it satisfies following constraints:

The pairing is linear in both constraints. So, EC Pairing is a function that takes a pair of points on an elliptic curve and returns an element of some other group, called the target group.

Example: , where

Pairing needs to have another property, i.e. Non-Degeneracy. For generators , :

Note: and can be any arbitrary operators. It doesn’t matter what symbols are used in abstract mathematics as long as they obey the properties of associativity, commutativity and reflexivity.

However, such simple pairings are not suitable for cryptography as its trivial to divide, compute logarithms and other computations. Simple integers can’t be used in a field having terms like public-private keys or one-way functions because anyone can go back to knowing and . Thus, we require numbers that can essentially function as “black boxes” or it’s only possible to do simple arithmetic like addition, subtraction, multiplication and division on them and nothing else. That’s where ECs and EC-points come in.

Pairing -

The reason why Bilinear map works?

First, we look into the concept of divisors.

Tate Pairings

Miller’s Algorithm

MOV Attack

MOV attack refers to the transfer of DLP over EC to finite field where it’s much easier to solve. This is related to the embedded degree of the EC.

Embedded Degree of an EC refers to the minimum value of k for which , where p = prime used for the field and n = order of the curve. This is actually called an attack because DLP shouldn’t be solvable on ECs and thus for curves used throughout the cryptographic primitives, value of k is unreasonably large such that pairings are computably infeasible to compute.

Complexities Assumptions on Bilinear Groups

  • Discrete Log problem is still difficult if target group is sufficiently large.
  • CDH (Computation Diffie-Hellman) is still hard as we can’t find if we know , , .
  • Bilinear Diffie-Hellman Problem: Given , compute tripartite-key-exchange

Prerequisites

  1. Fermat’s Little Theorem: for a prime p, and any positive integer a,
  2. Additive Group: set of numbers with operation defined on addition
  3. Multiplicative group: set of numbers with operation defined on multiplication
  4. Order of Multiplicative group

Resources