Encryption parameter setting apparatus, key generation apparatus, cryptographic system, program, encryption parameter setting method, and key generation method

US 8,401,179 B2
Filed: 01/18/2008
Issued: 03/19/2013
Est. Priority Date: 01/18/2008
Status: Active Grant

First Claim

Patent Images

1. An encryption parameter setting apparatus comprising:

a processing device for processing data;

a random divisor selection unit;

a base divisor generation unit;

a pairing log calculation unit; and

a parameter setting unit,wherein the random divisor selection unit selects an element from a plurality of elements of a cyclic group G′

, as a random divisor D*, by using the processing device;

the base divisor generation unit calculates a plurality of base divisors D^˜_jby mapping the random divisor D* by using a plurality of maps G_j, where the plurality of maps G_jare homomorphism from the cyclic group G′

to each of a plurality of cyclic groups G′

_j, based on the random divisor D* selected by the random divisor selection unit, by using the processing device;

the pairing log calculation unit calculates logarithms of pairing values of the plurality of base divisors D^˜_jin a group G, where the group G is a direct product of the plurality of cyclic groups G′

_j, and a pairing value by a bilinear pairing operation of two elements included in the group G is computable, and treats the logarithms as a plurality of pairing log coefficients η

_i, by using the processing device; and

the parameter setting unit treats the plurality of base divisors D^˜_jcalculated by the base divisor generation unit and the plurality of pairing log coefficients η

_icalculated by the pairing log calculation unit, as encryption parameters used in a cryptographic operation, by using the processing device.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A sophisticated cryptographic system is realized without using a pairing operation on a composite order. A random matrix selection unit 142 randomly selects a random matrix V* from a plurality of matrices satisfying a predetermined condition, based on a plurality of pairing log coefficients η_icalculated by an encryption parameter setting apparatus 100. An output base calculation unit 143 calculates a plurality of output bases g_k, based on a plurality of base divisors D^˜_jcalculated by the encryption parameter setting apparatus 100 and the random matrix V* selected by the random matrix selection unit 142.

Citations

23 Claims

1. An encryption parameter setting apparatus comprising:
- a processing device for processing data;
  
  a random divisor selection unit;
  
  a base divisor generation unit;
  
  a pairing log calculation unit; and
  
  a parameter setting unit,wherein the random divisor selection unit selects an element from a plurality of elements of a cyclic group G′
  
  , as a random divisor D*, by using the processing device;
  
  the base divisor generation unit calculates a plurality of base divisors D^˜_jby mapping the random divisor D* by using a plurality of maps G_j, where the plurality of maps G_jare homomorphism from the cyclic group G′
  
  to each of a plurality of cyclic groups G′
  
  _j, based on the random divisor D* selected by the random divisor selection unit, by using the processing device;
  
  the pairing log calculation unit calculates logarithms of pairing values of the plurality of base divisors D^˜_jin a group G, where the group G is a direct product of the plurality of cyclic groups G′
  
  _j, and a pairing value by a bilinear pairing operation of two elements included in the group G is computable, and treats the logarithms as a plurality of pairing log coefficients η
  
  _i, by using the processing device; and
  
  the parameter setting unit treats the plurality of base divisors D^˜_jcalculated by the base divisor generation unit and the plurality of pairing log coefficients η
  
  _icalculated by the pairing log calculation unit, as encryption parameters used in a cryptographic operation, by using the processing device.
- View Dependent Claims (2, 3, 4, 5, 6, 7)
- - 2. The encryption parameter setting apparatus according to claim 1,wherein the random divisor selection unit selects an element from a plurality of elements of a cyclic group G′
    - which is a subgroup of a group composed of divisors of a Jacobian variety Jac_cof an algebraic curve C in a finite field F_p, as a random divisor D* , by using the processing device; and
      
      the base divisor generation unit calculates the plurality of base divisors D^˜_jby treating a plurality of endomorphism maps in a group composed of divisors of a Jacobian variety Jac_Cof an algebraic curve C in an extension field K given by a finite algebraic extension of the finite field F_p, as the plurality of maps G_j, by using the processing device.
  - 3. A cryptographic system comprising:
    - an encryption parameter setting apparatus according to claim 1; and
      
      a key generation apparatus,wherein the key generation apparatus includes a second processing device for processing data, a storage device for storing data, a base divisor storage unit, a pairing log storage unit, an output base calculation unit, and a key calculation unit;
      
      the base divisor storage unit stores a plurality of base divisors D^{˜
      
      hd j}calculated by the encryption parameter setting apparatus, by using the storage device;
      
      the pairing log storage unit stores a plurality of pairing log coefficients η
      
      calculated by the encryption parameter setting apparatus, by using the storage device;
      
      the output base calculation unit calculates a plurality of output bases g_kbeing elements of the group G, where a pairing value of at least any two output bases g_kin the plurality of output bases g_kis 1, based on the plurality of base divisors D^˜_jstored by the base divisor storage unit and the plurality of pairing log coefficients n_istored by the pairing log storage unit, by using the second processing device; and
      
      the key calculation unit calculates a key to be used in a cryptographic operation, based on the plurality of output bases g_kcalculated by the output base calculation unit, by using the second processing device.
  - 4. The cryptographic system according to claim 3, further comprising a ciphertext generation apparatus;
    - and a ciphertext decryption apparatus,wherein the ciphertext generation apparatus generates a ciphertext, based on an encryption parameter set by the encryption parameter setting apparatus and a key generated by the key generation apparatus; and
      
      the ciphertext decryption apparatus decrypts the ciphertext generated by the ciphertext generation apparatus, based on the encryption parameter set by the encryption parameter setting apparatus and the key generated by the key generation apparatus.
  - 5. The cryptographic system according to claim 4, including a plurality of ciphertext decryption apparatuses, further comprising a wrongdoer tracing apparatus,wherein the key generation apparatus further includes a public key setting unit, a private key setting unit, and a tracer'"'"'s key setting unit;
    - the public key setting unit sets a public key to be used for generating a ciphertext by the ciphertext generation apparatus;
      
      the private key setting unit sets a plurality of private keys to be used for decrypting the ciphertext, generated by the ciphertext generation apparatus, by each of the plurality of ciphertext decryption apparatuses;
      
      the tracer'"'"'s key setting unit sets a tracer'"'"'s key to be used for identifying a leak source of a private key by the wrongdoer tracing apparatus;
      
      the ciphertext generation apparatus generates a ciphertext, based on the public key set by the key generation apparatus;
      
      each of the plurality of ciphertext decryption apparatuses decrypts the ciphertext generated by the ciphertext generation apparatus, based on the private key corresponding to a user of the ciphertext decryption apparatus in the plurality of private keys set by the key generation apparatus; and
      
      the wrongdoer tracing apparatus, based on the tracer'"'"'s key set by the key generation apparatus, generates a ciphertext, analyzes a decryption result of a generated ciphertext decrypted by a pirate decryption device which decrypts a ciphertext generated by the ciphertext generation apparatus, and identifies a private key having been used for decrypting the ciphertext by the pirate decryption device.
  - 6. The cryptographic system according to claim 3, further comprising a signing key issuing apparatus;
    - a plurality of signing apparatuses;
      
      a signature verification apparatus; and
      
      a signer tracing apparatus,wherein the signing key issuing apparatus generates a plurality of signing keys respectively corresponding to the plurality of signing apparatuses, based on an encryption parameter set by the encryption parameter setting apparatus and a key generated by the key generation apparatus;
      
      at least any signing apparatus of the plurality of signing apparatuses generates a signature by using a signing key corresponding to the signing apparatus in the plurality of signing keys generated by the signing key issuing apparatus;
      
      the signature verification apparatus verifies the signature generated by the signing apparatus, by using the encryption parameter set by the encryption parameter setting apparatus and the key generated by the key generation apparatus; and
      
      the signer tracing apparatus analyzes the signature generated by the signing apparatus, and identifies the signing apparatus used for generating the signature, by using the encryption parameter set by the encryption parameter setting apparatus and the key generated by the key generation apparatus.
  - 7. A non-transitory computer readable storage medium having stored therein computer executable instructions that cause a computer, having a processing device for processing data, to operate as the encryption parameter setting apparatus according to claim 1.

8. An encryption parameter setting apparatus comprising:
- a processing device for processing data;
  
  a random divisor selection unit;
  
  a base divisor generation unit;
  
  a discrete log calculation unit;
  
  a pairing log calculation unit; and
  
  a parameter setting unit,wherein the random divisor selection unit selects a random divisor D* from a plurality of divisors of a Jacobian variety Jac_Cof an algebraic curve C of genus d in a finite field F_p, where an order p of the finite field F_pis a prime number, and the genus d is an integer greater than or equal to 2, by using the processing device;
  
  the base divisor generation unit calculates a plurality of base divisors D^˜_j, based on the random divisor D* selected by the random divisor selection unit, by using the processing device;
  
  the discrete log calculation unit calculates a plurality of discrete logs l_K, by using the processing device;
  
  the pairing log calculation unit calculates a plurality of pairing log coefficients η
  
  _i, based on the plurality of discrete logs l_kcalculated by the discrete log calculation unit, by using the processing device; and
  
  the parameter setting unit sets an encryption parameter to be used in a cryptographic operation, based on the plurality of base divisors D^˜_jcalculated by the base divisor generation unit and the plurality of pairing log coefficients η
  
  _icalculated by the pairing log calculation unit, by using the processing device.
- View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
- - 9. The encryption parameter setting apparatus according to claim 8,wherein the random divisor selection unit selects a random divisor D* from a plurality of divisors of a Jacobian variety Jac_Cof a hyperelliptic curve C:
    - Y²=X^w+1, where w is a prime number of w=2d+1, and a remainder a of the order p divided by the prime number w is a generator of a multiplicative group F_W* of a finite field F_Wwhose order is W, in the finite field F_p, by using the processing device;
      
      the base divisor generation unit calculates, by applying Gauss sum operators G_jto the random divisor D* , where j is an integer greater than or equal to 0 and less than or equal to 2d-1, the Gauss sum operators G_jis an operation on a Jacobian variety Jac_Cin an extension field K shown in Expression 1, and the extension field K is an algebraic extension field given by a 2d-th order extension of the finite field F_p, a plurality of base divisors D^˜_j=G_j(D* ) of the Jacobian variety Jac_Cin the extension field K, based on the random divisor D* selected by the random divisor selection unit, by using the processing device;
      
      the discrete log calculation unit calculates a plurality of discrete logs l_Ksatisfying Expression 2, where K is an integer greater than or equal to 1 and less than or equal to 2d-1, and the plurality of discrete logs l_Kare integers greater than or equal to 0 and less than or equal to 2d-1, based on the remainder a, by using the processing device; and
      
      the pairing log calculation unit calculates a plurality of pairing log coefficients η
      
      _i, where i is an integer greater than or equal to 0 and less than or equal to 2d-1, the plurality of pairing log coefficients η
      
      _iare integers greater than or equal to 0 and less than or equal to r-1, and r is an order of the random divisor D* , by calculating an expression shown in Expression 3, based on the plurality of discrete logs l_Kcalculated by the discrete log calculation unit, by using the processing device.
  - 10. A key generation apparatus comprising:
    - a processing device for processing data;
      
      a storage device for storing data;
      
      a base divisor storage unit;
      
      a pairing log storage unit;
      
      a random matrix selection unit;
      
      an output base calculation unit; and
      
      a key calculation unit,wherein the base divisor storage unit stores a plurality of base divisors D^˜_jcalculated by an encryption parameter setting apparatus according to claim 9, by using the storage device;
      
      the pairing log storage unit stores a plurality of pairing log coefficients η
      
      _icalculated by the encryption parameter setting apparatus, by using the storage device;
      
      the random matrix selection unit randomly selects a random matrix V* from a plurality of matrices V satisfying a relational expression M′
      
      =V·
      
      M·
      
      V^T, where M′
      
      is a b-dimensional square matrix in which an integer m′
      
      _μ
      
      ν is a μ
      
      -th row and ν
      
      -th column element, V is a b row by 2d column matrix in which a variable c_μ
      
      νwhose value is an integer greater than or equal to 0 and less than or equal to r−
      
      1 is a μ
      
      -th row and ν
      
      -th column element, V^Tis a 2d row by b column matrix transposed from the matrix V, M is a 2d-dimensional square matrix in which an integer m_μ
      
      ν is a μ
      
      -th row and ν
      
      -th column element, and the integer m_μ
      
      ν is η
      
      _ν
      
      +1when μ
      
      +ν
      
      =2d+1 and 0 when μ
      
      +ν
      
      ≠
      
      2d+1, based on a predetermined condition that should be satisfied by a plurality of integers m′
      
      _μ
      
      ν where μ and
      
      ν
      
      are integers greater than or equal to 1 and less than or equal to b, and b is an integer greater than or equal to 2 and less than or equal to 2d, by using the processing device;
      
      the output base calculation unit calculates a plurality of output bases g_k=v_k·
      
      D^˜, where k is an integer greater than or equal to 1 and less than or equal to b, g_kis a divisor of a Jacobian variety Jac_Cin the extension field K, ν
      
      _kis a k-th row vector of the random matrix V*, and D^˜ is a 2d-dimensional column vector which uses the plurality of base divisors D^˜_jas a (j+1)th row element, based on the plurality of base divisors D^˜_jstored by the base divisor storage unit and the random matrix V* selected by the random matrix selection unit, by using the processing device; and
      
      the key calculation unit calculates a key to be used in a cryptographic operation, based on the plurality of output bases g_kcalculated by the output base calculation unit and the random matrix V* selected by the random matrix selection unit, by using the processing device.
  - 11. The key generation apparatus according to claim 10, further comprising a consistent condition input unit,wherein the consistent condition input unit inputs an integer pair (μ
    - ,ν
      
      ) indicating an output base pair whose pairing value e(g_μ,g_ν) of an output base g_μ and an output base g_ν in the plurality of output bases g_kshould be 1, by using the processing device; and
      
      the random matrix selection unit selects a random matrix V* satisfying a condition m′
      
      _μ
      
      ν=0, based on the integer pair (μ
      
      ,ν
      
      ) input by the consistent condition input unit, by using the processing device.
  - 12. The key generation apparatus according to claim 10, further comprising an inconsistent condition input unit,wherein the inconsistent condition input unit inputs an integer pair (μ
    - ,ν
      
      ) indicating an output base pair whose pairing value e(g_μ,g_ν) of an output base g_μ and an output base g_ν in the plurality of output bases g_kshould not be 1, by using the processing device; and
      
      the random matrix selection unit selects a random matrix V* satisfying a condition m′
      
      _μ
      
      ν≠
      
      0, based on the integer pair (μ
      
      ,ν
      
      ) input by the inconsistent condition input unit, by using the processing device.
  - 13. A cryptographic system comprising:
    - an encryption parameter setting apparatus according to claim 9;
      
      a key generation apparatus;
      
      a ciphertext generation apparatus; and
      
      a ciphertext decryption apparatus;
      
      wherein the key generation apparatus includes a second processing device for processing data, a storage device for storing data, a base divisor storage unit, a pairing log storage unit, a random matrix selection unit, an output base calculation unit, and a key calculation unit;
      
      the base divisor storage unit stores a plurality of base divisors D^˜_jcalculated by the encryption parameter setting apparatus, by using the storage device;
      
      the pairing log storage unit stores a plurality of pairing log coefficients n_jcalculated by the encryption parameter setting apparatus, by using the storage device;
      
      the random matrix selection unit randomly selects a random matrix V* from a plurality of matrices V satisfying a relational expression M′
      
      =V·
      
      M·
      
      V^T, where M′
      
      is a b-dimensional square matrix in which an integer m′
      
      _μ
      
      ν is a μ
      
      -th row and ν
      
      -th column element, V is a b row by 2d column matrix in which a variable c_μ
      
      ν, whose value is an integer greater than or equal to 0 and less than or equal to r−
      
      1 is a μ
      
      -th row and ν
      
      -th column element, V^Tis a 2d row by b column matrix transposed from the matrix V, M is a 2d-dimensional square matrix in which an integer m_μ
      
      ν
      
      ν is a μ
      
      -th row and ν
      
      -th column element, and the integer m_μ
      
      ν is η
      
      _ν
      
      +1 when μ
      
      +ν
      
      =2d+and 0 when μ
      
      +ν
      
      ≠
      
      2d+1, based on a predetermined condition that should be satisfied by a plurality of integers m′
      
      _μ
      
      ν, where μ and
      
      ν
      
      are integers greater than or equal to 1 and less than or equal to b, and b is an integer greater than or equal to 2 and less than or equal to 2d, by using the second processing device;
      
      the output base calculation unit calculates a plurality of output bases g_k=v_k·
      
      D^˜, where k is an integer greater than or equal to 1 and less than or equal to b, g_kis a divisor of a Jacobian variety Jac_Cin the extension field K, v_kis a k-th row vector of the random matrix V*, and D^˜ is a 2d-dimensional column vector which uses the plurality of base divisors D^˜_jas a (j+1)th row element, based on the plurality of base divisors D^˜_jstored by the base divisor storage unit and the random matrix V* selected by the random matrix selection unit, by using the second processing device;
      
      the key calculation unit calculates a key to be used in a cryptographic operation, based on the plurality of output bases g_kcalculated by the output base calculation unit and the random matrix V* selected by the random matrix selection unit, by using the second processing device;
      
      the random divisor selection unit selects a random divisor D* from a plurality of divisors of a Jacobian variety Jac_Cof a hyperelliptic curve C;
      
      Y²=X⁵+1, where a remainder a of a prime number p divided by 5 is 2 or 3, in a finite field F_p, by using the processing device;
      
      the random matrix selection unit selects a random matrix V* of 4 row by 4 column satisfying a condition;
      
      m′
      
      ₁₂=m′
      
      ₂₁=m′
      
      ₃₄=m′
      
      ₄₃=m′
      
      ₁₄=m′
      
      ₄₁=m′
      
      ₂₃=m′
      
      ₃₂=0, m′
      
      ₁₁≠
      
      0, m′
      
      ₂₂≠
      
      0, and m′
      
      ₃₃≠
      
      0, and m′
      
      ₄₄≠
      
      0, by using the second processing device;
      
      the output base calculation unit calculates four output bases g_k=v_k·
      
      D^˜, where k is an integer greater than or equal to 1 and less than or equal to 4, based on the plurality of base divisors D^˜_jstored by the base divisor storage unit and the random matrix V* calculated by the random matrix selection unit, by using the second processing device;
      
      the key calculation unit includes a number-of-users input unit, a public row base calculation unit, a public column base calculation unit, a row random number generation unit, a column random number generation unit, a pairing random number generation unit, a common random number generation unit, a public common divisor calculation unit, a public row first divisor calculation unit, a public row second divisor calculation unit, a public pairing value calculation unit, a public column divisor calculation unit, a public key setting unit, a private divisor calculation unit, and a private key setting unit;
      
      the number-of-users input unit inputs an integer n₁and an integer n₂, where n=n₁n₂, indicating n being a number of users, by using the second processing device;
      
      the public row base calculation unit calculates a divisor g=g₁+g₂of the Jacobian variety Jac_C, based on an output base g₁and an output base g₂calculated by the output base calculation unit, by using the second processing device;
      
      the public column base calculation unit calculates a divisor h=g₃+g₄of the Jacobian variety Jac_C, based on an output base g₃and an output base g₄calculated by the output base calculation unit, by using the second processing device;
      
      the row random number generation unit randomly generates n₁random numbers r_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number r_xis an integer greater than or equal to 1 and less than or equal to r−
      
      1, based on the integer n₁input by the number-of-users input unit, by using the second processing device;
      
      the column random number generation unit randomly generates n₂random numbers c_y, where y is an integer greater than or equal to 1 and less than or equal to n₂, and the random number c_yis an integer greater than or equal to 1 and less than or equal to r−
      
      1, based on the integer n₂input by the number-of-users input unit, by using the second processing device;
      
      the pairing random number generation unit randomly generates n₁random numbers α
      
      _x, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number α
      
      _xis an integer greater than or equal to 1 and less than or equal to r−
      
      1, based on the integer n₁input by the number-of-users input unit, by using the second processing device;
      
      the common random number generation unit randomly generates a random number β
      
      , where the random number β
      
      is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the second processing device;
      
      the public common divisor calculation unit calculates a divisor E=β
      
      ·
      
      g₂of the Jacobian variety Jac_C, based on the output base g₂calculated by the output base calculation unit and the random number β
      
      generated by the common random number generation unit, by using the second processing device;
      
      the public row first divisor calculation unit calculates n₁divisors E_x=β
      
      ·
      
      r_x·
      
      g₂, where x is an integer greater than or equal to 1 and less than or equal to n₁, of the Jacobian variety Jac_C, based on the output base g₂calculated by the output base calculation unit, the n₁random numbers r_xgenerated by the row random number generation unit, and the random number β
      
      generated by the common random number generation unit, by using the second processing device;
      
      the public row second divisor calculation unit calculates n₁divisors F_x=β
      
      ·
      
      r_x·
      
      g₄, where x is an integer greater than or equal to 1 and less than or equal to n₁, of the Jacobian variety Jac_C, based on the output base g₄calculated by the output base calculation unit, the n₁random numbers r_xgenerated by the row random number generation unit, and the random number β
      
      generated by the common random number generation unit, by using the second processing device;
      
      the public pairing value calculation unit calculates n₁pairing values G_x=e(g₄,g₄)^β
      
      ·
      
      α_x, where the pairing e is e(D,D′
      
      )=e_W(D,φ
      
      (D′
      
      ), e_Wis a Weil pairing, and φ
      
      is a calculable homomorphism mapping on the Jacobian variety Jac_C), based on the output base g₂calculated by the output base calculation unit, the n₁random numbers α
      
      _xgenerated by the pairing random number generation unit, and the random number β
      
      generated by the common random number generation unit, by using the second processing device;
      
      the public column divisor calculation unit calculates n₂divisors H_y=c_y·
      
      g, where y is an integer greater than or equal to 1 and less than or equal to n₂, of the Jacobian variety Jac_C, based on the divisor g calculated by the public row base calculation unit and the n₂random numbers c_ygenerated by the column random number generation unit, by using the second processing device;
      
      the public key setting unit sets a public key PK=(g,h,E,E_x,F_x,G_x,H_y), where x is an integer greater than or equal to 1 and less than or equal to n₁, and y is an integer greater than or equal to 1 and less than or equal to n₂, based on the divisor g calculated by the public row base calculation unit, the divisor h calculated by the public column base calculation unit, the divisor E calculated by the public common divisor calculation unit, the n₁divisors E_xcalculated by the public row first divisor calculation unit, the n₁divisors F_xcalculated by the public row second divisor calculation unit, the n₁pairing values G_xcalculated by the public pairing value calculation unit, and the n₂divisors H_ycalculated by the public column divisor calculation unit, by using the second processing device;
      
      the private divisor calculation unit calculates n divisors K_x,y=α
      
      _x·
      
      g+r_xc_y·
      
      g , where x is an integer greater than or equal to 1 and less than or equal to n₁, and y is an integer greater than or equal to 1 and less than or equal to n₂, based on the divisor g calculated by the public row base calculation unit, the n₁random numbers r_xgenerated by the row random number generation unit, the n₂random numbers c_ygenerated by the column random number generation unit, and the n₁random numbers α
      
      _xgenerated by the pairing random number generation unit, by using the second processing device;
      
      the private key setting unit sets n private keys SK_x,y=(K_x,y) respectively corresponding to n users, based on the n divisors K_x,ycalculated by the private divisor calculation unit, by using the second processing device;
      
      the ciphertext generation apparatus includes a third processing device for processing data, a public key input unit, a plaintext input unit, an encryption common random number generation unit, an encryption column random number generation unit, an encryption row random number generation unit, an encryption row first divisor calculation unit, an encryption row second divisor calculation unit, an encryption row third divisor calculation unit, an encryption key calculation unit, a plaintext encryption unit, a row ciphertext setting unit, an encryption column first divisor calculation unit, an encryption column second divisor calculation unit, and a column ciphertext setting unit;
      
      the public key input unit inputs the public key PK=(g,h,E,E_x,F_x,G_x,H_y) set by the key generation apparatus, by using the third processing device;
      
      the plaintext input unit inputs a plaintext M to be encrypted, by using the third processing device;
      
      the encryption common random number generation unit randomly generates a random number t, where the random number t is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the third processing device;
      
      the encryption column random number generation unit generates n₂or less random numbers w_y, where y is an integer greater than or equal to 1 and less than or equal to n₂, and the random number w_yis an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the third processing device;
      
      the encryption row random number generation unit generates n₁or less random numbers s_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number s_xis an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the third processing device;
      
      the encryption row first divisor calculation unit calculates n₁or less divisors R_x=s_x·
      
      E_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, of a Jacobian variety Jac_C, based on the n₁divisors E_xincluded in the public key PK input by the public key input unit and the n₁or less random numbers s_xgenerated by the encryption row random number generation unit, by using the third processing device;
      
      the encryption row second divisor calculation unit calculates n₁or less divisors R^˜_x=s_x·
      
      F_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, of the Jacobian variety Jac_C, based on the n₁divisors F_xincluded in the public key PK input by the public key input unit, and the n₁or less random numbers s_xgenerated by the encryption row random number generation unit, by using the third processing device;
      
      the encryption row third divisor calculation unit calculates n₁or less divisors A_x=s_xt·
      
      E, where x is an integer greater than or equal to 1 and less than or equal to n₁, of the Jacobian variety Jac_C, based on the divisor E included in the public key PK input by the public key input unit, the random number t generated by the encryption common random number generation unit, and the n₁or less random numbers s_xgenerated by encryption row random number generation unit, by using the third processing device;
      
      the encryption key calculation unit calculates n₁or less pairing values CK_x=G_x^s_x^t, where x is an integer greater than or equal to 1 and less than or equal to n₁, based on the n₁pairing values G_xincluded in the public key PK input by the public key input unit, the random number t generated by the encryption common random number generation unit, and the n₁or less random numbers s_xgenerated by the encryption column random number generation unit, by using the third processing device;
      
      the plaintext encryption unit generates, based on the plaintext M input by the plaintext input unit and the n₁or less pairing values CK_xcalculated by the encryption key calculation unit, n₁or less ciphertexts B_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, by encrypting the plaintext M by respectively using the n₁or less pairing values CK_xas encryption keys, by using the third processing device;
      
      the row ciphertext setting unit sets n₁or less row ciphertexts CT_x=(R_x,R^˜_x,A_x,B_x), where x is an integer greater than or equal to 1 and less than or equal to n₁, based on the n₁or less divisors R_xcalculated by the encryption row first divisor calculation unit, the n₁or less divisors R^˜_xcalculated by the encryption row second divisor calculation unit, the n₁or less divisors A_xcalculated by the encryption row third divisor calculation unit, and the n₁or less ciphertexts B_xgenerated by the plaintext encryption unit, by using the third processing device;
      
      the encryption column first divisor calculation unit calculates n₂or less divisors C_y=t·
      
      H_y+w_y·
      
      h, where y is an integer greater than or equal to 1 and less than or equal to n₂, of the Jacobian variety Jac_C, based on the divisors h and H_yincluded in the public key PK input by the public key input unit, the random number t generated by the encryption common random number generation unit, and the random number w_ygenerated by the encryption column random number generation unit, by using the third processing device;
      
      the encryption column second divisor calculation unit calculates n₂or less divisors C^˜_y=w_y·
      
      g, where y is an integer greater than or equal to 1 and less than or equal to n₂, of the Jacobian variety Jac_C, based on the divisor g included in the public key PK input by the public key input unit and the random number w_ygenerated by the encryption column random number generation unit, by using the third processing device;
      
      the column ciphertext setting unit sets n₂or less column ciphertexts CT_y=(C_y,C^˜_y), where y is an integer greater than or equal to 1 and less than or equal to n₂, based on the n₂or less divisors C_ycalculated by the encryption column first divisor calculation unit and the n₂or less divisors C^˜_ycalculated by the encryption column second divisor calculation unit, by using the third processing device;
      
      the ciphertext decryption apparatus includes a second storage device for storing data, a fourth processing device for processing data, a private key storage unit, a row ciphertext input unit, a column ciphertext input unit, a decryption key calculation unit, and a ciphertext decryption unit;
      
      the private key storage unit stores a private key SK_X,Y=(K_X,Y) corresponding to predetermined indexes X and Y, where X is an integer greater than or equal to 1 and less than or equal to n₁and Y is an integer greater than or equal to 1 and less than or equal to n₂, corresponding to a user of the ciphertext decryption apparatus, in the n private keys SK_x,yset by the key generation apparatus, by using the second storage device;
      
      the row ciphertext input unit inputs a row ciphertext CT_X=(R_X,R^˜_X,A_X,B_X) corresponding to the index X, in the n₁or less row ciphertexts CT_xset by the ciphertext generation apparatus, by using the fourth processing device;
      
      the column ciphertext input unit inputs a column ciphertext CT_Y=(C_Y,C^˜_Y) corresponding to the index Y, in the n₂or less column ciphertexts CT_yset by the ciphertext generation apparatus, by using the fourth processing device;
      
      the decryption key calculation unit calculates a pairing value CK′
      
      =e(K_X,Y,A_X)·
      
      e(R^˜_X,C^˜_Y)/e(C_Y,R_X), based on the private key SK_X,Ystored by the private key storage unit, the divisors R_x, R^˜_xand A_xincluded in the row ciphertext CT_Xinput by the row ciphertext input unit, the divisors C_yand C^˜_yincluded in the column ciphertext CT_yinput by the column ciphertext input unit, by using the fourth processing device; and
      
      the ciphertext decryption unit generates, based on a ciphertext B_Xincluded in the row ciphertext CT_xinput by the row ciphertext input unit and the pairing value CK′
      
      calculated by the decryption key calculation unit, a decrypted text M′
      
      by decrypting the ciphertext B_xby using the pairing value CK′
      
      as a decryption key, by using the fourth processing device.
  - 14. The cryptographic system according to claim 13, including a plurality of ciphertext decryption apparatuses, further comprising a wrongdoer tracing apparatus,wherein the key calculation unit further includes a tracer'"'"'s key setting unit;
    - the tracer'"'"'s key setting unit sets a tracer'"'"'s key TK=(g_k,r_x,α
      
      _x,c_y), where k is an integer greater than or equal to 1 and less than or equal to 4, x is an integer greater than or equal to 1 and less than or equal to n₁, and y is an integer greater than or equal to 1 and less than or equal to n₂, based on the four output bases g_kcalculated by the output base calculation unit, the n₁random numbers r_xgenerated by the row random number generation unit, the n₁random numbers α
      
      _xgenerated by the pairing random number generation unit, and the n₂random numbers c_ygenerated by the column random number generation unit, by using the second processing device;
      
      the wrongdoer tracing apparatus includes a third storage device for storing data, a fifth processing device for processing data, a tracer'"'"'s key storage unit, a target determination unit, a tracing plaintext generation unit, a tracing common random number generation unit, a tracing column random number generation unit, a tracing row random number generation unit, a disturbance row random number generation unit, a disturbance column random number generation unit, a tracing row first divisor calculation unit, a tracing row second divisor calculation unit, a tracing row third divisor calculation unit, a tracing encryption key calculation unit, a tracing plaintext encryption unit, a tracing row ciphertext setting unit, a tracing column first divisor calculation unit, a tracing column second divisor calculation unit, a tracing column ciphertext setting unit, a decrypted text input unit, and a leak source identification unit;
      
      the tracer'"'"'s key storage unit stores the tracer'"'"'s key TK=(g_k,r_x,α
      
      _x,c_y) set by the key generation apparatus, by using the third storage device;
      
      the target determination unit classifies the index x into three groups and the index y into two groups, by using the fifth processing device;
      
      the tracing plaintext generation unit generates a plaintext M by using the fifth processing device;
      
      the tracing common random number generation unit randomly generates a random number t, where the random number t is an integer greater than or equal to 1 and less than or equal to r, by using the fifth processing device;
      
      the tracing column random number generation unit randomly generates n₂or less random numbers w_y, where y is an integer greater than or equal to 1 and less than or equal to n₂, and the random number w_yis an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the fifth processing device;
      
      the tracing row random number generation unit randomly generates n₁or less random numbers s_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number s_xis an integer greater than or equal to 1 and less than or equal to r−
      
      1 by using the fifth processing device;
      
      the disturbance row random number generation unit randomly generates n₁or less random numbers v_x,1, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number v_x,1is an integer greater than or equal to 1 and less than or equal to r−
      
      1, n₁or less random numbers v_x,2, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number v_x,2is an integer greater than or equal to 1 and less than or equal to r−
      
      1, and n₁or less random numbers v_x,3, where x is an integer greater than or equal to 1 and less than or equal to n₁, and the random number v_x,3is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the fifth processing device;
      
      the disturbance column random number generation unit randomly generates n₂or less random numbers z_p,y, where y is an integer greater than or equal to 1 and less than or equal to n₂, and the random number z_p,yis an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the fifth processing device;
      
      the tracing row first divisor calculation unit calculates a divisor R_x=s_xr_x·
      
      g₂, where x is an integer greater than or equal to 1 and less than or equal to n_l, with respect to the index x belonging to a first group in the three groups, a divisor R_x=s_xr_x·
      
      (g₁+g₂), where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to a second group in the three groups, and a divisor R_x=v_x,1·
      
      (g₁+g₂), where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to a third group in the three groups, based on divisors g₁and g₂and the n₁random numbers r_xincluded in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit, the three groups of the index x classified by the target determination unit, the n₁or less random numbers s_xgenerated by the tracing row random number generation unit, and the n₁or less random numbers v_x,1generated by the disturbance row random number generation unit, by using the fifth processing device;
      
      the tracing row second divisor calculation unit calculates a divisor R^˜_x=s_xr_x·
      
      g₄, where x is an integer greater than or equal to 1 and less than or equal to n_l, with respect to the index x belonging to the first group in the three groups, a divisor R^˜_xs_xr_x·
      
      (g₃+g₄), where x is an integer greater than or equal to 1and less than or equal to n₁, with respect to the index x belonging to the second group in the three groups, and a divisor R^˜_x=v_x,1·
      
      (g₃+g₄), where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the third group in the three groups, based on divisors g₃and g₄and the n₁random numbers r_xincluded in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit, the three groups of the index x classified by the target determination unit, the n₁or less random numbers s_xgenerated by the tracing row random number generation unit, and the n₁or less random numbers v_x,1generated by the disturbance row random number generation unit, by using the fifth processing device;
      
      the tracing row third divisor calculation unit calculates a divisor A_x=s_xt·
      
      g₂, where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the first group in the three groups, a divisor A_x=s_xt·
      
      (g₁+g₂), where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the second group in the three groups, and a divisor A_x=v_x,2·
      
      (g₁+g₂), where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the third group in the three groups, based on the divisors g₁and g₂included in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit, the three groups of the index x classified by the target determination unit, the random number t generated by the tracing common random number generation unit, the n₁or less random numbers s_xgenerated by the tracing row random number generation unit, and the n₁or less random numbers v_x,2generated by the disturbance row random number generation unit, by using the fifth processing device;
      
      the tracing encryption key calculation unit calculates a pairing value CK_x=e(g₂,g₂)^α_x^s_x^t, where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the first group in the three groups, a pairing value CK_x=e(g₁+g₂,g₁+g₂) ^α_x^s_x^t, where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the second group in the three groups, and a pairing value CK_x+e(g₁+g₂,g₁+g₂)^ν_x,2, where x is an integer greater than or equal to 1 and less than or equal to n₁, with respect to the index x belonging to the third group in the three groups, based on the divisors g₁and g₂and the n₁random numbers α
      
      _xincluded in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit, the three groups of the index x classified by the target determination unit, the n₁or less random numbers s_xgenerated by the tracing row random number generation unit, and the n₁or less random numbers v_x,3generated by the disturbance row random number generation unit, by using the fifth processing device;
      
      the tracing plaintext encryption unit generates n₁or less ciphertexts B_x, where x is an integer greater than or equal to 1 and less than or equal to n₁, by encrypting the plaintext M by respectively using the n₁or less pairing values CK_xas encryption keys, based on the n₁or less pairing values CK_xcalculated by the tracing encryption key calculation unit and the plaintext M generated by the tracing plaintext generation unit, by using the fifth processing device;
      
      the tracing row ciphertext setting unit sets n₁or less row ciphertexts CT_x=(R_x,R^˜_x,A_x,B_x), where x is an integer greater than or equal to 1 and less than or equal to n₁, based on n₁or less divisors R_xcalculated by the tracing row first divisor calculation unit, n1 or less divisors R^˜_xcalculated by the tracing row second divisor calculation unit, n₁or less divisors A_xcalculated by the tracing row third divisor calculation unit, and the n₁or less ciphertexts B_xgenerated by the tracing plaintext encryption unit, by using the fifth processing device;
      
      the tracing column first divisor calculation unit calculates a divisor C_y=tc_y·
      
      (g₁+g₂)+w_y·
      
      (g₃+g₄), where y is an integer greater than or equal to 1 and less than or equal to n₂, with respect to the index y belonging to a first group in the two groups, and a divisor C_y=tc_y·
      
      (g₃+g₄)+z_p,y·
      
      g₁+w_y·
      
      (g₃+g₄), where y is an integer greater than or equal to 1 and less than or equal to n₂, with respect to the index y belonging to a second group in the two groups, based on the divisors g₁, g₂, g₃, and g₄, and the n₂random numbers c_yincluded in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit, the two groups of the index y classified by the target determination unit, the random number t generated by the tracing common random number generation unit, the n₂or less random numbers w_ygenerated by the tracing column random number generation unit, and the n2 or less random numbers z_p,ygenerated by the disturbance column random number generation unit, by using the fifth processing device;
      
      the tracing column second divisor calculation unit calculates n₂or less C^˜_y=w_y·
      
      (g₁+g₂), where y is an integer greater than or equal to 1 and less than or equal to n₂, based on the divisors g₁and g₂included in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit, and the n₂or less random numbers w_ygenerated by the tracing column random number generation unit, by using the fifth processing device;
      
      the tracing column ciphertext setting unit sets n₂or less column ciphertexts CT_y=(C_y,C^˜_y), where y is an integer greater than or equal to 1 and less than or equal to n₂, based on the n₂or less divisors C_ycalculated by the tracing column first divisor calculation unit, and the n₂or less divisors C^˜_ycalculated by the tracing column second divisor calculation unit, by using the fifth processing device;
      
      the decrypted text input unit inputs a decrypted text M′
      
      generated by decrypting a ciphertext, including the n₁or less row ciphertexts CT_xset by the tracing row ciphertext setting unit and the n₂or less column ciphertexts CT_yset by the tracing column ciphertext setting unit, by the pirate decryption device which decrypts a ciphertext generated by the ciphertext generation apparatus, by using the fifth processing device; and
      
      the leak source identification unit identifies a private key K_x,yhaving been used for decryption by the pirate decryption device, by comparing the plaintext M generated by the tracing plaintext generation unit and the decrypted text M′
      
      input by the decrypted text input unit, by using the fifth processing device.
  - 15. A cryptographic system comprising:
    - an encryption parameter setting apparatus according to claim 9;
      
      a key generation apparatus;
      
      a signing key issuing apparatus;
      
      a plurality of signing apparatuses;
      
      a signature verification apparatus; and
      
      a signer tracing apparatus;
      
      wherein the key generation apparatus includes a second processing device for processing data, a storage device for storing data, a base divisor storage unit, a pairing log storage unit, a random matrix selection unit, an output base calculation unit, and a key calculation unit;
      
      the base divisor storage unit stores a plurality of base divisors D^˜_jcalculated by the encryption parameter setting apparatus, by using the storage device;
      
      the pairing log storage unit stores a plurality of pairing log coefficients n_jcalculated by the encryption parameter setting apparatus, by using the storage device;
      
      the random matrix selection unit randomly selects a random matrix V* from a plurality of matrices V satisfying a relational expression M′
      
      =V·
      
      M·
      
      V^T, where M′
      
      is a b-dimensional square matrix in which an integer m′
      
      _μ
      
      ν is a μ
      
      -th row and ν
      
      -th column element, V is a b row by 2d column matrix in which a variable c_μ
      
      ν whose value is an integer greater than or equal to 0 and less than or equal to r−
      
      1 is a μ
      
      -th row and ν
      
      -th column element, V^Tis a 2d row by b column matrix transposed from the matrix V, M is a 2d-dimensional square matrix in which an integer m_μ
      
      ν is a μ
      
      -th row and ν
      
      -th column element, and the integer m_μ
      
      ν is η
      
      _ν
      
      +1when μ
      
      +ν
      
      =2d+1 and 0 when μ
      
      +ν
      
      ≠
      
      2d+1, based on a predetermined condition that should be satisfied by a plurality of integers m′
      
      _μ
      
      ν, where μ and
      
      ν
      
      are integers greater than or equal to 1 and less than or equal to b, and b is an integer greater than or equal to 2 and less than or equal to 2d, by using the second processing device;
      
      the output base calculation unit calculates a plurality of output bases g_k=v_k·
      
      D^˜, where k is an integer greater than or equal to 1 and less than or equal to b, g_kis a divisor of a Jacobian variety Jac_Cin the extension field K, v_kis a k-th row vector of the random matrix V*, and D^˜is a 2d-dimensional column vector which uses the plurality of base divisors D^˜_jas a (j+1)th row element, based on the plurality of base divisors D^˜_jstored by the base divisor storage unit and the random matrix V* selected by the random matrix selection unit, by using the second processing device;
      
      the key calculation unit calculates a key to be used in a cryptographic operation, based on the plurality of output bases g_kcalculated by the output base calculation unit and the random matrix V* selected by the random matrix selection unit, by using the second processing device;
      
      the random divisor selection unit selects a random divisor D* from a plurality of divisors of a Jacobian variety Jac_Cof a hyperelliptic curve C;
      
      Y²=X⁵+1, where a remainder a of a prime number p divided by 5 is 2 or 3, in a finite field F_p, by using the processing device;
      
      the random matrix selection unit selects a random matrix V* of 2 row by 2 column satisfying a condition;
      
      m′
      
      ₁₂=m′
      
      ₂₁=0,m′
      
      ₁₁≠
      
      0, and m′
      
      ₂₂≠
      
      0, by using the second processing device;
      
      the output base calculation unit calculates two output bases g_k=v_k·
      
      D^˜, where k is an integer greater than or equal to 1 and less than or equal to 2, based on a plurality of base divisors D^˜_jstored by the base divisor storage unit and the random matrix V* calculated by the random matrix selection unit, by using the second processing device;
      
      the key calculation unit includes a bit length input unit, a base random number generation unit, a pairing random number generation unit, a master random number generation unit, a public base calculation unit, a public first divisor calculation unit, a public pairing value calculation unit, a public second divisor generation unit, a public third divisor generation unit, a public bit divisor generation unit, a master divisor calculation unit, a public key setting unit, a master key setting unit, and a tracer'"'"'s key setting unit;
      
      the bit length input unit inputs a bit length m of a message to be signed, by using the second processing device;
      
      the base random number generation unit randomly generates a random number β
      
      , where the random number β
      
      is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the second processing device;
      
      the pairing random number generation unit randomly generates a random number α
      
      , where the random number α
      
      is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the second processing device;
      
      the master random number generation unit randomly generates a random number ω
      
      , where the random number ω
      
      is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the second processing device;
      
      the public base calculation unit calculates a divisor g=g₂+β
      
      ·
      
      g₁of the Jacobian variety Jac_C, based on an output base g₁and an output base g₂calculated by the output base calculation unit and the random number β
      
      generated by the base random number generation unit, by using the second processing device;
      
      the public first divisor calculation unit calculates a divisor Ω
      
      =ω
      
      ·
      
      g of the Jacobian variety Jac_C, based on the random number ω
      
      generated by the master random number generation unit and the divisor g calculated by the public base calculation unit, by using the second processing device;
      
      the public pairing value calculation unit calculates a pairing value A=e(g,g)^α, based on the random number α
      
      generated by the pairing random number generation unit and the divisor g calculated by the public base calculation unit, by using the second processing device;
      
      the public second divisor generation unit randomly generates a divisor u of the Jacobian variety Jac_C, by using the second processing device;
      
      the public third divisor generation unit randomly generates a divisor v′
      
      of the Jacobian variety Jac_C, by using the second processing device;
      
      the public bit divisor generation unit randomly generates m divisors v_i, where i is an integer greater than or equal to 1 and less than or equal to m, of the Jacobian variety Jac_C, based on the bit length m input by the bit length input unit, by using the second processing device;
      
      the master divisor calculation unit calculates a divisor g′
      
      =α
      
      ·
      
      g of the Jacobian variety Jac_C, based on the random number α
      
      generated by the pairing random number generation unit and the divisor g calculated by the public base calculation unit, by using the second processing device;
      
      the public key setting unit sets a public key PK=(g₁,g,Ω
      
      ,A,u,v′
      
      ,v_i), where i is an integer greater than or equal to 1 and less than or equal to m, based on the output base g₁calculated by the output base calculation unit, the divisor g calculated by the public base calculation unit, the divisor Ω
      
      calculated by the public first divisor calculation unit, the pairing value A calculated by the public pairing value calculation unit, the divisor u generated by the public second divisor generation unit, the divisor v′
      
      generated by the public third divisor generation unit, and the m divisors v_igenerated by the public bit divisor generation unit, by using the second processing device;
      
      the master key setting unit sets a master key MK=(ω
      
      ,g′
      
      ), based on the random number ω
      
      generated by the master random number generation unit and the divisor g′
      
      calculated by the master divisor calculation unit, by using the second processing device;
      
      the tracer'"'"'s key setting unit sets a tracer'"'"'s key TK=(g₂), based on the output base g₂calculated by the output base calculation unit, by using the second processing device;
      
      the signing key issuing apparatus includes a second storage device for storing data, a third processing device for processing data, a master key storage unit, an issuer public key input unit, an identifier generation unit, a signing first key calculation unit, a signing second key calculation unit, a signing third key calculation unit, a signing key setting unit, and an identifier setting unit;
      
      the master key storage unit stores the master key MK=(ω
      
      ,g′
      
      ) set by the key generation apparatus, by using the second storage device;
      
      the issuer public key input unit inputs the public key PK=(g₁,g,Ω
      
      ,A,u,v′
      
      ,v_i) set by the key generation apparatus, by using the third processing device;
      
      the identifier generation unit randomly generates an identifier s_IDwhere the identifier S_IDis an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the third processing device;
      
      the signing first key calculation unit calculates a divisor K₁={1/(ω
      
      +s_ID)}·
      
      g′
      
      of the Jacobian variety Jac_C, based on the random number ω and
      
      the divisor g′
      
      included in the master key MK stored by the master key storage unit and the identifier s_IDgenerated by the identifier generation unit, by using the third processing device;
      
      the signing second key calculation unit calculates a divisor K₂=s_ID·
      
      g of the Jacobian variety Jac_C, based on the divisor g included in the public key PK stored by the issuer public key input unit and the identifier S_IDgenerated by the identifier generation unit, by using the third processing device;
      
      the signing third key calculation unit calculates a divisor K₃=s_ID·
      
      u of the Jacobian variety Jac_C, based on the divisor u included in the public key PK stored by the issuer public key input unit and the identifier s_IDgenerated by the identifier generation unit, by using the third processing device;
      
      the signing key setting unit sets a signing key SK=(K₁,K₂,K₃), based on the divisor K₁calculated by the signing first key calculation unit, the divisor K₂calculated by the signing second key calculation unit, and the divisor K₃calculated by the signing third key calculation unit, by using the third processing device;
      
      the identifier setting unit sets the identifier s_IDgenerated by the identifier generation unit as an identifier for identifying the signing key SK set by the signing key setting unit, by using the third processing device;
      
      each of the signing apparatus includes a third storage device for storing data, a fourth processing device for processing data, a signing key storage unit, a signer public key input unit, a signer message input unit, a signer message divisor calculation unit, a signature first random number generation unit, a signature second random number generation unit, a signature first divisor calculation unit, a signature second divisor calculation unit, a signature third divisor calculation unit, a signature fourth divisor calculation unit, a signature fifth divisor calculation unit, a signature sixth divisor calculation unit, and a signature output unit;
      
      the signing key storage unit stores the signing key SK=(K₁,K₂,K₃) set by the key generation apparatus, by using the third storage device;
      
      the signer public key input unit inputs the public key PK=(g₁,g,Ω
      
      ,A,u,v′
      
      ,v_i) set by the key generation apparatus, by using the fourth processing device;
      
      the signer message input unit inputs a message M to be signed, by using the fourth processing device;
      
      the signer message divisor calculation unit calculates a divisor v =v'"'"'+Σ
      
      (μ
      
      _i·
      
      v_i), where i is an integer greater than or equal to 1 and less than or equal to m, and μ
      
      i is an integer being 0 or 1 indicating an i-th bit of the message M, of the Jacobian variety Jac_C, based on the divisor v′ and
      
      the m divisors v_iincluded in the public key PK input by the signer public key input unit and the message M input by the signer message input unit, by using the fourth processing device;
      
      the signature first random number generation unit generates a random number s, where the random number s is an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the fourth processing device;
      
      the signature second random number generation unit randomly generates four random numbers t_j, where j is an integer greater than or equal to 1 and less than or equal to 4 and the random number t_jis an integer greater than or equal to 1 and less than or equal to r−
      
      1, by using the fourth processing device;
      
      the signature first divisor calculation unit calculates a divisor σ
      
      ₁=K₁+t₁·
      
      g₁of the Jacobian variety Jac_C, based on the divisor g₁included in the public key PK input by the signer public key input unit, the divisor K₁included in the signing key SK stored by the signing key storage unit, and a random number t₁generated by the signature second random number generation unit, by using the fourth processing device;
      
      the signature second divisor calculation unit calculates a divisor σ
      
      ₂=K₂+t₂·
      
      g₁of the Jacobian variety Jac_C, based on the divisor g₁included in the public key PK input by the signer public key input unit, the divisor K₂included in the signing key SK stored by the signing key storage unit, and a random number t₂generated by the signature second random number generation unit, by using the fourth processing device;
      
      the signature third divisor calculation unit calculates a divisor σ
      
      hd 3=K₃+s·
      
      v+t₃·
      
      g₁of the Jacobian variety Jac_C, based on the divisor g₁included in the public key PK input by the signer public key input unit, the divisor K₃included in the signing key SK stored by the signing key storage unit, the divisor v calculated by the signer message divisor calculation unit, the random number s generated by the signature first random number generation unit, and a random number t₃generated by the signature second random number generation unit, by using the fourth processing device;
      
      the signature fourth divisor calculation unit calculates a divisor σ
      
      ₄=s·
      
      g+t₄·
      
      g₁of the Jacobian variety Jac_C, based on the divisors g and g₁included in the public key PK input by the signer public key input unit, the random number s generated by the signature first random number generation unit, and a random number t₄generated by the signature second random number generation unit, by using the fourth processing device;
      
      the signature fifth divisor calculation unit calculates a divisor π
      
      ₁=t₁t₂·
      
      g₁+t₂·
      
      K₁+t₁·
      
      (K₂+Ω
      
      ) of the Jacobian variety Jac_C, based on the divisors g_iand Ω
      
      included in the public key PK input by the signer public key input unit, the divisors K₁and K₂included in the signing key SK stored by the signing key storage unit, and the random numbers t₁and t₂generated by the signature second random number generation unit, by using the fourth processing device;
      
      the signature sixth divisor calculation unit calculates a divisor π
      
      ₂=t₂·
      
      u−
      
      t₃·
      
      g−
      
      t₄·
      
      v of the Jacobian variety Jac_C, based on the divisors g and u included in the public key PK input by the signer public key input unit, the divisor v calculated by the signer message divisor calculation unit, and the random numbers t₂, t₃, and t₄generated by the signature second random number generation unit, by using the fourth processing device;
      
      the signature output unit outputs a signature σ
      
      =(σ
      
      ₁,σ
      
      ₂,σ
      
      ₃,σ
      
      ₄,π
      
      ₁,π
      
      ₂), based on the divisor σ
      
      ₁calculated by the signature first divisor calculation unit, the divisor σ
      
      ₂calculated by the signature second divisor calculation unit, the divisor σ
      
      ₃calculated by the signature third divisor calculation unit, the divisor σ
      
      ₄calculated by the signature fourth divisor calculation unit, the divisor π
      
      ₁calculated by the signature fifth divisor calculation unit, and the divisor π
      
      ₂calculated by the signature sixth divisor calculation unit, by using the fourth processing device;
      
      the signature verification apparatus includes a fifth processing device for processing data, a verifier public key input unit, a verifier signature input unit, a verifier message input unit, a verifier message divisor calculation unit, a signature first verification value calculation unit, a signature second verification value calculation unit, a signature third verification value calculation unit, a signature fourth verification value calculation unit, and a signature verification judgment unit;
      
      the verifier public key input unit inputs the public key PK=(g₁,g,Ω
      
      ,A,u,v′
      
      ,v_i) set by the key generation apparatus, by using the fifth processing device;
      
      the verifier signature input unit inputs the signature σ
      
      =(σ
      
      ₁,σ
      
      ₂,σ
      
      ₃,σ
      
      ₄,π
      
      ₁,π
      
      ₂) output by the signing apparatus, by using the fifth processing device;
      
      the verifier message input unit inputs the message M signed with the signature σ
      
      , by using the fifth processing device;
      
      the verifier message divisor calculation unit calculates the divisor v=v′
      
      +Σ
      
      (μ
      
      _i·
      
      v_i), where i is an integer greater than or equal to 1 and less than or equal to m, and μ
      
      _iis an integer being 0 or 1 indicating an i-th bit of the message M, of the Jacobian variety Jac_C, based on the divisor v′ and
      
      the m divisors v_iincluded in the public key PK input by the verifier public key input unit and the message M input by the verifier message input unit, by using the fifth processing device;
      
      the signature first verification value calculation unit calculates a pairing value C=e(g₁,π
      
      ₁), based on the divisor g₁included in the public key PK input by the verifier public key input unit and the divisor π
      
      ₁included in the signature σ
      
      input by the verifier signature input unit, by using the fifth processing device;
      
      the signature second verification value calculation unit calculates a pairing value C′
      
      =e(σ
      
      ₁,σ
      
      ₂+Ω
      
      )/A, based on the divisor Ω and
      
      the pairing value A included in the public key PK input by the verifier public key input unit and the divisors σ
      
      _land σ
      
      ₂included in the signature σ
      
      input by the verifier signature input unit, by using the fifth processing device;
      
      the signature third verification value calculation unit calculates a pairing value D=e(g₁,π
      
      ₂), based on the divisor g₁included in the public key PK input by the verifier public key input unit and the divisor π
      
      ₂included in the signature a input by the verifier signature input unit, by using the fifth processing device;
      
      the signature fourth verification value calculation unit calculates a pairing value D′
      
      =e(σ
      
      ₂,u)/{e(g,σ
      
      ₃)·
      
      e(σ
      
      ₄,v)}, based on the divisors u and g included in the public key PK input by the verifier public key input unit, the divisors σ
      
      ₂, σ
      
      ₃, and σ
      
      ₄included in the signature σ
      
      input by the verifier signature input unit, and the divisor v calculated by the verifier message divisor calculation unit, by using the fifth processing device;
      
      the signature verification judgment unit judges whether the pairing value C and the pairing value C′
      
      are equal or not and whether the pairing value D and the pairing value D′
      
      are equal or not, based on the pairing value C calculated by the signature first verification value calculation unit, the pairing value C′
      
      calculated by the signature second verification value calculation unit, the pairing value D calculated by the signature third verification value calculation unit, and the pairing value D′
      
      calculated by the signature fourth verification value calculation unit, and when judging that the pairing value C and the pairing value C′
      
      are equal and the pairing value D and the pairing value D′
      
      are equal, judges the signature σ
      
      input by the verifier signature input unit to be valid, by using the fifth processing device;
      
      the signer tracing apparatus includes a fourth storage device for storing data, a sixth processing device for processing data, a tracer'"'"'s key storage unit, an identifier storage unit, a tracer signature input unit, a signature pairing value calculation unit, an identifier pairing value calculation unit, and a signer identification unit;
      
      the tracer'"'"'s key storage unit stores a tracer'"'"'s key TK=(g₂) set by the key generation apparatus, by using the fourth storage device;
      
      the identifier storage unit stores the identifier s_IDfor identifying the signing key SK issued by the signing key issuing apparatus, by using the fourth storage device;
      
      the tracer signature input unit inputs the signature σ
      
      output by the signing apparatus, by using the sixth processing device;
      
      the signature pairing value calculation unit calculates a pairing value E=e(g₂,σ
      
      ₂), based on the divisor g₂included in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit and the divisor σ
      
      ₂included in the signature σ
      
      input by the tracer signature input unit, by using the sixth processing device;
      
      the identifier pairing value calculation unit calculates a pairing value E_ID=e(g₂,g₂)^s_ID, based on the divisor g₂included in the tracer'"'"'s key TK stored by the tracer'"'"'s key storage unit and the identifier s_IDstored by the identifier storage unit, by using the sixth processing device; and
      
      the signer identification unit identifies an identifier of the signing key SK which had generated the signature σ
      
      input by the tracer signature input unit, by detecting a pairing value in accordance with the pairing value E calculated by the signature pairing value calculation unit in the pairing value E_IDcalculated by the identifier pairing value calculation unit, by using the sixth processing device.

16. A key generation apparatus comprising:
- a processing device for processing data;
  
  a storage device for storing data;
  
  a base divisor storage unit;
  
  a pairing log storage unit;
  
  an output base calculation unit; and
  
  a key calculation unit,wherein the base divisor storage unit stores, as a plurality of base divisors D˜
  
  _j, a plurality of elements of a group G, where the group G is a direct product of a plurality of cyclic groups of a same order, a pairing value by a bilinear pairing operation of two elements included in the group G is computable, and the plurality of base divisors D^˜_jare mutually linearly independent, by using the storage device;
  
  the pairing log storage unit stores logarithms of pairing values of the plurality of base divisors D^˜_j, as a plurality of pairing log coefficients η
  
  _i, by using the storage device;
  
  the output base calculation unit calculates a plurality of output bases g_kbeing elements of the group G, where a pairing value of at least any two output bases g_kin the plurality of output bases g_kis 1, based on the plurality of base divisors D^˜_j, stored by the base divisor storage unit and the plurality of pairing log coefficients η
  
  _istored by the pairing log storage unit, by using the processing device; and
  
  the key calculation unit calculates a key to be used in a cryptographic operation, based on the plurality of output bases g_kcalculated by the output base calculation unit, by using the processing device.
- View Dependent Claims (17, 18, 19)
- - 17. The key generation apparatus according to claim 16, further comprising a random matrix selection unit,wherein the random matrix selection unit randomly selects a random matrix V* from a plurality of matrices V satisfying m′
    - _uv=0, where u and v are predetermined integers greater than or equal to 1 and less than or equal to b, in a relational expression M′
      
      =V·
      
      M·
      
      V^T, where M′
      
      is a b-dimensional square matrix in which m′
      
      _μ
      
      ν is a μ
      
      -th row and ν
      
      -th column element, b is a number of a plurality of output bases g_kwhich the output base calculation unit calculates, V is a b row by f column matrix in which a variable c_μ
      
      ν whose value is an integer greater than or equal to 0 and less than or equal to r−
      
      1 is a μ
      
      -th row and ν
      
      -th column element, r is an order of the plurality of cyclic groups, f is a number of the plurality of base divisors D^˜_j, stored by the base divisor storage unit, M is an f-dimensional square matrix in which a pairing log coefficient η
      
      _iof a base divisor D^˜_μand a base divisor D^˜_νin the pairing log coefficients μ
      
      _istored by the pairing log storage unit is a μ
      
      -th row and ν
      
      -th column element, and V^Tis an f row by b column matrix transposed from the matrix V, based on the plurality of pairing log coefficients η
      
      stored by the pairing log storage unit, by using the processing device; and
      
      the output base calculation unit calculates the plurality of output bases g_k=v_k·
      
      D^˜, where k is an integer greater than or equal to 1 and less than or equal to b, ν
      
      _kis a k-th row vector of the random matrix V*, and D^˜is an f-dimensional column vector which uses the plurality of base divisors D^˜_jas a (j+1)th row element, based on the plurality of base divisors D^˜_jstored by the base divisor storage unit and the random matrix V* selected by the random matrix selection unit, by using the processing device.
  - 18. The key generation apparatus according to claim 16,wherein the base divisor storage unit stores a plurality of elements of a group G which is a subgroup of a group composed of a plurality of divisors of a Jacobian variety Jac_Cof an algebraic curve C in an extension field K given by a finite algebraic extension of a finite field F_p, as the plurality of base divisors D^˜
    - _j, by using the storage device.
  - 19. A non-transitory computer readable storage medium having stored therein computer executable instructions that cause a computer, having a processing device for processing data, to operate as the key generation apparatus according to claim 16.

20. An encryption parameter setting method according to which an encryption parameter setting apparatus, having a processing device for processing data, sets encryption parameters used for a cryptographic operation, the encryption parameter setting method comprising:
- selecting, by the processing device, an element from a plurality of elements of a cyclic group G′
  
  , as a random divisor D* ;
  
  calculating, by the processing device, a plurality of base divisors D^˜_jby mapping the random divisor D* by using a plurality of maps G _j, where the plurality of maps G_jare homomorphism from the cyclic group G′
  
  to each of a plurality of cyclic groups G′
  
  _j, based on the random divisor D* selected;
  
  calculating, by the processing device, logarithms of pairing values of the plurality of base divisors D^˜_jin a group G, where the group G is a direct product of the plurality of cyclic groups G′
  
  _j, and a pairing value by a bilinear pairing operation of two elements included in the group G is computable, and treating the logarithms as a plurality of pairing log coefficients η
  
  _i; and
  
  treating, by the processing device, the plurality of base divisors D^˜_jcalculated and the plurality of pairing log coefficients η
  
  _i;
  
  calculated, as the encryption parameters.

21. An encryption parameter setting method according to which an encryption parameter setting apparatus, having a processing device for processing data, sets encryption parameters used for a cryptographic operation, the encryption parameter setting method comprising:
- selecting, by the processing device, a random divisor D* randomly from a plurality of divisors of a Jacobian variety Jac_Cof a hyperelliptic curve C of genus d in a finite field F_p(where an order p of the finite field F_pis a prime number, and the genus d is an integer greater than or equal to
  
  2);
  
  calculating, by the processing device, a plurality of base divisors D^˜_j, based on the random divisor D* selected;
  
  calculating, by the processing device, a plurality of discrete logs l_K, where K is an integer greater than or equal to 1 and less than or equal to 2d-1, and the discrete log l _Kis an integer greater than or equal to 0 and less than or equal to 2d-1;
  
  calculating, by the processing device, a plurality of pairing log coefficients η
  
  _i, where i is an integer greater than or equal to 0 and less than or equal to 2d-1, the pairing log coefficient η
  
  _iis an integer greater than or equal to 0 and less than or equal to r−
  
  1, and r is an order of the plurality of divisors of the Jacobian variety Jac_C, based on the plurality of discrete logs l_Kcalculated; and
  
  setting, by the processing device, the encryption parameters, based on the plurality of base divisors D^˜_jcalculated and the plurality of pairing log coefficients η
  
  _icalculated.

22. A key generation method according to which a key generation apparatus, having a processing device for processing data and a storage device for storing data, generates a key used for a cryptographic operation, the key generation method comprising:
- storing, by the storage device, as a plurality of base divisors D^˜_j, a plurality of elements of a group G, where the group G is a direct product of a plurality of cyclic groups of a same order, a pairing value by a bilinear pairing operation of two elements included in the group G is computable, and the plurality of base divisors D^˜_jare mutually linearly independent;
  
  storing, by the storage device, logarithms of pairing values of the plurality of base divisors D^˜_j, as a plurality of pairing log coefficients η
  
  _i;
  
  calculating, by the processing device, a plurality of output bases g_kbeing elements of the group G, where a pairing value of at least any two output bases g_kin the plurality of output bases g_kis 1, based on the plurality of base divisors D^˜_jstored by the storage device and the plurality of pairing log coefficients η
  
  _istored by the storage device; and
  
  calculating, by the processing device, the key, based on the plurality of output bases calculated.

23. A key generation method according to which a key generation apparatus, having a processing device for processing data and a storage device for storing data, generates a key used for a cryptographic operation, the key generation method comprising:
- storing, by the storing device, a plurality of base divisors D^˜_jof a Jacobian variety Jac_Cof an algebraic curve C of genus d in an extension field K given by a finite algebraic extension of a finite field F_p, where an order p of the finite field F_pis a prime number, the genus d is an integer greater than or equal to 2, and w is a prime number of w=2d+1, and a plurality of pairing log coefficients η
  
  _iindicating a relation of a pairing value of the plurality of base divisors;
  
  randomly, by the processing device, selecting a random matrix V* satisfying a predetermined condition, based on the plurality of pairing log coefficients η
  
  _istored by the storage device;
  
  calculating, by the processing device, a plurality of output bases g_k, based on the plurality of base divisors D^˜_jstored by the storage device and the random matrix V* selected; and
  
  calculating, by the processing device, the key, based on the plurality of output bases g_kcalculated.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Mitsubishi Electric Corporation
Original Assignee
Mitsubishi Electric Corporation
Inventors
Takashima, Katsuyuki
Primary Examiner(s)
CERVETTI, DAVID GARCIA

Application Number

US12/863,100
Publication Number

US 20100329454A1
Time in Patent Office

1,887 Days
Field of Search

380/28, 380/44
US Class Current

380/28
CPC Class Codes

H04L 2209/606 Traitor tracing

H04L 9/3073 involving pairings, e.g. id...

Encryption parameter setting apparatus, key generation apparatus, cryptographic system, program, encryption parameter setting method, and key generation method

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

Citations

23 Claims

Specification

Solutions

Use Cases

Quick Links

Encryption parameter setting apparatus, key generation apparatus, cryptographic system, program, encryption parameter setting method, and key generation method

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

Citations

23 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links