Search

EP-4736362-A1 - BILINEAR PAIRINGS

EP4736362A1EP 4736362 A1EP4736362 A1EP 4736362A1EP-4736362-A1

Abstract

A computer-implemented method for computing a pairing in script is provided. A script is generated which is configured to execute a line function and a square-and-update function. The line function computes an array of elements. The array of elements is provided as an input to the square-and-update function. The square-and-update function computes an intermediate value for computing a pairing.

Inventors

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

Assignees

  • nChain Licensing AG

Dates

Publication Date
20260506
Application Date
20240529

Claims (20)

  1. CLAIMS 1. A computer-implemented method for computing a pairing in script, the method comprising generating a script configured to: execute a line function to compute an array of elements; and execute a square-and-update function, wherein the array of elements is provided as an input to the square-and-update function, to compute an intermediate value for computing a pairing.
  2. 2. The method of claim 1 wherein the line function comprises a plurality of loops, wherein each loop comprises one of a first set of subfunctions or a second set of subfunction, wherein the set of subfunctions of a specific loop is predefined, wherein the number of loops of the line function is predefined, wherein each loop of the line function is configured to: compute a portion of the array of elements; and update a current curve point; wherein each loop of the line function receives as input the current curve point computed by a previous loop of the line function except a first loop of the line function.
  3. 3. The method of claim 2, wherein the line function further comprises: an initial curve point subfunction configured to compute an initial current curve value; wherein the initial current curve value is provided as input to the first loop of the line function.
  4. 4. The method of claim 2 or claim 3, wherein each of the plurality of loops of the line function further comprises a point doubling line subfunction configured to compute a sparse array of elements based on the current curve point, wherein the array of elements output by the line function is based at least in part on the sparse array of elements.
  5. 5. The method of any of claims 2 to 4, wherein each of the plurality of loops of the line function further comprises a point doubling subfunction configured to double a current curve point.
  6. 6. The method of claim 2 or any claim dependent thereon, wherein the number of loops of the line function is dependent on a predefined curve parameter.
  7. 7. The method of claim 6, wherein the predefined curve parameter is represented in a binary format, wherein each loop of the plurality of loops of the line function corresponds to a bit of the curve parameter, wherein: if a first curve parameter condition is met, the corresponding loop of the line function comprises the first set of subfunctions; and if a second curve parameter condition is met, the corresponding loop of the line function comprises the second set of subfunctions.
  8. 8. The method of claim 5 or any claim dependent thereon, wherein the second set of subfunctions further comprises at least one sparse vector multiplication subfunction, wherein an output of the at least one sparse vector multiplication is a somewhat sparse vector.
  9. 9. The method of claim 8, wherein the second set of subfunctions further comprises a point addition line subfunction, wherein an output of the point addition line subfunction is sparse and provided as input to the sparse vector multiplication subfunction.
  10. 10. The method of claim 9, wherein the point addition line subfunction has inputs λ and θ, wherein the second set of subfunctions of the line function further comprises: a precompute subscript for computing λ and θ; and a point addition subfunction configured to update the current curve point, wherein λ and θ are inputs for the point addition subfunction.
  11. 11. The method of claim 9 or claim 10, wherein the sparse vector multiplication subfunction comprises two inputs, wherein the inputs of the sparse vector multiplication subfunction comprise: the output of the point addition line subfunction; and an output of the point doubling line subfunction.
  12. 12. The method of claim 11, wherein the portion of the array of elements computed by each loop of the line function comprises: if the loop comprises the first set of subfunctions, the output of the point doubling line subfunction of each of the plurality of sets of subfunctions; and if the loop comprises the second set of subfunctions, an output of the sparse vector multiplication subfunction of each of the plurality of sets of subfunctions.
  13. 13. The method of claim 11, wherein the second set of subfunctions of the line function further comprises: a somewhat-sparse vector multiplication subfunction, having inputs of a first and second vector output of the sparse vector multiplication subfunction; and a second somewhat-sparse vector multiplication subfunction, having inputs of a third vector output of the sparse vector multiplication subfunction and an output of the somewhat-sparse vector multiplication subfunction; wherein the portion of the array of elements computed by a loop of the line function comprising the second set of subfunctions comprises an output of the second somewhat- sparse vector multiplication subfunction.
  14. 14. The method of any of claims 4 to 11, or claim 13, wherein first set of subfunctions of the line function further comprises: a second sparse vector multiplication subfunction having inputs of a first and second vector output of the point doubling line subfunction; and a second somewhat-sparse vector multiplication subfunction having inputs of a third vector output of the point doubling line subfunction and an output of the second sparse vector multiplication subfunction; wherein the portion of the array of elements computed by a loop of the line function comprising the first set of subfunctions comprises an output of the second somewhat- sparse vector multiplication subfunction.
  15. 15. The method of any preceding claim, wherein the square-and-update function comprises a plurality of loops, wherein each loop of the square-and-update function comprises a set of subfunctions, wherein the number of loops of the square-and-update function is predefined, wherein each loop of the square-and-update function is configured to update a current intermediate value, wherein each loop of the square-and-update function receives as input the current intermediate value computed by a previous loop of the square-and-update function except a first loop of the square-and-update function, wherein the square-and-update function further comprises: an initial intermediate value subfunction configured to compute a first current intermediate value based on the array of elements output by the line function; wherein the first current intermediate value is provided as input to the first loop of the square-and-update function.
  16. 16. The method of claim 15, wherein each loop of the square-and-update function comprises: a squaring subfunction configured to compute a square of the current intermediate value; and a multiply subfunction configured to multiply the square of the current intermediate value with the array of elements to update the current intermediate value.
  17. 17. The method of claim 15 or claim 16, wherein the number of loops of the square-and- update function is dependent on a curve parameter.
  18. 18. The method of any of claims 15 to 17, wherein the output of a final loops of the square-and-update function is the intermediate value for computing a pairing.
  19. 19. The method of any of claims 16 to 18, wherein each loop of the square-and-update function comprises one of a third set of subfunctions and a fourth set of subfunctions, wherein the set of subfunctions of a specific loop is predefined, wherein: the multiple subfunction of the third set of subfunctions is a sparse-by-dense multiplication; and the multiplication subfunction of the fourth set of subfunctions is a somewhat sparse-by-dense multiplication.
  20. 20. The method of claim 19, wherein the number of loops of the square-and-update function is dependent on a predefined curve parameter.

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. An important part of the pairing computation is the execution of a Miller loop or Miller function. The Miller function can be written as two functions, with the second taking as input the output of the first. The output of the Miller function is an intermediate value, which can be used to compute the pairing. The Miller function split in this way allows for a more efficient algorithm, and therefore reduces the computations. 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 configured to: execute a line function to compute an array of elements; and execute a square-and-update function, wherein the array of elements is provided as an input to the square-and-update function, to compute an intermediate value for computing a pairing. 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 ^^ . ^^^ − ^^^ ଶ ^^ ≔ ^^ொ − ^^^ ^^ ≔ 3 ^^^ 2 ^^^ If ^^ ≠ ^^ then ^^ + ^^ ≔ ( ^^ோ, ^^ோ) have ^^ + ^^ ≔ ( ^^ோ, ^^ோ) have coordinates: coordinates: ^^ − ^^ ଶ ଶ ^^ ≔ ^^ଶ ^ ^ ^^ − ^^ ோ − 2 ^^^ = ^ ^ − 2 ^^^ ோ ≔ ^^ଶ − ^^^ − ^^ொ