JP6348082B2 - Structure conversion apparatus and program - Google Patents

Description

  The present invention relates to a technique for converting an algebraic structure of an algorithm.

A technique for converting the algebraic structure of an algorithm is known. For example, Non-Patent Documents 1 and 2, the group G, the pairing on _{G T} e: an algorithm using _G × G → G _T, the group _{G 1,} G 2, pairing on _{G T} e: G A technique for converting into an algorithm using ₁ × G ₂ → G _T (where G ₁ ≠ G ₂ ) is disclosed. In this technique, the group G ₁ or G ₂ is allocated to the node of the dependency graph of the group operation on the group G, the allocation status is evaluated by the evaluation function, and the allocation with the best evaluation is selected.

T. Tango, M. Abe, and T. Okamoto, “Implementation of Automated Translation for Schemes on Symmetric Bilinear Groups,” In Proc. Of SCIS 2014, 2014. M. Abe, J. Groth, M. Ohkubo, and T. Tango, “Converting cryptographic schemes from symmetric to asymmetric bilinear groups,” In JA Garay and R. Gennaro, editors, Advances in Cryptology-CRYPTO 2014-34th Annual Cryptology Conference , Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 241-260. Springer, 2014.

  In the prior art, there is a problem that a search space for allocation is wide and a calculation amount is large. An object of the present invention is to reduce the amount of calculation for converting an algebraic structure of an algorithm.

First, for the linear constraint q (s (i, φ (0))) +... + Q (s (i, φ (S (i) −1))) = y (i, n) ∈F ₂ Y for the element r of the complement of {s (i, φ (0)),..., S (i, φ (S (i) −1))} in {0,. (I, r) = 0, and y (i, k) = for element k of {s (i, φ (0)),..., S (i, φ (S (i) -1))} Information indicating a matrix having y (i, 0),..., Y (i, n−1), y (i, n) as elements in the i-th row is obtained. However, n is an integer greater than or equal to 2, and j = 0, ..., n-1. F ₂ is a finite field of order 2, and q (j) = 0∈ when assigning the algebraic structure G ₁ to the node N (j) of the dependency graph representing the dependency of the operation in the algebraic structure G When F ₂ is assigned and the algebraic structure G ₂ is assigned to the node N (j), q (j) = 1∈F ₂ (G ₁ ≠ G ₂ ). m is an integer of 1 or more, and i = 0,..., m−1. S (i) is an integer of 1 or more, and {s (i, φ (0)),..., S (i, φ (S (i) -1))} ⊆ {0,. n-1}. Next, from a matrix having y (i, 0),..., Y (i, n-1), y (i, n) as elements of the i-th row, z (i, 0),. , Z (i, n-1), z (i, n) is obtained as information representing a step matrix having elements in the i-th row. Thereafter, it is determined whether the node N (j) is an independent node based on the information representative of the stairs matrix, assigning the algebraic structure G ₁ or algebraic structure G ₂ to the node N (j).

  Thereby, the amount of calculation for converting the algebraic structure of the algorithm can be reduced.

FIG. 1 is a block diagram illustrating a functional configuration of the structure conversion device according to the first embodiment. FIG. 2 is a flowchart for explaining the structure conversion method of the first embodiment. FIG. 3 is a diagram illustrating a dependency relationship graph. Figure 4 is a diagram illustrating a dependency graph of nodes that are assigned to G _1. Figure 5 is a view illustrating the dependency graph of nodes that are assigned to G _2. FIG. 6 is a diagram illustrating a dependency relationship graph. FIG. 7 is a diagram illustrating a dependency relationship graph. FIG. 8 is a block diagram illustrating a functional configuration of the structure conversion device according to the second embodiment. FIG. 8 is a flowchart for explaining the structure conversion method of the second embodiment.

Embodiments of the present invention will be described below.
[Overview]
In this embodiment, first, the linear constraint q (s (i, φ (0))) +... + Q (s (i, φ (S (i) −1))) = y (i, n) ∈F ₂ , S (i, φ (S (i) -1))} elements of {s (i, φ (0)),. y (i, r) = 0 for r and y (i, r (0,0)),..., s (i, φ (S (i) -1))} k) = 1 to obtain information representing a matrix having y (i, 0),..., y (i, n-1), y (i, n) as elements of the i-th row. However, n is an integer greater than or equal to 2, and j = 0, ..., n-1. F ₂ is a finite field of order 2, and q (j) when assigning the algebraic structure G ₁ to the node (variable) N (j) of the dependency graph representing the dependency of the operation in the algebraic structure G When = 0∈F ₂ and the algebraic structure G ₂ is assigned to the node N (j), q (j) = 1∈F ₂ (G ₁ ≠ G ₂ ). Examples of algebraic structures are groups such as Abelian groups, semigroups, monoids, fields, rings and the like. m is an integer of 1 or more, and i = 0,..., m−1. S (i) is an integer of 1 or more, and {s (i, φ (0)),..., S (i, φ (S (i) -1))} ⊆ {0,. n-1}. However, S (i) is an integer of 2 or more when the relationship between nodes is restricted. Next, from a matrix having y (i, 0),..., Y (i, n-1), y (i, n) as elements of the i-th row, z (i, 0),. , Z (i, n-1), z (i, n) is obtained as information representing a step matrix having elements in the i-th row. Thereafter, it is determined whether or not the node N (j) is an independent node (independent variable) based on the information representing the staircase matrix, and the algebraic structure G ₁ or the algebraic structure G ₂ is assigned to the node N (j). assign. Here, if the node N (j) is not an independent node (that is, if it is a dependent node (dependent variable)), the assignment of the algebraic structure to the node N (j) depends on the assignment to other nodes. . That is, if the allocation to the independent node is determined, the allocation to the subordinate node is also determined accordingly. As a result, the search space can be reduced and the amount of calculation can be reduced.

The determination as to whether it is an independent node or a dependent node is performed as follows.
(1) When the staircase matrix includes a row with z (0,0) = 1 and a row with z (1,1) = 0, it is determined that the node N (1) is an independent node.
(2) z (ω, 0) = ... = z (ω, t (ω) −1) = 0 and z (ω, t () for an integer t (ω) having a step matrix of 1 to n−2. The node N (t (ω) +1) is determined to be an independent node when it includes a row where ω)) = 1 and a row where z (ω + 1, t (ω) +1) = 0. However, ωε {0,..., M−2} and t (ω) ε {1,.
(3) The step matrix is z (m−1,0) =... = Z (m−1, t (m−1) −1) = 0 and z (m−1, t (m−1)) , N (n−1) is determined to be an independent node when a row including = 1 is included.
(4) The other nodes N (j) are determined to be subordinate nodes.
This makes it possible to determine whether the node is an independent node or a dependent node with a small amount of calculation.

Algebraic structure assignment to independent nodes and subordinate nodes is performed as follows.
(1) First, a node N (ν) (where νε {0,..., N−1}) determined to be an independent node is assigned an algebraic structure G ₁ or an algebraic structure G ₂ . Decide whether to allocate. This assignment is performed, for example, by a search process using a predetermined evaluation function.
(2) Thereafter, the algebraic structure G ₁ or the algebraic structure G ₂ is assigned to another node (η) that is a subordinate node (where η∈ {0,..., N−1} and η ≠ ν). . This assignment is determined according to the assignment to the independent node.
Thereby, the search space can be reduced.

The above-described method can be applied to bilinear mapping type conversion such as pairing. The configuration in this case is as follows.
(1) The dependency relationship graph represents a dependency relationship of group operations included in an algorithm for obtaining an input value of a symmetric bilinear map.
(2) The algebraic structure G is a group and forms a domain G × G of a symmetric bilinear map.
(3) The algebraic structure G ₁ and the algebraic structure G ₂ are groups different from each other, and form the domain G ₁ × G ₂ of the asymmetric bilinear map.
(4) S (i) = 2. The linear constraint corresponding to the nodes N (j ₁ ) and N (j ₂ ) corresponding to the same symmetric bilinear mapping input value pair is q (j ₁ ) + q (j ₂ ) = 1∈F ₂ . . Node N _{(j 3)} the node N _{(j 3)} linear constraints _q (j 3) corresponding to that the ancestor node node N _{(j 4)} of the + _{q (j} 4) = a 0∈F _2. However, j ₁ , j ₂ , j ₃ , j ₄ ε {0,..., N−1}.
As a result, an algorithm using a symmetric bilinear map can be converted to an algorithm using an asymmetric bilinear map at high speed. A specific example will be described later.

The search space and evaluation function may be converted to a problem instance of 0-1 integer programming as follows to speed up the search.
(1) Based on the dependency graph representing the dependency of operations in the algebraic structure G, q _{1, j} + _{Σρ (χ) ∈D (j)} d (ρ (χ)) ≦ # D (j) Yes, for ∀ρ (χ) ∈D (j), q _{1, j} + d (ρ (χ)) ≧ 1, and q _{2, j} −Σρ _{(χ) ∈D (j)} d (ρ (χ) ) ≦ 0, and a linear constraint including that q _{2, j} −d (ρ (χ)) ≧ 0 is set for ∀ρ (χ) ∈D (j). However, n is an integer greater than or equal to 2, and j = 0, ..., n-1. When assigning the algebraic structure G ₁ to the node N (j) of the dependency graph, q _{1, j} = 1 and q _{2, j} = 0, and assigning the algebraic structure G ₂ to the node N (j) _{1, j} = 0 and q2 _{, j} = 1. G ₁ ≠ G ₂ , d (j) = 0 when assigning the algebraic structure G ₁ to the node N (j), and d (j) when assigning the algebraic structure G ₂ to the node N (j) = 1. The descendant nodes of the node N (j) are DN (ρ (j, 0)),..., DN (ρ (j, # D (j) −1)), and D (j) is a set {ρ ( j, 0), ..., ρ (j, # D (j) -1)}, and #D (j) is the number of elements in the set D (j).
(2) Under the linear constraints described above, the linear evaluation function f (q _1,0 ,..., Q _{1, n−1} , q _2,0 ,..., Q _{2, n−1} ) Q _1,0 ,..., Q _{1, n−1} , q _2,0 ,..., Q _{2, n−1} whose output values satisfy a predetermined condition are determined.
_{q 1,0, ···, q 1,} n-1, q 2,0, ···, by determining the _{q 2, n-1,} allocation of algebraic structure of each node N (j) It can be performed.

As the evaluation function, for example, f (q _1,0 ,..., Q _{1, n−1} , q _2,0 ,..., Q _{2, n−1} ) = Σ _{j∈ {0,. , N−1}} (w _j , ₁ · q _{1, j} + w _j , ₂ · q _{2, j} ) can be used. However, | G _σ | is an information amount (for example, bit length) necessary for expressing an element of the algebraic structure G _{σ with} respect to σ∈ {1, 2}, and w _j is preliminarily set for the node N (j). It is a determined weighting factor, and w _j , _σ = w _j · | G _σ |. w _j may be a real number greater than or equal to 0, or may be a negative real number. This evaluation function corresponds to the amount of computation in an algorithm implemented by an algebraic structure assigned to each node. The smaller the output value of this evaluation function, the smaller the calculation amount. For this reason, it is desirable to perform allocation so that the output value of the evaluation function is minimized.

The configuration when applied to the type conversion of the bilinear map is as follows.
(1) The dependency relationship graph represents a dependency relationship of group operations included in an algorithm for obtaining an input value of a symmetric bilinear map.
(2) The algebraic structure G is a group and forms a domain G × G of a symmetric bilinear map.
(3) The algebraic structure G ₁ and the algebraic structure G ₂ are groups different from each other, and form the domain G ₁ × G ₂ of the asymmetric bilinear map.
(4) The linear constraint is d (j ₁ ) + d (j ₂ ) = 1 for nodes N (j ₁ ) and N (j ₂ ) corresponding to the same symmetric bilinear mapping input value pair, further comprising the fact the node N _{(j 3)} the node N _{(j 3)} the node N _{(j 4)} and the _d (j 3) is an ancestor node of + d _(j 4) = 0.
As a result, an algorithm using a symmetric bilinear map can be converted to an algorithm using an asymmetric bilinear map at high speed. A specific example will be described later.

[First Embodiment]
Hereinafter, an example in which the algebraic structures G, G ₁ and G ₂ are grouped and the above-described method is applied to the pairing type conversion will be described.

<Definition>
First, terms used in this embodiment are defined.
In cryptography, “pairing” generally means the following stochastic polynomial time algorithm.
1. λ is a safety variable.
2. q is a sufficiently large positive integer.
3. G _1, in _{G 2,} G _T each order q group of the same type (e.g., finite Abelian group), each with a sample operation and group operation of polynomial time.
4). _{e: G 1 × G 2 →} G T is polynomial-time bi-homomorphism.
5. _{G 1,} G 2, CDH problem on the _{G T} is difficult.

Pairing used in cryptographic protocols is classified into the following three types (for example, Reference 1 “SD Galbraith, KG Paterson, and NP Smart,“ Pairings for cryptographers, ”Discrete Applied Mathematics, 156 (16): 3113. -3121, 2008 ").
Type1: G ₁ = G ₂
There exists a polynomial time isomorphism map of Type ₂ : G ₁ ≠ G ₂ and Φ: G ₂ → G ₁ .
Type 3: There is no polynomial time isomorphism between G ₁ ≠ G ₂ , G ₁ , and G ₂ .
Since Type 1 is structurally simple, many cryptographic protocols are designed on the assumption of Type 1. However, it is now considered desirable to use Type 3 pairing from the viewpoint of efficiency such as computational complexity and spatial computational complexity (such as the size of public keys and ciphertexts).

In this embodiment, the method A ₁ algorithm that operates on a pairing group in which Type 1 pairing (symmetric bilinear mapping) is defined is paired with Type 3 pairing (asymmetric bilinear mapping). converting the algorithm of type a ₃ operating in groups. Hereinafter, the group of Type 1 is denoted as G. G = G ₁ or G ≠ G ₁ may be sufficient. G = G ₂ or G ≠ G ₂ may be sufficient. Algorithm scheme A ₁ is made from the algorithm of the components of a protocol to execute the method A _1, especially an algorithm for obtaining the input values of the pairing Type1. Further safety scheme A ₁ is indicated by the presence of a set of algorithms (resulting algorithm) called "return". Algorithm scheme A ₁ also comprises further the resulting algorithm.

The algorithm of the method A ₁ can be expressed by a dependency graph (directed graph) indicating the dependency of group operations included in the algorithm (see, for example, Non-Patent Document 2). In the description of the algorithm type A _1, input, output, and each group element appearing as intermediate results is given a unique label. In the dependency graph, “node (variable)” is assigned to the labels of all group elements handled by the algorithm. The dependency graph has an “edge” from the node toward the node of the next group element obtained by using the group element. It illustrates a dependency graph representing a group operation dependencies included in the algorithm of type A ₁ in FIG. The dependency graph of FIG. 3 includes nodes X ₁ -X ₁₀ and p ₁ [0], p ₁ [1], p ₂ [0], p ₂ [1]. Each node corresponds to a group element of group G, and has an edge from the node toward another node. For example, the node X ₁ corresponds to the generator g of the group G, and the node X ₂ represents the group element g ^υ2 εG obtained by the group operation using the generator g. For example, the nodes X ₄ and X ₇ correspond to the group elements g ^υ4 and g ^υ7 εG, respectively, and the node X ₉ has a group operation using the group elements g ^υ4 and g ^υ7 (for example, g ^υ4 · g ^υ7 εG). Represents the group element g ^υ9 ∈G obtained by

A node that can be reached from the node X in the edge direction is called a “descendant node” of X. Conversely, a node that can be reached from the node X in the opposite direction of the edge is called an “ancestor node” of X. In the example of FIG. 3, the node X ₉ is a descendant node of the node X _2, node X ₂ in the reverse is the ancestor node of the node X _9.

A node corresponding to the input value of pairing is called a “pairing node”. The pairing input value is a pair of two group elements, and a pairing node corresponding to them is also a pair. In the example of FIG. 3, p ₁ [0], p ₁ [1], p ₂ [0], and p ₂ [1] are pairing nodes. A pair of group elements corresponding to the pair (p ₁ [0], p ₁ [1]) becomes an input to the pairing e ₁ and a group element corresponding to the pair (p ₂ [0], p ₂ [1]) pair becomes the input to the pairing e ₂ of.

A node that does not have an edge to another node and a node that forms a loop in which an edge to another node exists but the destination following the edge returns to the original node is referred to as a “bottom node”. In the example of FIG. 3, the node X ₈ is a bottom node.

Assume a group operation H (x) = g ^α1 ∈G for an element x of the group G. Here, α1 is an arbitrary positive integer. At this time, the group elements _{x 1} ∈G ₁ and _{x 2} ∈G ₂ corresponding to the generated source kappa ₁ ∈G ₁ and origin kappa ₂ ∈G ₂ groups _{G 2} groups _{G 1,} and based on the x, α1 Without knowing, there is a group operation H in which it is difficult to set operations H ₁ and H ₂ that satisfy H ₁ (x ₁ ) = κ ₁ ^α1 and H ₂ (x ₂ ) = κ ₂ ^α1 . An example of the group operation H is a hash function. It is impossible to assign both the groups G ₁ and G ₂ to the node corresponding to the operation value of the group operation H. Such a node is called a “duplication prohibited node”. In the example of FIG. 3, the node X ₆ is duplicated prohibition node.

The pairing node, the bottom node, and the duplication prohibition node are collectively referred to as a “critical node”. A node that is not a critical node is called a “normal node”. Critical node can not allocate any of the group G ₁ or G ₂ mutually exclusive. On the other hand, the normal node may be assigned only one of the groups G ₁ or G _2, may be assigned to both groups G ₁ and G _2. In the example of FIG. 3, nodes X ₆ , X ₈ , p ₁ [0], p ₁ [1], p ₂ [0], p ₂ [1] are critical nodes, and nodes X ₁ -X ₅ , X ₇ , X ₉ and X ₁₀ are normal nodes.

4, of the nodes of the dependency graph of FIG. 3 illustrates a dependency graph reconstructed by the node group G ₁ is assigned. 5, among the nodes of the dependency graph of FIG. 3 illustrates a dependency graph that is reconstructed from the node group G ₂ is assigned. These dependency graph representing an algorithm scheme A _3. As shown in these examples, it is not possible to allocate only a either one of the group G ₁ or G ₂ is the critical node may be assigned to both groups G ₁ and G ₂ double the normal node However, only one of them may be assigned.

<Configuration>
As illustrated in FIG. 1, the structure conversion device 1 according to the present embodiment includes an input unit 11, a storage unit 12, a control unit 13, a graph construction unit 141, a linear constraint setting unit 142, a matrix generation unit 143, a matrix transformation unit 144, A determination unit 145 and a structure allocation unit 147 are included. The structure allocation unit 147 includes a search unit 147a, an allocation unit 147b, and a determination unit 147c. The structure conversion device 1 executes each process under the control of the control unit 13. The input data and the data obtained by each unit are stored in the storage unit 12, and are read out as necessary and used for each processing. The structure conversion apparatus 1 is a general-purpose or dedicated computer including a processor (hardware processor) such as a CPU (central processing unit) and a memory such as random-access memory (RAM) and read-only memory (ROM), for example. Is configured by executing a predetermined program. The computer may include a single processor and memory, or may include a plurality of processors and memory. This program may be installed in a computer, or may be recorded in a ROM or the like in advance. In addition, some or all of the processing units are configured using an electronic circuit that realizes a processing function without using a program, instead of an electronic circuit (circuitry) that realizes a functional configuration by reading a program like a CPU. May be. In addition, an electronic circuit constituting one device may include a plurality of CPUs.

<Processing>
A process of converting the algorithm of the method A _{1 into} the algorithm of the method A ₃ will be described with reference to FIG. First, the algorithm of the method A ₁ is input to the input unit 11 and stored in the storage unit 12. The graph construction unit 141 reads the algorithm of the method A ₁ from the storage unit 12, constructs a dependency graph graph (A ₁ ) representing the dependency relationship of the group operation included in the algorithm, and stores it in the storage unit 12 (step S141). .

The linear constraint setting unit 142 extracts the dependency graph graph (A ₁ ) from the storage unit 12, sets the linear constraint for the critical node included therein, and outputs it. In addition to the restriction that both of the groups G ₁ and G ₂ cannot be assigned twice, the critical node has the following restrictions.
(Constraint 1) When the group G ₁ is assigned to _one of the pairing pairing nodes, the group G ₂ must be assigned to the other side.
(Constraint 2) When there are critical nodes of ancestor nodes of a certain critical node, the groups assigned to those critical nodes are equal.
Here, the critical node of the dependency graph graph (A ₁ ) is expressed as N (j), and when assigning the group G ₁ to N (j), q (j) = 0∈F ₂ and N (j) Q (j) = 1εF ₂ when assigning group G ₂ to. However, n is an integer greater than or equal to 2, and j = 0, ..., n-1. Then, a pairing node (a node corresponding to a pair of input values of the same symmetric bilinear map) N (j ₁ ) and N (j ₂ ) corresponding to the pair 1 is a relational expression q (j ₁ ) + Q (j ₂ ) = 1∈F ₂ . The constraint 2 corresponding to N (j ₃ ) and its ancestor node N (j ₄ ) can be expressed by the relational expression q (j ₃ ) + q (j ₄ ) = 0εF ₂ . Generalizing such a relational expression, q (s (i, φ (0))) +... + Q (s (i, φ (S (i) −1))) = y (i, n) the ∈F _2. However, m is an integer greater than or equal to 1, and i = 0, ..., m-1. S (i) is an integer of 2 or more (for example, S (i) = 2), and {s (i, φ (0)),..., S (i, φ (S (i) −1) )} ⊆ {0,..., N−1}. The linear constraint setting unit 142 outputs such a relational expression as a linear constraint (step S142).

The linear constraint q (s (i, φ (0))) +... + Q (s (i, φ (S (i) −1))) = y (i, n) is input to the matrix generation unit 143. Is done. The matrix generation unit 143 complements {s (i, φ (0)),..., S (i, φ (S (i) −1))} in {0,. Y (i, r) = 0 for the element r of the set and y for the element k of {s (i, φ (0)),..., S (i, φ (S (i) −1))} A matrix matrix (A ₁ ) having y (i, 0),..., Y (i, n−1), y (i, n) as elements of the i-th row, where (i, k) = 1 is set. Obtain and output information to represent. That is, q (s (i, φ (0))) +... + Q (s (i, φ (S (i) -1))) = y (i, n), y (i, j) Y (i, 0) · q (0) +... + Y (i, n−1) · q (n−1) = y (i, n) using ∈F ₂ i, 0), ···, y (i, n-1), and y (i, a m × n matrix of n) and the i-th row element matrix _{(a 1).} y (i, 0),..., y (i, n-1) and y (i, n) are polynomials y (i, 0) .q (0) +... + y (i, n- 1) Corresponds to a coefficient and a constant term of q (n-1) = y (i, n). In the example of FIG. 3, X ₆ , X ₈ , p ₁ [0], p ₁ [1], p ₂ [0], and p ₂ [1] are represented by N (0), N (1), N (2 ), N (3), N (4), and N (5), the matrix (A ₁ ) is as follows (step S143).
0011001
0000111 Formula (1)
1001000
1100000

Information representing the matrix matrix (A ₁ ) is input to the matrix transformation unit 144. The matrix transformation unit 144 transforms the matrix matrix (A ₁ ) into a step matrix e-matrix (A ₁ ) using this information. The staircase matrix e-matrix (A ₁ ) is expressed as m × with z (i, 0),..., Z (i, n−1), z (i, n) ∈F ₂ as elements of the i-th row. n matrix. The transformation from the matrix matrix (A ₁ ) to the staircase matrix e-matrix (A ₁ ) can be performed using a known method such as Gaussian elimination (sweeping method). For example, the step matrix e-matrix (A ₁ ) of the matrix matrix (A ₁ ) illustrated in Expression (1) is as follows (step S144).
1001000
0101000 Formula (2)
0011001
0000111

The staircase matrix e-matrix (A ₁ ) is input to the determination unit 145. The determination unit 145 includes a case where e-matrix (A ₁ ) includes an element where z (ι, 0) =... = Z (ι, n−1) = 0 and z (ι, n) = 1 ( However, ιε {0,..., M−1}), it is determined that the assignment with the linear constraint set in step S142 is impossible (step S145), and the process is terminated. Otherwise, the determination unit 145 determines that assignment is possible (step S145), and advances the processing to step S147. In the case of the formula (2), the last nonzero row is 0000111, z (ι, 0) =... = Z (ι, n−1) = 0 and z (ι, n) = 1 There is no element that becomes. Therefore, the determination unit 145 determines that assignment is possible, and advances the process to step S147.

In step S147, first, the staircase matrix e-matrix (A ₁ ) is input to the determination unit 147c. The determination unit 147c performs the following determination.
(1) If the step matrix e-matrix (A ₁ ) includes a row where z (0,0) = 1 and a row where z (1,1) = 0, N (1) is an independent node judge.
(2) z (ω, 0) =... = Z (ω, t (ω) −1) = 0 for an integer t (ω) where the step matrix e-matrix (A ₁ ) is 1 or more and n−2 or less. N (t (ω) +1) is determined to be an independent node when it includes a row where z (ω, t (ω)) = 1 and a row where z (ω + 1, t (ω) +1) = 0. To do.
(3) The step matrix e-matrix (A ₁ ) is z (m−1,0) =... = Z (m−1, t (m−1) −1) = 0 and z (m−1, If the row includes t (m−1)) = 1, it is determined that the nodes N (t (m−1) +1),..., N (n−1) are independent nodes.
(4) It is determined that other N (j) are subordinate nodes.

If N (j) is an independent node, the group G ₁ or G ₂ can be assigned to N (j) independently of the assignment of the group to other critical nodes. When N (j) is a subordinate node, the assignment of the group G ₁ or G ₂ is determined according to the assignment of the group to other critical nodes. For example, in the example of Expression (2), the third row of the staircase matrix e-matrix (A ₁ ) is 0011001, and the fourth row is 0000111. Therefore, for ω = 2, t (2) = 2, z (2,0) = z (2,1) = 0 and z (2,2) = 1, and z (3,3) = 0. Therefore, the determination unit 147c determines that N (3) is an independent node. For m = 4, t (3) = 4, and n = 6, z (3,0) =... = Z (3,3) = 0 and z (3,4) = 1. Therefore, the determination unit 147c determines that N (5) is an independent node. In this example, N (3) is p ₁ [1] and N (5) is p ₂ [1], which are certainly independent nodes (FIG. 3). On the other hand, X ₆ is an ancestor node of p ₁ [1], and is also an ancestor node of X ₈ . Also, a group different from p ₁ [1] is assigned to p ₁ [0]. Therefore, X ₆ , X ₈ , p ₁ [0] are subordinate nodes of p ₁ [1]. Further, a group different from p ₂ [1] is assigned to p ₂ [0]. Therefore, p ₂ [0] is a subordinate node of p ₂ [1] (step S147c).

Information on whether N (j) and N (j) are independent nodes is input to the search unit 147a. The search unit 147a uses a predetermined evaluation function to set the group G ₁ and the group G to the critical node N (ν) (where ν∈ {0,..., N−1}) determined to be an independent node. Any of ₂ is assigned. As the evaluation function, a function representing the total value of the bit lengths of the group elements corresponding to the critical node N (ν) which is an independent node, and the total value of the bit lengths of the group elements corresponding to all the critical nodes N (j) Examples of such functions include a function that represents the total value of the bit lengths of the group elements of all nodes. A well-known means such as the Monte Carlo method may be used for the search. However, since the search space is only the critical node N (ν) determined to be an independent node, the amount of calculation required for the search can be suppressed. The search unit 147a outputs the result of group assignment to N (ν) (step S147a).

Allocation unit 147b receives the group allocation result to N (ν) and N (j) as inputs, and allocates either group G ₁ or group G ₂ to the critical node determined to be a subordinate node. This assignment is uniquely determined from the result of group assignment to N (ν). For example, the assigning unit 147b determines a group to be assigned to the subordinate node N (j) where z (i, j) = 1 in order from the row with the largest i in the staircase matrix e-matrix (A ₁ ). For example, in the case of the expression (2), the group G ₁ or G ₂ has already been assigned to the independent nodes N (3) and N (5). First, the assigning unit 147b assigns a group different from the group assigned to N (5) to N (4). Next, the assigning unit 147b assigns a group different from the group assigned to N (3) to N (2). Next, the assigning unit 147b assigns the same group as that assigned to N (3) to N (1). Finally, the assigning unit 147b assigns the same group as that assigned to N (3) to N (0). As a result, the group G ₁ or G ₂ is assigned to all the critical nodes N (0),..., N (n−1), respectively. Thereafter, the assigning unit 147b assigns at least one of the groups G ₁ and G ₂ to the normal node of the dependency relationship graph graph (A ₁ ). Arbitrary methods may be used to assign groups to normal nodes. However, at least a group assigned to the critical node is assigned to the ancestor node of the critical node, or both the groups G ₁ and G ₂ are assigned twice. The assigning unit 147b obtains a set of dependency graphs (A ₃ ), which are obtained from the dependency graph composed of the nodes to which the group G ₁ is assigned, and the dependency graph composed of the nodes to which the group G ₂ is assigned. ) (For example, FIG. 4 and FIG. 5) (step S147b).

<Specific example 1>
FIG. 6 shows a dependency graph graph (A ₁ ) of a verifier local revocation group signature of Boneh et al. (For example, reference document “D. Boneh and H. Shacham,“ Group signatures with verifier-local revocation, ” In V. Atluri, B. Pfitzmann, and PD McDaniel, editors, Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, Washington, DC, USA, October 25-29, 2004, pages 168-177. ACM, 2004. "). In the example of FIG. 6, (p ₁ [0], p ₁ [1]),..., (P ₈ [0], p ₈ [1]) are each a pair of pairing nodes. Also, R ₁ , R ₂ , (g ₁ ^* ) ^{1 / γ + x} where no edge to another node exists is a bottom node. U and v correspond to nodes that are prohibited from being duplicated. Therefore, this graph shows u, v, R ₁ , R ₂ , (g ₁ ^* ) ^{1 / γ + x} , p ₁ [0], p ₁ [1],..., P ₈ [0], p ₈ [ 1] 21 critical nodes N (0),..., N (20).

In this case, the following 21 × 22 matrix matrix (A ₁ ) is generated in step S143.
0000011000000000000001
0000000110000000000001
0000000001100000000001
0000000000011000000001
0000000000000110000001
0000000000000001100001
0000000000000000011001
0000000000000000000111
1010000000000000000000
1001000000000000000000
0100100000000000000000
0100000100000000000000
0100000001000000000000
0100000000010000000000
0100000000000100000000
0100000000000001000000
1000000000000000100000
0100000000000000010000
1000000000000000001000
1000000000000000000100
0100000000000000000010

In this case, the staircase matrix e-matrix (A ₁ ) generated in step S144 is as follows.
1010000000000000000000
0100100000000000000000
0011000000000000000000
0001000000000000100000
0000100100000000000000
0000011000000000000001
0000000110000000000001
0000000011000000000001
0000000001100000000001
0000000000110000000001
0000000000010100000000
0000000000001100000001
0000000000000101000000
0000000000000011000001
0000000000000001100001
0000000000000000110001
0000000000000000011001
0000000000000000001100
0000000000000000000111
0000000000000000000000
0000000000000000000000

The last non-zero row of this step matrix e-matrix (A ₁ ) is 0000000000000000000111. Therefore, it is determined in step S145 that assignment is possible. In step S147c of step S147, N (6) = p ₁ [1] and N (20) = p ₈ [1] are determined to be independent nodes, and the other critical nodes are determined to be subordinate nodes. . In step S147a, p ₁ [1] and p ₈ [1] are used as search spaces, and groups G ₁ or G ₂ are assigned to them. In step S 147b, according to the assignment to p ₁ [1] and p ₈ [1]. Assign to other nodes, and obtain and output a dependency graph graph (A ₃ ).

<Specific example 2>
FIG. 7 shows a dependency graph graph (A ₁ ) of Waters ID-based encryption (for example, Reference 3 “B. Waters,“ Efficient identity-based encryption without random oracles, ”In R. Cramer, editor, Advances. in Cryptology-EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science, pages 114-127.Springer, 2005. Etc.)). In FIG. 7, (p ₁ [0], p ₁ [1]),..., (P ₄ [0], p ₄ [1]) are a pair of pairing nodes. The bottom node and the duplication prohibition node are not particularly set. Therefore, the graph shows eight critical nodes N (0),..., N (p ₁ [0], p ₁ [1],..., P ₄ [0], p ₄ [1]. 7) exists.

In this case, a 4 × 9 matrix matrix (A ₁ ) is generated in step S143.
110000001
001100001
000011001
000000111

In this case, the step matrix e-matrix (A ₁ ) generated in step S144 is the same as the matrix (A ₁ ).

The last non-zero row of this step matrix e-matrix (A ₁ ) is 000000111. Therefore, it is determined in step S145 that assignment is possible. In step S147c of step S147, N (1) = p ₁ [1], N (3) = p ₂ [1], N (5) = p ₃ [1], N (7) = p ₄ [1] Are determined to be independent nodes, and other critical nodes are determined to be subordinate nodes. In step S147a, p ₁ [1], p ₂ [1], p ₃ [1], and p ₄ [1] are assigned as search spaces, and groups G ₁ or G ₂ are assigned to them. In step S 147b, these assignments are made. Accordingly, assignment to other nodes is performed, and a dependency graph graph (A ₃ ) is obtained and output.

[Second Embodiment]
In the specific example 1 (FIG. 6) described above, there are two independent nodes p ₁ [1] and p ₈ [1], and the other critical nodes are subordinate nodes. Therefore, it was possible to allocate 2 ² ways. In Specific Example 1 (FIG. 6), there are four independent nodes p ₁ [1], p ₂ [1], p ₃ [1], p ₄ [1], and other critical nodes are subordinate nodes. Met. Therefore, it was possible to allocate two ways ^4. In general, if there are Θ independent variables, there are 2 ^Θ assignment methods. In this embodiment, a method for efficiently finding an optimal assignment satisfying some evaluation criteria among such assignments (divisions) will be described.

For example, in the case of ID-based encryption having the dependency graph graph (A ₁ ) in FIG. 7, g, g ₁ , g ₂ , u ′, u _ε are held as public keys. However, u _ε represents a plurality (L) of elements. Therefore, if you want to find the assignment with the smallest public key size, find the dependency graph graph (A ₃ ) with the smallest total size of g, g ₁ , g ₂ , u ′ and L elements u _ε. That's fine.

と記述する。それらの述語が真であるときの値を１と表現し、述語が偽であるときその値を０とする。すなわち、（Ｎ（ｊ）∈Ｇ_σ）∈｛０，１｝である。 Here, a weight coefficient w _j is determined for each node N (j) of the dependency graph graph (A ₁ ). For example, in the case of the dependency graph graph (A ₁ ) in FIG. 7, the node weight coefficient corresponding to g, g ₁ , g ₂ , u ′ is set to 1, and it corresponds to u _ε consisting of L _elements . The node weighting factor is set to L, and the weighting factors of other nodes (normal nodes) are set to zero. A group G _σ (where σ∈ {1, 2}) is assigned to a certain node N (j), and the node N (j) is included in the graph on the group G _σ side of the dependency graph graph (A ₃ ). the predicates are described with N _(j) ∈G σ, the negation of the predicate ¬ the (N _(j) ∈G σ)

Is described. The value when those predicates are true is expressed as 1, and the value is 0 when the predicate is false. That is, _{(N (j) ∈G σ)} ∈ {0,1}.

であり、（Ｎ（ｊ）∈Ｇ_１）∧（Ｎ（ｊ）∈Ｇ_２）＝０が成立する。 If a node N (j) is a critical node, it is exclusive with predicate N (j) ∈G ₁ and predicate N (j) ∈G _2. That is,

And (N (j) εG ₁ ) ∧ (N (j) εG ₂ ) = 0 holds.

On the other hand, if the node N (j) is a normal node, (N (j) εG ₁ ) ∧ (N (j) εG ₂ ) = 0 does not necessarily hold. Also, | G _σ | (where σ∈ {1, 2}) is defined as the number of bits necessary to express the element of G _σ and is defined as w _j , _σ = w _j · | G _σ | . A set of nodes N (j) included in the dependency graph graph (A ₁ ) is defined as Vg. Using these notations and assuming that the value of each predicate is an integer as it is, the problem of minimizing the size of the public key can be regarded as a problem of minimizing the value of the following evaluation function. .

A set of critical nodes DN (ρ (j, 0)),..., DN (ρ (j, # D (j) −1)), which are descendants of the node N (j), is set (j) = { DN (ρ (j, 0)),..., DN (ρ (j, # D (j) -1))}, and the set D (j) = {ρ (j, 0),. , Ρ (j, # D (j) -1)}. However, #D (j) is a positive integer representing the number of elements of the set D (j). Assigned to the group _Gσ assigned to the node N (j) and its descendant nodes, the critical node DN (ρ (j, 0)), ..., DN (ρ (j, # D (j) -1)) And the group G _σ to be matched. Therefore, the following relationship is established.

すると、式（４）は以下のように書くことができる。

ただし、¬ｄ（ρ（χ））はｄ（ρ（χ））の否定を表す。 When assigning group G ₁ to node N (j), which is a critical node, d (j) = 0, and when assigning group G ₂ to node N (j), which is a critical node, d (j) = 1. . That is, the node N (j) that is a critical node is defined as follows.

Then equation (4) can be written as:

However, ¬d (ρ (χ)) represents negation of d (ρ (χ)).

そのため、どのような命題変数の論理式も命題変数の線型不等式の組で記述できる。 By the way, for variables x ′ and y ′ on {0, 1}, predicates x′∧y ′ and ¬x ′ can be described as follows using ordinary four arithmetic operations.
x′∧y ′ = x ′ × y ′
¬x '= 1-x'
Since conjunction and negation can be defined by four arithmetic operations, any logical expression of a propositional variable can be defined by a polynomial of the propositional variable. Also, since the variable x ′ on {0, 1} and the natural number ξ of 1 or more are x ′ ^ξ = x ′, the above polynomials regards any variable other than the variable of interest as a constant as a constant. It can be at most a first order polynomial. Here, for variables x ₁ ′,..., X _Γ ′ (where Γ is a positive integer) on {0, 1}, their product is expressed as y ′ = x ₁ ′ x _Γ ′. Then the following holds.

Therefore, any logical expression of a propositional variable can be described by a set of linear inequalities of the propositional variable.

Here, q _{1, j} ε {0,1} is defined as q _{1, j} = (N (j) εG ₁ ). That is, q _{1, j} = 1 when the group G ₁ is assigned to the node N (j), and q _{1, j} = 0 when the group G ₁ is not assigned to the node N (j). Then, from Equations (5) and (6), q _{1 and j} can be described by the following set of linear illegal equations.

Since y ″ = 1−q _{1, j} from equation (7), the following holds.

Similarly, q _{2, j} ε {0,1} is defined as q _{2, j} = (N (j) εG ₂ ). That is, q _{2, j} = 1 when the group G ₂ is assigned to the node N (j), and q _{2, j} = 0 when the group G ₂ is not assigned to the node N (j). Then, from Equations (5) and (6), q _{2 and j} can be described by the following set of linear illegal equations.

Since z ″ = 1−q _{2, j} and _{Σρ (χ) εd (j)} 1 = # D (j) from the equation (9), the following holds.

なる評価関数（すなわち、Σ_{ｊ∈｛０，・・・，ｎ−１｝}（ｗ_ｊ，_１・ｑ_１，ｊ＋ｗ_ｊ，_２・ｑ_２，ｊ））を最小化する問題に帰着できる。 From Eqs. (8) and (10), the problem of minimizing the value of Eq. (3) is related to ∀N (j) ∈Vg. (Linear constraint 1) q _{1, j} + _{Σρ (χ) ∈D (j)} ρ (χ)) ≦ # D (j),
(Linear constraint 2) q _{1, j} + d (ρ (χ)) ≧ 1, for ∀ρ (χ) ∈D (j)
(Linear constraint 3) q _{2, j} −Σρ _{(χ) ∈D (j)} d (ρ (χ)) ≦ 0,
(Linear constraint 4) For ∀ρ (χ) ∈D (j), q _{2, j} −d (ρ (χ)) ≧ 0
Under the linear constraint

Can be reduced to the problem of minimizing the evaluation function (ie, Σ _{jε {0,..., N−1}} (w _j , ₁ · q _{1, j} + w _j , ₂ · q _{2, j} )).

Further, critical node N (j ₁ ) and N (j ₂ ) corresponding to the pair of input values of pairing satisfy d (j ₁ ) + d (j ₂ ) = 1∈F ₂ , and critical node N (j ₃ ) And its ancestor node critical node N (j ₄ ) satisfy d (j ₃ ) + d (j ₄ ) = 0∈F ₂ . The linear constraint is d (j ₁ ) + d (j ₂ ) = 1∈F ₂ for critical nodes N (j ₁ ) and N (j ₂ ) corresponding to the paired input value pair (linear constraint 5) , Further includes that d (j ₃ ) + d (j ₄ ) = 0∈F ₂ for the critical node N (j ₃ ) and the critical node N (j ₄ ) that is an ancestor node (linear constraint 6) Good.

By inputting the above evaluation function (Equation 11) and linear constraints into an arbitrary 0-1 integer programming algorithm, q _1,0 ,..., Q _{1, n−1} , q _2,0 ,. • Obtain an exact or approximate solution of q2 _{, n-1} .

  Next, an example in which the above search method is applied to the method of the first embodiment will be described. In the following, differences from the items described so far will be mainly described, and the items already described will be simplified by using the same reference numerals.

<Configuration>
As illustrated in FIG. 1, the structure conversion device 2 according to the present embodiment includes an input unit 11, a storage unit 12, a control unit 13, a graph construction unit 141, a linear constraint setting unit 142, a matrix generation unit 143, a matrix transformation unit 144, A determination unit 145 and a structure allocation unit 247 are included. The structure allocation unit 247 includes a linear constraint setting unit 247a, an evaluation function setting unit 247b, a search unit 247c, and an allocation unit 247d. The structure conversion device 2 is configured, for example, by reading a predetermined program into the above-described computer.

<Processing>
The processing of this embodiment will be described with reference to FIG. First, instead of the structure conversion apparatus 1, the structure conversion apparatus 2 executes the processes of steps S141 to S145 described above. If it is determined in step S145 that allocation is possible, the following process in step S247 is executed.

In step S247, first, the dependency graph graph (A ₁ ) is input to the linear constraint setting unit 247a. The linear constraint setting unit 247a sets and outputs a linear constraint including the above-mentioned (linear constraint 1)-(linear constraint 6) using the dependency graph graph (A ₁ ) (step S247a).

The dependency function graph graph (A ₁ ) is input to the evaluation function setting unit 247b. The evaluation function setting unit 247b sets and outputs the evaluation function of Expression (11) using the dependency graph graph (A ₁ ) (step S247b).

The search operation unit 247ac receives the linear constraint obtained in step S247a and the evaluation function obtained in step S247b. The search operation unit 247ac inputs these linear constraints and evaluation functions to an arbitrary 0-1 integer programming algorithm, whereby q _1,0 ,..., Q _{1, n−1} , q _2,0 , .., Q _{2, n-1} are obtained and output as exact or approximate solutions (step S247c).

The allocation unit 247d _{includes, q 1,0, ···, q 1} , n-1, q 2,0, ···, is a solution of _{q 2, n-1} are inputted. According to these, the assigning unit 247d assigns at least one of the groups G ₁ and G _{2 to} all the nodes N (j) (where j = 0,..., N−1) of the dependency graph graph (A ₁ ). assign. Assignment section 247d, for _{example, q 1,} j = 1 or group assignment _{G 1} to node N (j) in the case of _{q 2, j = 0, q} 1, j = 0 or _{q 2,} the case of j = 1 assign group _{G 2} to the node N (j) to. Allocation unit 247d includes a set consisting of the dependency graph dependency graph Thus the group G ₁ obtained consists assigned nodes, and the group G ₂ consisting of the assigned node, the dependency graph `graph (A ₃ ) Is output (step S247d).

[Other variations]
The present invention is not limited to the above-described embodiment. For example, after executing the process of step S141, the processes of steps S247a to S247d may be executed without executing steps S142 to S145. Further, the present invention is not only the pairing type conversion, the decomposing generally a process comprising the process comprising a calculation of the algebraic structure G from the calculation of the algebraic processing an operational structures G ₁ and algebraic structure G ₂ Applicable. For example, the linear constraint q (s (i, φ (0))) +... + Q (s (i, φ (S (i) −1))) exemplified in the first embodiment = y (i, n ) Is not limited, and any S (i) (for example, S (i) ≧ 3), {s (i, φ (0)),..., S (i, φ (S (I) -1))}, y (i, n) may be set. Further, the evaluation function exemplified in the second embodiment is not limited to Σ _{j∈ {0,..., N−1}} (w _j , ₁ · q _{1, j} + w _j , ₂ · q _{2, j} ). Depending on the purpose, other polynomials including q _{1, j} and q _{2, j} may be used as the evaluation function.

  The various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. Needless to say, other modifications are possible without departing from the spirit of the present invention.

  When the above configuration is realized by a computer, the processing contents of the functions that each device should have are described by a program. By executing this program on a computer, the above processing functions are realized on the computer. The program describing the processing contents can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  This program is distributed, for example, by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads a program stored in its own recording device and executes a process according to the read program. As another execution form of the program, the computer may read the program directly from the portable recording medium and execute processing according to the program, and each time the program is transferred from the server computer to the computer. The processing according to the received program may be executed sequentially. The above-described processing may be executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition without transferring a program from the server computer to the computer. Good.

  In the above embodiment, the processing functions of the apparatus are realized by executing a predetermined program on a computer. However, at least a part of these processing functions may be realized by hardware.

1, 2 structure converter

Claims (9)

n is an integer of 2 or more, j = 0,..., n−1, F ₂ is a finite field of order 2, and a dependency graph representing the dependency of operations in the algebraic structure G Q (j) = 0εF ₂ when assigning the algebraic structure G ₁ to the node N (j) of the node, and q (j) = 1ε when assigning the algebraic structure G ₂ to the node N (j). F ₂ , G ₁ ≠ G ₂ , m is an integer of 1 or more, i = 0,..., M−1, S (i) is an integer of 1 or more, {s ( i, φ (0)),..., s (i, φ (S (i) -1))} ⊆ {0,.
For a linear constraint q (s (i, φ (0))) +... + Q (s (i, φ (S (i) −1))) = y (i, n) ∈F ₂ , {0 ,..., N−1}, y (i) about the element r of the complement of {s (i, φ (0)),..., S (i, φ (S (i) −1))} , R) = 0, and y (i, k) = 1 for the element k of {s (i, φ (0)),..., S (i, φ (S (i) −1))}. A matrix generation unit for obtaining information representing a matrix having y (i, 0),..., Y (i, n-1), y (i, n) as elements of the i-th row;
From the matrix having y (i, 0),..., y (i, n-1) and y (i, n) as elements in the i-th row, z (i, 0),. A matrix transformation unit for obtaining information representing a staircase matrix having (i, n-1) and z (i, n) as elements of the i-th row;
It is determined whether or not the node N (j) is an independent node based on the information representing the step matrix, and the algebraic structure G ₁ or the algebraic structure G ₂ is assigned to the node N (j). A structure assignment unit;
A structure conversion device. The structure conversion device according to claim 1,
(1) When the step matrix includes a row where z (0,0) = 1 and a row where z (1,1) = 0, the node N (1) is determined to be an independent node; 2) z (ω, 0) = ... = z (ω, t (ω) −1) = 0 and z (ω, t () for an integer t (ω) where the step matrix is 1 or more and n−2 or less. ω)) = 1 and a node where z (ω + 1, t (ω) +1) = 0 are included, it is determined that the node N (t (ω) +1) is an independent node, (3) The step matrix is z (m−1,0) =... = Z (m−1, t (m−1) −1) = 0 and z (m−1, t (m−1)) = 1. , N (n−1) is a separate determination node that determines that the node N (t (m−1) +1),..., N (n−1) is an independent node. The structure conversion device according to claim 2,
The structure allocating unit adds the algebraic structure G ₁ and the algebraic structure G to the node N (ν) (where νε {0,..., N−1}) determined to be an independent node. ₂ is assigned, the algebraic structure G ₁ or the algebraic structure is assigned to the other node (η) (where η∈ {0,..., N−1} and η ≠ ν). assign structures _{G 2,} structure conversion device. The structure conversion device according to any one of claims 1 to 3,
When the staircase matrix includes elements such that z (ι, 0) =... = Z (ι, n−1) = 0 and z (ι, n) = 1, assignment with the linear constraint is impossible. The structure conversion apparatus which has the 2nd determination part which determines with being. The structure conversion device according to any one of claims 1 to 4,
The dependency graph represents a group operation dependency included in an algorithm for obtaining an input value of a symmetric bilinear map,
The algebraic structure G is a group and forms a domain G × G of the symmetric bilinear map,
The algebraic structure G ₁ and the algebraic structure G ₂ are groups different from each other, and form a domain G ₁ × G ₂ of an asymmetric bilinear map,
S (i) = 2,
The linear constraint corresponding to the nodes N (j ₁ ) and N (j ₂ ) corresponding to the same symmetric bilinear mapping input value pair is q (j ₁ ) + q (j ₂ ) = 1∈F ₂
The node N _{(j 3)} and the node N _{(j 3)} the node N _{(j 4)} corresponding to said linear constraints _q (j 3) is an ancestor node of _{+ q (j 4) = 0∈F} 2 The structure conversion device. n is an integer of 2 or more, j = 0, ···, a n-1, algebraic structure G ₁ to node N (j) of the dependency graph representing the operation of the dependencies in algebraic structure G Q _{1, j} = 1 and q _{2, j} = 0, and when assigning the algebraic structure G ₂ to the node N (j), q _{1, j} = 0 and q _{2, j} = 1, When G ₁ ≠ G ₂ and when assigning the algebraic structure G ₁ to the node N (j), d (j) = 0, and when assigning the algebraic structure G ₂ to the node N (j) d (j) = 1, and descendant nodes of the node N (j) are DN (ρ (j, 0)),..., DN (ρ (j, # D (j) −1)), D (j) is a set {ρ (j, 0),..., Ρ (j, # D (j) −1)}, and #D (j) is the number of elements of the set D (j). Yes,
Based on the dependency graph, q _{1, j} + _{Σρ (χ) ∈D (j)} d (ρ (χ)) ≦ # D (j), and q for ∀ρ (χ) ∈D (j) _{1, j} + d (ρ (χ)) ≧ 1, q _{2, j} −Σρ _{(χ) ∈D (j)} d (ρ (χ)) ≦ 0, and ∀ρ (χ) ∈D ( a linear constraint setting unit that sets a linear constraint including _{j 2,} q _{2, j} −d (ρ (χ)) ≧ 0;
Under the linear constraint, the output value of the linear evaluation function f (q _1,0 ,..., Q _{1, n−1} , q _2,0 ,..., Q _{2, n−1} ) is predetermined. and satisfies _{q 1,0, ···, q 1,} n-1, q 2,0, ···, evaluation search unit for determining a _{q 2, n-1,}
A structure conversion device. The structure conversion device according to claim 6,
| G _σ | is the amount of information necessary to express the element of the algebraic structure G _σ with respect to σ∈ {1, 2}, and w _j is a weighting factor predetermined for the node N (j) Yes, w _j , _σ = w _j · | G _σ |, and the evaluation function is f (q _1,0 ,..., Q _{1, n−1} , q _2,0 ,..., Q _{2. , N−1} ) = Σ _{j∈ {0,..., N−1}} (w _j , ₁ · q _{1, j} + w _j , ₂ · q _{2, j} ), and the predetermined condition is the evaluation A structure converter that minimizes the output value of a function. The structure conversion device according to claim 6 or 7, wherein
The dependency graph represents a group operation dependency included in an algorithm for obtaining an input value of a symmetric bilinear map,
The algebraic structure G is a group and forms a domain G × G of the symmetric bilinear map,
The algebraic structure G ₁ and the algebraic structure G ₂ are groups different from each other, and form a domain G ₁ × G ₂ of an asymmetric bilinear map,
The linear constraint is d (j ₁ ) + d (j ₂ ) = 1 for the nodes N (j ₁ ) and N (j ₂ ) corresponding to the same symmetric bilinear mapping input value pair, further comprising the fact the node N _{(j 3)} and the node N _{(j 3)} the node N _{(j 4)} and the _d (j 3) is an ancestor node of + d _(j 4) = 0, structure conversion apparatus.   A program for causing a computer to function as the structure conversion device according to claim 1.

Images