EP-4736361-A1 - BILINEAR PAIRINGS

EP4736361A1EP 4736361 A1EP4736361 A1EP 4736361A1EP-4736361-A1

Abstract

A computer-implemented method for generating a pairing is provided. An intermediate value, derived based on an initial value provide by a provider, is obtained. A candidate inverse intermediate value is received from the provider. It is determined if the candidate inverse intermediate value is equal to a target inverse intermediate value, wherein the target inverse intermediate value is an inverse of the intermediate value. If the candidate inverse intermediate value is equal to the target inverse intermediate value, the pairing is computed based on the intermediate value and the candidate inverse intermediate value.

Inventors

GERMOUTY, Paul
LARRAIA, Enrique
ZHANG, WEI

Assignees

nChain Licensing AG

Dates

Publication Date: 20260506
Application Date: 20240529

Claims (19)

CLAIMS 1. A computer-implemented method for generating a pairing, the method comprising: obtaining an intermediate value derived based on an initial value provided by a provider; receiving, from the provider, a candidate inverse intermediate value; determining if the candidate inverse intermediate value is equal to a target inverse intermediate value, wherein the target inverse intermediate value is an inverse of the intermediate value; and if the candidate inverse intermediate value is equal to the target inverse intermediate value, computing the pairing based on the intermediate value and the candidate inverse intermediate value.
2. The method of claim 1, wherein the method is implemented in script.
3. The method of claim 1 or claim 2, wherein it is determined if the candidate inverse intermediate value is equal to the target inverse intermediate value by computing a dot product of the candidate inverse intermediate value and the intermediate value; wherein the candidate inverse intermediate value is equal to the target inverse intermediate value if the computed dot product is equal to one.
4. The method of any preceding claim, wherein the method further comprises implementing a previous computational block, wherein the intermediate value is an output of the previous computational block.
5. The method of claim 4, wherein the previous computation block comprises a Miller loop computation of a bilinear pairing computation, wherein the intermediate value is an output of the Miller loop computation.
6. The method of any preceding claim, wherein the initial value comprises a pair of points over which the pairing is computed.
7. The method of any preceding claim, wherein the initial value is a candidate proof, wherein the provider is a proof generator, wherein the method further comprises: implementing a next computational block, wherein the next computation block receives the pairing as an input and verifies the candidate proof based on the pairing.
8. The method of claim 7, wherein the candidate proof is a zero-knowledge proof.
9. The method of any of claims 1 to 6, wherein the initial value comprises a public key and a message, wherein the method further comprises: implementing a next computational block, wherein the next computation block receives the pairing as an input and generates a signature based on the pairing.
10. The method of any of claims 1 to 6, wherein the initial value comprises a signature and a curve generator, wherein the method further comprises: implementing a next computational block, wherein the next computation block receives the pairing as an input and generates a second signature based on the pairing.
11. A computer-implemented method for generating a challenge blockchain transaction, the method comprising: providing, at a first output of the challenge blockchain transaction, a first locking script, wherein the first locking script is configured, when executed together with a first unlocking script of a solution blockchain transaction provided by a provider, to implement the method of claim 1, wherein the first unlocking script comprises the initial value and the candidate inverse intermediate value, wherein the candidate inverse intermediate value is received by obtaining the candidate inverse intermediate value from the first unlocking script; and making the challenge blockchain transaction available to one or more nodes of a blockchain network.
12. The method of claim 11, wherein the first locking script is further configured, when executed together with the first unlocking script of a solution blockchain transaction, to: derive, based on the initial value, the intermediate value.
13. The method of claim 11 or claim 12, wherein the initial value is a candidate proof, wherein the first locking script is further configured, when executed together with the first unlocking script of a solution blockchain transaction, to: verify the proof based on the pairing.
14. A computer-implemented method for satisfying a challenge, wherein the challenge is satisfied based on a pairing derived from an intermediate value and an inverse of the intermediate value, wherein the intermediate value is derived from an initial value the method comprising: receiving, from a verifier, a request for the initial value and a candidate inverse intermediate value; and providing, to the verifier, the initial and the candidate inverse intermediate value, wherein the candidate inverse intermediate value is the inverse of the intermediate value; wherein the challenge is satisfied based on the pairing derived based on the candidate intermediate value and the initial value.
15. The method of claim 14, wherein the method further comprises generating a solution blockchain transaction comprising a first unlocking script, wherein the first unlocking script comprises the initial value and the candidate inverse intermediate value, and making the solution blockchain transaction available to one or more nodes of a blockchain network.
16. The method of claim 14 or claim 15, wherein the method further comprises: computing the candidate inverse intermediate value.
17. The method of any of claims 14 to 16, wherein the initial value is a candidate proof, wherein the method further comprises computing the candidate proof.
18. Computer equipment comprising: memory comprising one or more memory units; and processing apparatus comprising one or more processing units, wherein the memory stores code arranged to run on the processing apparatus, the code being configured so as when on the processing apparatus to perform the method of any of claims 1 to 17.
19. A computer program embodied on computer-readable storage and configured so as, when run on one or more processors, to perform the method of any of claims 1 to 17.

Description

BILINEAR PAIRINGS TECHNICAL FIELD The present disclosure relates to a computer-implemented method for generating a pairing, a method for generating a blockchain transaction for computing a pairing, and a method for satisfying a challenge which is satisfied based on a pairing. BACKGROUND Pairings over elliptic curves span a large number of cryptographic applications. For example, with pairings it is possible to construct signatures, identity-based encryption, non- interactive zero-knowledge proofs, and communication-efficient multi-party key agreement. A pairing ^^ is a bilinear map defined over two group source elements ^^ଶ in a torsion group ^^ [ ^^]. It maps a pair of elements to an element in a target group ^^் ≔ ^^∗ ^ೖ : SUMMARY Efficiently implementing a pairing in script is not trivial. Methods known in the art require script sizes of around 1.5MB. Provided herein are methods for improving the computational efficiency of a pairing computation, and thereby optimising a resultant pairing script. When computing a pairing, an inverse of an intermediate value is required. Inverting field elements is the most expensive arithmetic operation in the pairing calculation. To reduce the size of the script, and therefore reduce the computational requirements when computing the pairing, a method is provided herein in which a candidate inverse intermediate value is provided, and a check carried out to determine if it is the inverse of the intermediate value. If it is, the candidate inverse intermediate value can be used in the pairing computation. The script for implementing the check on the candidate inverse intermediate value is much smaller in size than the script for inverting a field element. According to one aspect disclosed herein, there is provided a computer-implemented method for generating a pairing, the method comprising: obtaining an intermediate value derived based on an initial value provide by a provider; receiving, from the provider, a candidate inverse intermediate value; determining if the candidate inverse intermediate value is equal to a target inverse intermediate value, wherein the target inverse intermediate value is an inverse of the intermediate value; and if the candidate inverse intermediate value is equal to the target inverse intermediate value, computing the pairing based on the intermediate value and the candidate inverse intermediate value. BRIEF DESCRIPTION OF THE DRAWINGS To assist understanding of embodiments of the present disclosure and to show how such embodiments may be put into effect, reference is made, by way of example only, to the accompanying drawings in which: Figure 1 is a schematic block diagram of a system for implementing a blockchain, Figure 2 schematically illustrates some examples of transactions which may be recorded in a blockchain, Figure 3 illustrates point addition and point doubling in an elliptic curve, Figure 4 schematically illustrates a conceptual division of scripts for computing a pairing, Figure 5 schematically illustrates dependencies of scripts implemented extension field arithmetic, and Figure 6 schematically illustrates relationships of scripts for implementing a Miller loop for computing a sing pairing or a multi-pairing. DETAILED DESCRIPTION OF EMBODIMENTS 1. ELIPTICAL CURVES AND PAIRINGS 1.1 Elliptic Curves Let a cubic equation ^^ଶ = ^^ଷ + ^^ ^^ + ^^ where the coefficients ^^, ^^ are taken from a finite field ^^^ of ^^ elements. An elliptic curve is the set of affine points ^^ ≔ ( ^^, ^^) that satisfy the above equation along with an extra point at infinity denoted with ^^: ^^^ is the field of definition of the curve, that is, ^^, ^^ ∈ ^^^, and ^^ is over ^^^. The coordinates ^^, ^^ of points ^^ ∈ ^^| ^^^ do not necessarily lie in ^^^, they can be defined over an extension field ^^^ೖ (of ^^^ elements). Notation. The notation ^^| ^^^: ^^ଶ = ^^ଷ + ^^ ^^ + ^^ means an elliptic curve over ^^^ with equation ^^ଶ = ^^ଷ + ^^ ^^ + ^^. ^^ ∶ ^^ଶ = ^^ଷ + ^^ ^^ + ^^ is written if the field of definition is understood from context but there is a want to stress which is the cubic equation. ^^ can be written if both the field of definition and the equation are understood from context; it denotes all points in the elliptic curve (that is, points ^^ ≔ ( ^^, ^^) with coordinates ^^, ^^ in any possible extension field). ^^( ^^^) denotes the set of points whose coordinates are in ^^^. Likewise, ^^( ^^^ೖ) denotes the set of points with coordinates in the extension ^^^ೖ. 1.1.1 Adding and Doubling Points in Affine Coordinates An elliptic curve ^^ forms a group under the ‘tangent and chord’ rule. This addition rule makes ^^ a group with identity element the point at infinity ^^. Figure 3 illustrates group law in elliptic curve. The left-hand graph illustrates point addition, while the right-hand graph illustrates point doubling. To add two points ^^ ≠ ^^ the line ℓ^,ொ passing through ^^, ^^ and the vertical line ^^ோ passing through the intersection poin