Search

JP-7854863-B2 - Sparse multiplication calculator, mirror function calculator, pairing calculator, cryptographic calculator, sparse multiplication calculator method, and sparse multiplication calculator program

JP7854863B2JP 7854863 B2JP7854863 B2JP 7854863B2JP-7854863-B2

Inventors

  • 林田 大輝
  • 早坂 健一郎
  • 照屋 唯紀

Assignees

  • 三菱電機株式会社

Dates

Publication Date
20260507
Application Date
20220610

Claims (12)

  1. A sparse multiplication calculator that computes sparse multiplication used in the calculation of mirror functions in pairing operations on an elliptic curve with a cubic twist, wherein k is a natural number divisible by 3, e is a natural number expressible as k/3, Fp k is a finite field with p k elements having a polynomial ring representation Fp k = Fp e [v]/(v 3 - u), u is an element of Fp e , and v 3 - u is an irreducible polynomial, and the sparse multiplication calculator that computes sparse multiplication f*g with elements f and g of the finite field Fp k as input, A pre-calculation unit calculates five polynomials that associate the aforementioned element f and element g with h0 , h1 , h2 , h3 , and h4, which are the coefficients of the polynomial obtained by expressing the sparse multiplication f*g in terms of v. The equation formulation section sets up a five-dimensional linear equation to find the coefficients h₀ , h₁ , h₂ , h₃ , and h₄ of the polynomial obtained by expressing the sparse multiplication f*g in terms of v, using the five polynomials mentioned above. A sparse multiplication calculator comprising a solution unit that solves the aforementioned five-dimensional linear equation and finds h0 , h1 , h2 , h3 , and h4 which are coefficients of the polynomial obtained by expressing the sparse multiplication f*g in terms of v.
  2. The aforementioned pre-calculation unit, The sparse multiplication calculator according to claim 1, wherein the element f is a polynomial f(X) and the element g is a polynomial g(X), and using f(0), f(1), f(-1), f(2), f(∞), g(0), g(1), g(-1), g(2), g(∞) obtained by substituting predetermined values for X, the calculator calculates the five polynomials by associating each of H0 = f(0)・g(0), H1 = f(1)・g(1), H2 = f(-1)・g(-1), H3 = f(2)・g(2), and H4 = f(∞)・g(∞) with the coefficients h0, h1 , h2 , h3 , h4 of the polynomial expressed in terms of v for the sparse multiplication, with respect to each of the following:
  3. The aforementioned pre-calculation unit, The sparse multiplication calculator according to claim 1, wherein the element f is a polynomial f(X) and the element g is a polynomial g(X), and using f(0), f(1), f(-1), f(-u), f(∞), g(0), g(1), g(-1), g(-u), g(∞) obtained by substituting predetermined values for X, the calculator calculates the five polynomials by associating each of H0 = f(0)・g(0), H1 = f(1)・g(1), H2 = f(-1)・g(-1), H3 = f(-u)・g(-u), and H4 = f(∞)・g(∞) with the coefficients h0, h1 , h2 , h3 , h4 of the polynomial expressed in terms of v for the sparse multiplication, with respect to each of the following:
  4. A mirror function calculator that performs the calculation of mirror functions in pairing operations on an elliptic curve with a cubic twist, A mirror function calculator comprising a sparse multiplication calculator according to any one of claims 1 to 3.
  5. A pairing calculation device that performs pairing calculations on an elliptic curve with a cubic twist, A pairing arithmetic device comprising a mirror function calculator according to claim 4 and a final power calculator for calculating the final power.
  6. The pairing calculation device is The pairing calculation device according to claim 5, which performs pairing calculations on the BLS (Barreto-Lynn-Scott) 27 curve.
  7. The pairing calculation device is The pairing calculation device according to claim 5, which performs pairing calculations on a BLS9 curve.
  8. The pairing calculation device is The pairing calculation device according to claim 5, which performs pairing calculations on a BLS15 curve.
  9. The pairing calculation device is The pairing calculation device according to claim 5, which performs pairing calculations on the BLS21 curve.
  10. An encryption processing device comprising a pairing calculation device as described in claim 5, and an encryption processing unit that performs encryption processing using the results of the pairing calculation calculated by the pairing calculation device.
  11. A sparse multiplication calculator that computes sparse multiplication used in the calculation of mirror functions in pairing operations on an elliptic curve with a cubic twist, wherein k is a natural number divisible by 3, e is a natural number expressible as k/3, Fp k is a finite field with p k elements having a polynomial ring representation Fp k = Fp e [v]/(v 3 - u), u is an element of Fp e , and v 3 - u is an irreducible polynomial, and the sparse multiplication calculator that computes sparse multiplication f*g using elements f and g of a finite field Fp k as input, wherein the sparse multiplication calculator computes sparse multiplication f*g using elements f and g of a finite field Fp k as input, The computer calculates five polynomials that associate the elements f and g with h0, h1 , h2 , h3 , and h4, which are the coefficients of the polynomial obtained by expressing the sparse multiplication f*g in terms of v. Using the five polynomials mentioned above, we formulate a five-dimensional linear equation to find the coefficients h₀ , h₁ , h₂ , h₃ , and h ₴ of the polynomial obtained by expressing the sparse multiplication f*g in terms of v. A method for calculating sparse multiplication, which involves solving the aforementioned five-dimensional linear equation and obtaining h₀ , h₁ , h₂ , h₃ , and h ₴ , which are the coefficients of the polynomial obtained by expressing the sparse multiplication f*g in terms of v.
  12. A sparse multiplication calculator that computes sparse multiplication used in the calculation of mirror functions in pairing operations on an elliptic curve with a cubic twist, wherein k is a natural number divisible by 3, e is a natural number expressible as k/3, Fp k is a finite field with p k elements having a polynomial ring representation Fp k = Fp e [v]/(v 3 - u), u is an element of Fp e , and v 3 - u is an irreducible polynomial, and the sparse multiplication calculator program used in the calculator computes sparse multiplication f*g with elements f and g of a finite field Fp k as input, A pre-calculation process to calculate five polynomials that associate the aforementioned element f and element g with h0 , h1 , h2 , h3 , and h4, which are the coefficients of the polynomial obtained by expressing the sparse multiplication f*g in terms of v, The process involves formulating a five-dimensional linear equation to find the coefficients h₀ , h₁ , h₂ , h₃ , and h₄ of the polynomial obtained by expressing the sparse multiplication f*g in terms of v, using the five polynomials mentioned above, A sparse multiplication calculation program that causes a computer to perform a solution process to find the coefficients h0 , h1 , h2 , h3 , and h4 of the polynomial obtained by solving the aforementioned five-dimensional linear equation in terms of v.

Description

This disclosure relates to a sparse multiplication calculator, a mirror function calculator, a pairing calculator, a cryptographic calculator, a sparse multiplication calculator method, and a sparse multiplication calculator program. In particular, this disclosure relates to a sparse multiplication calculator technique in pairing operations. Pairing operations are calculations using elliptic curves that are processed internally within cryptographic schemes such as functional cryptography and secure lookup. Elliptic curves suitable for efficient pairing operations are called pairing-friendly curves. Until recently, the BN curve was known as a pairing-friendly curve equivalent to 128-bit security. BN stands for Barrett-Naehrig. However, since around 2016, security has been re-evaluated, and interest in pairing operations using various pairing-friendly curves such as the BLS curve and KSS curve has increased. BLS stands for Barreto-Lynn-Scott. KSS stands for Kachisa-Schaefer-Scott. Pairing operations can be broadly divided into two categories: the calculation of mirror functions and the calculation of the final power. The calculation of mirror functions is also called a mirror loop. Both the calculation of mirror functions and the calculation of the final power require complex computational processes and significantly impact the overall computational complexity of cryptographic schemes such as functional cryptography and secure search. Recent research has focused on BLS curves, which are considered to offer good overall efficiency in pairing operations among the many types of pairing-friendly curves. Pairing operations on BLS curves with embedding orders k = 24, 27, 42, and 48 have been extensively studied. In particular, in recent years, elliptic curves with cubic twist, as well as those with 6th-order twist, have attracted attention. A curve parameterized by the family of elliptic curves is an elliptic curve determined by a polynomial r(x), a polynomial p(x), a polynomial t(x), an embedding degree k, and an integer u. The polynomials r(x), p(x), and t(x) have different forms depending on the embedding degree k. A curve E parameterized by a family of elliptic curves of embedding degree k is an elliptic curve defined on a finite field F p consisting of p = p(x) elements. r = r(x) is the largest prime number dividing the order of the subgroup E(F p ) of the elliptic curve E. t = t(x) is the trace of the elliptic curve E. The pairing operation on an elliptic curve E is performed by taking two points P and Q on the elliptic curve E as input, calculating a rational function f called a Miller function, and then raising it to the power of (p(x) k - 1)/r(x). In other words, the pairing operation on an elliptic curve E is calculated by equation 11. Non-patent document 1 describes an efficient sparse multiplication algorithm for efficiently calculating Miller functions. To explain sparse multiplication, consider elements f and g of the extension field Fp9 . Typically, the element f (and similarly the element g) has the form shown in equation 12. Here, the coefficients f₀ , f₁ , and f₂ are elements of the intermediate field Fp3 , and v is the variable when the extension field Fp9 is expressed as the polynomial ring Fp9 = Fp3 [v]/( v3 - u). In this context, sparse multiplication of element f and element g refers to a situation where either the coefficient of element f or element g is an element of the prime field Fp. In this case, computational efficiency is better than ordinary multiplication. A. J. Devegili, C. OhEigeartigh, M. Scott and R. Dahab, “Multiplication and Squaring on Pairing-Friendly Fields” A diagram showing an example configuration of a sparse multiplication calculator according to Embodiment 1.A flowchart showing the overall operation of the sparse multiplication calculator according to Embodiment 1.A flowchart showing the calculation process for specifically calculating equations 14 and 15 according to Embodiment 1.A flowchart showing the calculation process for specifically calculating the number 20 according to Embodiment 1.A flowchart showing the calculation process for specifically calculating the number 20 according to Embodiment 1.This figure shows an example of the configuration of a sparse multiplication calculator according to a modified example 1 of Embodiment 1.This figure shows an example of the configuration of a Miller function calculator according to a modified example 3 of Embodiment 1.This figure shows an example of the configuration of a pairing calculation device according to a modified example 4 of Embodiment 1.A diagram showing an example configuration of a sparse multiplication calculator according to Embodiment 2.A flowchart showing the calculation process for specifically calculating equations 27 and 28 according to Embodiment 2.A flowchart showing the calculation process for specifically calculating the number 33 according to Embodiment 2.A flowchart showing the calculation proc