This article first appeared on Medium.

Pairing-based cryptography is a variant of elliptic curve cryptography, on which Bitcoin ECDSA signatures are based. Thanks to the characteristics of pairing, new cryptographic algorithms and protocols can achieve functions or efficiency that cannot be achieved otherwise, such as Identity-Based Encryption (IBE), Attribute-Based Encryption (ABE) , authenticated key exchange (AKE) and short signatures.

Bilinear pairing” width=”448″ height=”351″ srcset=”https://coingeek.com/wp-content/uploads/2022/06/bilinear-pairings-on-bitcoin-pairing-based-cryptography-part- 1-inline-1.png 448w, https://coingeek.com/wp-content/uploads/2022/06/bilinear-pairings-on-bitcoin-pairing-based-cryptography-part-1-inline-1-300×235 .png 300w, https://coingeek.com/wp-content/uploads/2022/06/bilinear-pairings-on-bitcoin-pairing-based-cryptography-part-1-inline-1-280×220.png 280w, https ://coingeek.com/wp-content/uploads/2022/06/bilinear-pairings-on-bitcoin-pairing-based-cryptography-part-1-inline-1-100×78.png 100w” sizes=”(max- width: 448px) 100vw, 448px”/>
Bilinear matching

Several applications of pairing-based cryptography have been used in practice in many blockchains.

  1. Zcash implements a zero-knowledge proof algorithm named zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)
  2. Ethereum supports pairing verification to perform zkSNARK verification
  3. DFINITY (now called The Internet Computer) built a scheme based on the BLS signature, which is shorter than ECDSA signatures.

We demonstrate that pairings can be implemented directly on Bitcoin and thus enable all sorts of pairing-based cryptography applications previously considered impossible on Bitcoin.

Bilinear pairings

A pairing e is simply a function that takes two inputs¹ and returns an output like below.

Twinning

Twinning

A bilinear matching has the following property:

: Bilinear cartographic equations
Bilinear cartographic equations

That is, it is linear in each of its inputs separately. It is easy to see the following takes.linear equation

Intuitively, we can permute the scalar not between its inputs and output it as an exponent.

An example of a toy

Consider the following matching function.

pairing function

It is bilinear because it satisfies the two equations above. For instance,

linear equations

Bilinear pairings on elliptic curves

In practice, the pairing above is not secure for cryptographic use. Instead, we use pairings on elliptical curves. The inputs are points on an elliptic curve and the output is a number². There are several ways to construct pairings on elliptic curves, such as Weil, Tate, and Ate pairings.

Miller’s algorithm

Miller’s algorithm is used to efficiently calculate pairings. It consists of two parts:

  1. main loop: Lines 3 to 10. It is structurally similar to the double-addition algorithm when calculating the multiplication of scalar points.
  2. final exponentiation at line 11.

pack, and r are parameters of the elliptic curve used³.

Miller's algorithm to compute the Tate matching e(P, Q)

Miller’s algorithm to compute the Tate matching e(P, Q)

Implementation

We have implemented Miller’s algorithm to compute Tate pairings below, based on our elliptic curve arithmetic library.

Implementing Tate e(P, Q) pairing

rowfunction(P, Q, R) is a linear function that passes through P and Q and is evaluated in R.

***

REMARKS:

[1] So the name twinning.

[2] In the strict sense, it is an element of a multiplicative group. Since this serves as an introduction to pairings, we favor readability over mathematical rigor throughout the article.

[3] Not all elliptical curves can be used for pairings. Only those where the pairings are efficiently computable are used in practice. These are called favorable matching curves, of which the Barreto-Naehrig (BN) or Boneh–Lynn–Shacham (BLS) curves are notable examples.

Watch: Keynote speech by Dr. Craig Wright: Cloud Security, Overlays & Blockchain at the BSV Global Blockchain Convention

New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn more about Bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.