6
$\begingroup$

As described by Wikipedia, BLS uses Diffie-Hellman in some way. I understand how Diffie-Hellman works in both its normal and elliptic curve forms. But what is the "pairing function"?

$\endgroup$
6
$\begingroup$

BLS signatures work in any so called gap group, i.e., a group where the computational version of the Diffie-Hellman (DH) problem - the CDH - is hard, but the decisional version of the DH problem - the DDH - is easy. Below I'm using the notation from the wikipedia article on BLS.

Just recall, that the DDH in a group $(G, g, r)$ (where $g$ is a generator and the group $G$ is of prime order $r$) is that, when given $(g, g^a, g^b, g^c)$, it's hard to decide whether $c=ab$.

If you look at the BLS signature verification, one checks whether the signature $\sigma$ for message $m$ has the form $\sigma=H(m)^x$ and writing it as $(g,h=g^x, H(m), \sigma)$, one sees that verification is to check for a valid DDH tuple (CDH needs to stay hard for unforgeability). Note that $H$ is a hash function modeled as a random oracle that maps strings to elements of $G$. So $H(m)$ can be written as $g^\gamma$ for some unknown $\gamma$.

Now, the existence of a pairing $e: G\times G \rightarrow G_T$ (symmetric for simplicity) exactly makes $G$ such a gap group. The check $e(\sigma, g) = e(H(m), h)$ in the signature verification exactly allows you to test if $(g,h=g^x, H(m), \sigma)$ is a valid DDH tuple. Using bilinearity of $e$, this should be easy to see, and I leave it as an exercise to you.

Pairings used in cryptography have evolved into a large (rather quickly changing) field and requires some time to study them. But the above symmetric pairing can be instantiated e.g., by setting $G$ as a subgroup of a supersingluar elliptic curve group, $e$ being the Weil pairing and $G_T$ a subgroup of the multiplicative group of a quadratic extension field of the curve's base field (you may want to look here for details). The choice of $H$ also depends on the setting, but it is crucial that $H$ is constructed such that one does not learn the discrete logarithm to the base $g$ from $H(m)$. You could look at the original BLS paper,who instantiate the scheme in a so called Type-2 pairing setting (in their setting, $G_2$ is the gap DH group). You may also want to look at this paper for how you can instantiate BLS in other Types of pairings.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I highly appreciate this answer, but regret that it currently does not come with a concrete illustration, especially of $H:\{0,1\}^*\to G$ for some $G$ allowing a pairing $e:G\times G\rightarrow G_T$. $\endgroup$ – fgrieu Oct 12 '16 at 10:49
  • 1
    $\begingroup$ @fgrieu Unfortunately, it is usually rather hard to compactly write that down. I now include some more details and pointers. $\endgroup$ – DrLecter Oct 12 '16 at 11:10

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.