Search

EP-4736363-A1 - BILINEAR PAIRINGS

EP4736363A1EP 4736363 A1EP4736363 A1EP 4736363A1EP-4736363-A1

Abstract

A computer-implemented method for computing a pairing in script is provided. Computing the pairing comprises at least one sub-computation executed in a target field, wherein the target field is represented as an extension field. A script is generated which comprises at least one subfunction configured to perform the sub-computation as an extension over the extension field.

Inventors

  • GERMOUTY, Paul
  • LARRAIA, Enrique
  • ZHANG, WEI

Assignees

  • nChain Licensing AG

Dates

Publication Date
20260506
Application Date
20240531

Claims (20)

  1. CLAIMS 1. A computer-implemented method for computing a pairing in script, the method comprising generating a script, wherein computing the pairing comprises at least one sub- computation executed in a target field, wherein the target field is represented as an extension field, wherein the script comprises at least one subfunction configured to perform the sub-computation as an extension over the extension field.
  2. 2. The method of claim 1, wherein the sub-computation is one of: a multiplication operation; and an inverse operation.
  3. 3. The method of claim 1 or claim 2, wherein the target field is a field of a Barreto- Lynn-Scott, BLS, family curve with an embedding degree of 12.
  4. 4. The method of any preceding claim, wherein a second field ^ ^ a is a quadratic extension over a first field ^ ^ , wherein a third field ^ ^ ^ is a quadratic extension over the second field ^ ^ ^, wherein a fourth field ^ ^ ^ is a cubic extension over the second field ^ ^ a, and wherein a fifth field ^ ^ ^a is: a sextic extension over the second field ^ ^ a; a cubic extension over the third field ^ ^ ^; or a quadratic extension over the fourth field ^ ^ ^.
  5. 5. The method of claim 4, wherein the fifth field ^ ^ ^a is the target field.
  6. 6. The method of claim 4 or claim 5, wherein the second field ^ ^ a is a twisted field.
  7. 7. The method of claim 4 or any claim dependent thereon, wherein the script comprises a plurality of subfunctions, wherein at least one subfunction of the plurality of subfunctions is configured to perform a sub-computation in each of: the sextic extension over the second field ^ ^ a; the cubic extension over the third field ^ ^ ^; and the quadratic extension over the fourth field ^ ^ ^.
  8. 8. The method of claim 4 or any claim dependent thereon, wherein the script comprises a Miller loop subscript configured to execute a Miller function for a predefined number of inputs, wherein the Miller loop subscript is configured to compute an intermediate value, wherein the pairing is computed based on the intermediate value.
  9. 9. The method of claim 8, wherein the Miller loop subscript comprises at least one sparse vector multiplication subfunction, wherein the least one vector multiplication subfunction is executed in the cubic extension over the third field ^ ^ ^.
  10. 10. The method of claim 9, wherein the least one vector multiplication subfunction is a sparce vector multiplication subfunction.
  11. 11. The method of any of claims 8 to 10, wherein the Miller loop subscript comprises at least one point addition or point doubling subfunction, wherein the point addition or point doubling subfunction is executed in the second field ^ ^ a.
  12. 12. The method of any of claims 8 to 11, wherein the Miller loop subscript comprises at least one line subfunction, wherein the at least one line function is executed in the cubic extension over the third field ^ ^ ^.
  13. 13. The method of claim 4 or any claim dependent thereon, wherein the script comprises an exponentiation subscript is configured to verify a received candidate inverse intermediate value is equal to a target inverse intermediate value, wherein the exponentiation subscript comprises a set of subfunctions executed in the quadratic extension over the fourth field ^ ^ ^.
  14. 14. The method of claim 13 when dependent on claim 8, wherein the exponentiation subscript receives as input the intermediate value computed by the Miller loop subscript, wherein the intermediate value is an element in the cubic extension of the third field ^ ^ ^, wherein the exponentiation subscript is configured to: convert the intermediate value from an element in the cubic extension of the third field ^ ^ ^ to an element in the quadratic extension over the fourth field ^ ^ ^.
  15. 15. The method of claim 13 or claim 14, wherein the exponentiation subscript comprises a conjugate subfunction configured to compute an inverse of a unitary element in the target field.
  16. 16. The method of any of claims 13 to 15, wherein the exponentiation subscript comprises at least one exponentiate to a constant value subfunction configured to exponentiate a unitary element to the constant value via Frobenius endomorphisms, wherein the exponentiate to a constant value subfunction is configured to execute a plurality of multiplication over the second field ^ ^ a.
  17. 17. A computer-implemented method for computing a pairing, wherein the method comprises generating a script configured to execute the method of any preceding claim.
  18. 18. The method of claim 17, wherein the script is a blockchain script, wherein the method further comprises: generating a challenge blockchain transaction, wherein the challenge blockchain transaction comprises a first locking script comprising the script; and backing the challenge blockchain transaction available to one or more nodes of a blockchain network.
  19. 19. 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 18.
  20. 20. 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 18.

Description

BILINEAR PAIRINGS TECHNICAL FIELD The present disclosure relates to a computer-implemented method for computing a pairing in script. 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. Known methods for computing pairings use field arithmetic, such as Karatsuba multiplication, to minimize CPU cycles during the execution. This comes at the cost of increasing the overall number of mathematical operations, that is there are less multiplications at the cost of more additions, which are faster to execute. According to one aspect disclosed herein, there is provided a computer-implemented method for computing a pairing in script, the method comprising generating a script, wherein computing the pairing comprises at least one sub-computation executed in a target field, wherein the target field is represented as an extension field, wherein the script comprises at least one subfunction configured to perform the sub-computation as an extension over the extension field. The use of extension fields for performing portions of the pairing computation allows multiplications, instead of additions, to be implemented, and therefore the size of the script is reduced. 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 it can be said that ^ 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 point with ^ that is not ^ or ^ (i.e., −& in Figure 3, left) are needed. Likewise, to double a point ^, the tangent line ℓ"," of ^ at ^ and the vertical line $% passing through the other intersection point with ^ (−& in Figure 3, right) are needed. The formulas are given below, with the left-had formulas corresponding to point addition for ^ ≠ ^, and the right-hand formulas corresponding to point doubling for ^ + ^ ≔ 2^ . 0 ≔ ^" − ^" 3^^ ^ 0 ≔ " # − ^" 2^" If ^ ≠ ^ then ^ + ^ ≔ (^%, ^%) have ^ + ^ ≔ (^%, ^%) have coordinates: coordinates: ^ − ^ ^ ^ ^" − ^" ^% ≔ 0^ − 2^" = 1 " ^" ^ − ^ 3 − 2^"