JP5980178B2 - Program conversion apparatus, program conversion method, and program - Google Patents

Description

  The present invention relates to a technique for converting a program on a pairing group using a certain elliptic curve into a program on a pairing group using a different elliptic curve.

In recent years, various cryptographic primitives using bilinear mapping called pairing have been proposed. The bilinear mapping used in the cryptographic field is a function for performing a pairing operation defined at two points on a certain elliptic curve. Specifically, let G ₁ , G ₂ , and G _{T be} a group of prime orders q, and e: G ₁ × G ₂ → G _T can be efficiently calculated, and any generator g∈G ₁ , This is a mapping with the property that e (g ^a , h ^b ) = e (g, h) ^ab , e (g, h) ≠ 1 for h∈G ₂ and any a, b∈Z _q . Such a set of groups λ _q = (G ₁ , G ₂ , G _T ) is called a pairing group.

In this case, the equation (1) consisting of constants A _i , C _i ∈ G ₁ , B _i , D _i ∈ G ₂ , d _ij ∈ Z _q and variables Y _i ∈ G ₁ , X _i ∈ G _{2 is} expressed as This is called the pairing product equation for variables X _i and Y _i . In particular, a case where a variable appears only in one group is called a linear expression, and the other case is called a non-linear expression.

A pairing group in which G ₁ = G ₂ is called a type I pairing group. In the type I pairing group, G ₁ and G ₂ are not particularly distinguished from _{each other,} and are simply written as G. For example, Non-Patent Document 1 describes an ID-based encryption method using a type I pairing group.

On the other hand, for G ₀ ≠ G ₂ and for randomly chosen non-zero a, b∈Z _q , finding h ^a ∈G ₂ without knowing the value of a from g ^a ∈G ₁ , and When it is difficult to find g ^b εG ₁ without knowing the value of b from h ^b εG ₂ , the pairing group is called a type III pairing group. Here, Z _q is a remainder ring with q as the order. For example, Non-Patent Document 2 describes an ID-based encryption method and signature method using a type III pairing group.

The type I pairing group has a feature that the method is easy to describe and it is not necessary to consider which group the group element belongs to. Therefore, it is convenient for the construction of a cryptographic protocol that combines a plurality of various cryptographic primitives such as a signature, zero knowledge proof, and public key cryptography. However, the type I pairing group uses a special elliptic curve, which is inferior in safety. In fact, the solution of the discrete logarithm problem in the group G _T Type I is progressing.

Since type III pairing groups do not have an efficient mapping between group G ₁ and group G ₂ , it is always necessary to consider which group the group element belongs to. Therefore, special consideration is required for the notation and design of the system. However, the type III pairing group has a more general structure and is considered to be excellent in safety. Therefore, in the same safety parameter, the type III pairing group has a feature that the bit representation of the group element can be shortened compared to the type I pairing group.

  Techniques have been proposed for converting an encryption scheme on a pairing group into an encryption scheme on a different pairing group. For example, Non-Patent Document 3 and Non-Patent Document 4 describe a method of converting an encryption system configured with a paired group of composite orders into an encryption system configured with a pairing group of prime orders. Yes. However, a method for converting an encryption method on a type I pairing group to an encryption method on a type III pairing group has not been proposed.

Brent Waters, “Efficient Identity-Based Encryption Without Random Oracles”, Advances in Cryptology-EUROCRYPT 2005, Lecture Notes in Computer Science, vol. 3494, pp. 114-127, 2005. Jie Chen, Hoon Wei Lim, San Ling, Huaxiong Wang, Hoeteck Wee, “Shorter IBE and Signatures via Asymmetric Pairings”, Pairing-Based Cryptography-Pairing 2012, Lecture Notes in Computer Science, vol. 7708, pp. 122-140, 2013. Allison Lewko, “Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting”, Advances in Cryptology-EUROCRYPT 2012, Vol. 7237, pp. 318-335, 2012. David Mandell Freeman, “Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups”, Advances in Cryptology-EUROCRYPT 2010, Vol. 6110, pp. 44-61, 2010.

  A scheme (primitive or protocol) designed and described in a type I pairing group does not necessarily operate directly in a type III pairing group.

As a simple example, consider method A on a type I pairing group. Method A is to include pairing operation comprising e (X, X) with respect to the group element X∈G _1. Since G ₁ = G ₂ for Type I, this operation can be performed. However, if we try to implement method A using a type III pairing group, X ~ ∈G ₂ corresponding to the group element X∈G ₁ cannot be found, so the pairing operation e (X, X) The corresponding operation cannot be executed. As another example, method A on a pairing group of type I has a pairing operation of e (X, Y) and a group operation of Z ← X · Y (here, ). In type I, all these operations can be executed. In the case of type III, X∈G ₁ and Y∈G ₂ may be used so that the pairing operation e (X, Y) can be calculated. However, the group operation X · Y cannot be calculated. Conversely, in order to be able to calculate group operations X and Y, both X and Y should be group elements of G ₁ (or G ₂ ), but then the pairing operation e (X, Y) It cannot be calculated. Therefore, method A on a type I pairing group cannot be directly implemented in a type III pairing group.

  The above describes the operation in the system, but the same can be said for the operation in the system security proof. For example, if a pairing operation e (X, X) is performed during the proof of a certain method, the method itself does not use the pairing operation e (X, X) and type III pairing Even if it is operable in the group, the safety of the implementation in Type III is not guaranteed because the safety proof is not valid.

  An object of the present invention is to convert a system that has been proven to be safe by operating on a type I pairing group to a system that operates on a type III pairing group.

In order to solve the above problems, a program conversion apparatus of the present invention includes a duplexing unit, a group operation conversion unit, a pairing operation conversion unit, and an equivalence checking conversion unit. In this invention, G ₁ , G ₂ , G _T are groups of prime order q, g is a generator of group G ₁ , h is a generator of group G ₂ , and x is a modulo ring modulo q the original Z _q, the pairing operation type I is bilinear mapping of _{G 1 × G 1 → G T} , pairing operation type III is bilinear mapping of _{G 1 × G 2 → G T} . The duplexing unit receives as input a program including at least one type I pairing operation, and the variable X ~ corresponding to the variable X = g ^x on the group G ₁ used in the calculation process of the program on the group G ₂ = h Generates ^x . The group operation conversion unit generates a group operation using the variable on the group G ₂ for the group operation using the variable on the group G ₁ included in the program. Pairing operation converting unit type to a type I pairing operation to enter the two variables on the group G ₁ included in the program, as input variables and variables on the group G ₂ on the group G ₁ III To the pairing operation. The equivalence checking conversion unit is a type III variable in which the equivalence checking between the variables on the group G ₁ and the variables on the group G ₂ included in the program is input to the variables on the group G ₁ and the generation source of the group G ₂ . converted into equations and using a pairing operation type III to type the pairing operation and the group G ₂ on the variables and generator of the group G _1.

  According to the present invention, it is possible to describe an algorithm with a type I pairing group that is simple in notation and does not require special attention in design, and can implement it with an efficient type III pairing group. . As a result, in the type I pairing group, safety can be improved without significantly changing the implementation and description.

FIG. 1 is a diagram illustrating a functional configuration of the program conversion apparatus. FIG. 2 is a diagram illustrating a processing flow of the program conversion method. FIG. 3 is a diagram illustrating the state of the directional graph. FIG. 4 is a diagram illustrating the state of the directional graph. FIG. 5 is a diagram illustrating the state of the directionality graph. FIG. 6 is a diagram illustrating the state of the directional graph. FIG. 7 is a diagram illustrating the state of the directional graph.

  Hereinafter, embodiments of the present invention will be described in detail. In addition, the same number is attached | subjected to the component which has the same function in drawing, and duplication description is abbreviate | omitted.

[Embodiment]
An example of a functional configuration of the program conversion apparatus according to the embodiment will be described with reference to FIG. The program conversion apparatus 1 according to the embodiment includes a duplex unit 10, a conversion unit 20, a control unit 101, and a memory 102. The duplexing unit 10 includes a graph construction unit 12, a subgraph replication unit 14, an edge switching unit 16, and a subgraph deletion unit 18. The conversion unit 20 includes a group operation conversion unit 22, a pairing operation conversion unit 24, and an equivalence check conversion unit 26. The program conversion apparatus 1 is a special program configured by a special program loaded into a known or dedicated computer having a central processing unit (CPU), a main storage (Random Access Memory, RAM), and the like. Device. The program conversion apparatus 1 executes each process under the control of the control unit 101, for example. The data input to the program conversion apparatus 1 and the data obtained in each process are stored in, for example, the memory 102, and the data stored in the memory 102 is read out as necessary and used for other processes. .

  With reference to FIG. 2, an example of the processing flow of the program conversion method will be described according to the order of procedures actually performed.

  The program conversion apparatus 1 is operated on a type I pairing group and receives a program α that implements a method A that has been proven to be safe. The program A operates on a type III pairing group and can guarantee safety. Outputs the program α that implements '.'

  Assume that the security of a scheme A is shown by the existence of a set of algorithms called reduction. Note that method A itself is a set of algorithms. In method A and its reduction algorithm (hereinafter these algorithms are simply referred to as algorithm A), the operations related to group elements of type I pairing groups include group membership checks and comparisons between group elements in the same group (hereinafter referred to as "group A"). , Sometimes referred to as equivalence checking), limited to group operations and pairing operations.

  In step S10, the duplexing unit 10 generates a directional graph T from the input program α on the type I pairing group, and the directional graph T ′ obtained by converting the directional graph T so that it can operate in type III. Is output. The directionality graph T ′ is input to the conversion unit 20. Hereinafter, the process of the duplexer 10 will be described in more detail.

  In step S12, the graph construction unit 12 receives the program α on the type I pairing group as an input, and generates a directional graph T based on the program α. First, the graph construction unit 12 represents the entire group operation of the algorithm A by a directional graph. In the description of algorithm A, it is assumed that each group element appearing as an input, output, or intermediate result is given a unique label. This label is called a variable. In the directivity graph, all variables handled by the algorithm are assigned to nodes, and the node of the variable storing the result from the assigned variable to which the group operation is performed has an edge. The pairing operation is represented by a node having a unique label (hereinafter referred to as a pairing node). The pairing node has an edge toward two nodes to which variables input to the pairing calculation are assigned. A node having no input edge is called an input node, and a variable assigned to the input node is called an input variable. Considering a digital signature scheme as an example, typically an input node is assigned a message to be signed and an instance of a difficulty problem to be reduced. The directionality graph thus generated from the program α is denoted by T. The direction graph T may be composed of several separated graphs.

An example of the directionality graph T is shown in FIG. In the example of FIG. 3, the nodes are drawn with solid circles, and the pairing nodes are drawn with dashed-dotted circles. The edge representing the group operation is a solid arrow, and the direction of the arrow is from the node to be calculated to the node of the calculation result. The edge representing the pairing calculation is a one-dot chain line arrow, and the direction of the arrow is from the pairing node to the calculation target node. As shown in FIG. 3, the algorithm A shown in the direction graph T includes a group operation X ₃ ← X ₁ · X _2, a group operation X ₄ ← X ₂ · X ₃ , X ₆ ← X ₂ · A group operation X _5, a group operation X ₈ ← X ₆ · X _7, a group operation X ₃ ← Y ₁ · Y _2, and a pairing operation e (X ₄ , X ₈ ) are included. In the directional graph T, input nodes are nodes X ₁ , X ₂ , X ₅ , X ₇ , Y ₁ , Y ₂ .

For the node X included in the direction graph T, the “X subgraph” refers to a graph including all nodes having a path reaching the node X (except for a pairing node) and its edges. In the example of FIG. 3, “X ₈ subgraph” is a graph composed of a portion surrounded by a dotted line, that is, nodes X ₂ , X ₅ , X ₆ , X ₇ , X ₈ and edges connecting each node.

Since the subgraph of node X means generation of node X through a chain of group operations, variables included in the subgraph need to belong to the same group in type III. On the other hand, since type III pairing operations are performed on variables belonging to different groups, if two nodes included in the same subgraph are connected via a pairing node, the algorithm does not work on type III . In the example of FIG. 3, since the node X ₂ is included in both the subgraph of the node X _{4 and} the subgraph of the node X ₈ connected to the pairing nodes P _{X4 and X8} , the algorithm A represented in the direction graph T is It can be seen that it does not work on the type III pairing group.

In step S14, the subgraph duplicating unit 14 selects one of the edges connected to the pairing node, and duplicates the subgraph of the node connected to the edge. That is, when algorithm A calculates the pairing operation e (X, Y), it selects either X or Y node (hereinafter, X is selected), and the subgraph of the selected node X is Duplicate. Give different variable names to the nodes in the duplicated subgraph. For example, the copied node is given a variable name with a symbol with “~” (tilde) added to the original variable name. If a graph having a node with a variable name with a tilde already exists by the preceding processing, it is merged with the graph. A node replicated in this way is called a replication node. In the following description, a node belonging to the group G ₁ may be expressed as a node X, and a replication node corresponding to the node X may be expressed as a replication node X˜.

FIG. 4 shows an example of the directional graph T after the subgraph duplication unit 14 duplicates the subgraph. In the example of FIG. 4, the duplicate node is drawn with a dashed circle. This example selects the edge leading to node X ₈ of the two edges of the pairing node P _{X4, X8,} it is replicating subgraph node X _8. Specifically, the nodes X ₂ , X ₅ , X ₆ , X ₇ , and X ₈ are duplicated to generate duplicate nodes X to ₂ , X to ₅ , X to ₆ , X to ₇ , and X to ₈ .

In step S16, the edge switching unit 16 switches the edge from the pairing node toward the node X to the duplicate node X˜. FIG. 5 shows an example of the directional graph T after the edge switching unit 16 switches the edge of the pairing node. In this example, of the two edges of the pairing nodes P _{X4 and X8} , the edge connected to the node X ₈ is connected to the replication nodes X to ₈ .

In step S <b> 18, the subgraph deletion unit 18 confirms whether or not a subgraph that is not connected to another graph is generated, and deletes the entire subgraph. FIG. 6 shows an example of the directivity graph T when the subgraph deletion unit 18 specifies a subgraph to be deleted. In this example, nodes X ₅ , X ₆ , X ₇ , X that are no longer input to other nodes among the nodes included in the subgraph of node X ₈ where the edges of pairing nodes P _{X4, X8} are cut off ₈ is selected as the subgraph to be deleted. FIG. 7 shows an example of the directionality graph T in a state where the selected subgraph is deleted.

  The duplexer 10 performs the processing from step S14 to step S18 on all pairing nodes included in the directionality graph T. The entire graph obtained as a result is output as a directional graph T '.

  From which pairing node of the pairing nodes included in the directivity graph T in step S14, and which edge of the two edges connected to the pairing node to select in step S16, Several methods are conceivable. It is desirable to make a selection so that the finally obtained directional graph T ′ is small because the efficiency of the algorithm A ′ after the conversion is improved. However, in this invention, any selection may be made. Absent.

  In step S20, the conversion unit 20 converts each operation on the type I pairing group included in the program α into an operation on the type III pairing group based on the input directional graph T ′. The program α ′ on the type III pairing group is output. Hereinafter, the process of the conversion unit 20 will be described in more detail.

In step S22, the group operation conversion unit 22 performs the group operation on the type I pairing group for the node X included in the program α based on the input directional graph T ′ for the corresponding replication node X˜. Generate group operations on type III pairing groups. When the processing of the group operation conversion unit 22 is applied to the example of FIG. 7, a group operation of X ~ ₆ ← X ~ ₂ · X ~ _{5 and} a group operation of X ~ ₈ ← X ~ ₆ · X ~ ₇ are generated. Become.

In step S24, the pairing calculation conversion unit 24 determines the node X and the nodes X˜ for the type I pairing calculation with the node X included in the program α as an input based on the input directional graph T ′. Convert to input type III pairing operation. Applying the process of pairing operation converting section 24 in the example of FIG. 7 will convert e (X _4, X ₈₎ comprising a pairing operation e to (X _4, X ~ ₈₎ consisting pairing operation.

In step S26, the equivalence checking conversion unit 26 converts the equivalence checking between the node X and the duplicate node X ~ into an equation using a type III pairing operation with the node X and the duplicate node X ~ as inputs. To do. Specifically, with g as the generator of group G ₁ , h as the generator of group G ₂ , A as the element of group G ₁ , and B as the element of group G ₂ , It may be replaced with equation (2).

A can be expressed as g ^a, and B can be expressed as h ^b , where a, bεZ _q . Therefore, the equation (2) can be expressed as the following equation (3).

  Equation (3) can be transformed into Equation (4) due to the nature of the pairing operation.

Therefore, equivalence checking conversion section 26, different groups G _1, the comparison between the group elements A∈G ₁ and B∈G ₂ belonging to G _2, the value a that belong to the same residue ring Z _q, the B∈Z _q It can be said that it is converted to comparison.

  In this way, the program conversion technique of the present invention converts the program α on the type I pairing group into the program α ′ on the type III pairing group. The type I pairing group is simple to describe because there is only one base group, and does not require special attention in the design of the algorithm, but may be inferior in safety because of the special group. On the other hand, the type III pairing group has two base groups, so the description is somewhat complicated and the design of the algorithm requires attention. However, because it is a more general group, it is said to be safe.

  However, algorithms designed for Type I pairing groups may not work in Type III pairing groups no matter how the input group elements are divided into two groups. Need attention. An object of the present invention is to provide means for adding group elements and operations so that an algorithm designed for a type I pairing group operates in a type III pairing group. The scene to be provided by the present invention may be determined in view of characteristics such as safety required for the algorithm.

[Program, recording medium]
The present invention is not limited to the above-described embodiment, and it goes without saying that modifications can be made as appropriate without departing from the spirit of the present invention. The various processes described in the above-described embodiments are not only executed in time series according to the order described, but may be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes.

  When various processing functions in each device described in the above embodiment are realized by a computer, the processing contents of the functions that each device should have are described by a program. Then, by executing this program on a computer, various processing functions in each of the above devices are realized on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

  The program is distributed 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, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

DESCRIPTION OF SYMBOLS 1 Program conversion apparatus 10 Duplexing part 12 Graph construction part 14 Subgraph replication part 16 Edge switching part 18 Subgraph deletion part 20 Conversion part 22 Group operation conversion part 24 Pairing operation conversion part 26 Equivalence check conversion part 101 Control part 102 Memory

Claims (7)

G ₁ , G ₂ , G _T are groups of prime order q, g is a generator of group G ₁ , h is a generator of group G ₂ , and x is a modulo ring Z _{q element} modulo _q And the type I pairing operation is a G ₁ × G ₁ → G _T bilinear map, and the type III pairing operation is a G ₁ × G ₂ → G _T bilinear map,
A program including at least one type I pairing operation is used as an input, and a variable X ~ = h ^x corresponding to the variable X = g ^x on the group G ₁ used in the calculation process of the above program on the group G ₂ A duplexer that generates
For group operations using variables on the group G ₁ included in the program, a group operation conversion unit that generates group operations using variables on the group G ₂ ;
Type I pairing operation with two variables on the group G ₁ included in the program as input, type III pairing with the variables on the group G ₁ and variables on the group G ₂ as inputs A pairing calculation conversion unit for converting to calculation;
A type III pairing operation in which the equivalence check between the variable on the group G ₁ and the variable on the group G ₂ included in the program is input to the variable on the group G ₁ and the generation source of the group G ₂ And an equivalence checking conversion unit for converting to an equation using a type III pairing operation that takes as input a variable on the group G ₂ and a generator of the group G ₁ ,
A program conversion apparatus including: The program conversion device according to claim 1,
The duplex part is
With the program as an input, the variables on the group G ₁ are represented as nodes, the type I pairing operations included in the program are represented as pairing nodes, and the operation target nodes of the group operations included in the program are A direction that represents the structure of the program by connecting the nodes to be operated and the pairing nodes for the type I pairing operation included in the program by the edge, connected by an edge representing input / output to the operation. A graph construction unit to convert to a sex graph;
Select any edge connected to the pairing node, and use the group connected to the selected edge as a leading node based on a subgraph consisting of a series of nodes connected to the leading node by a chain of edges. duplicating nodes representing variables on G ₁ generates a node representing the variables on the group G _2, the node that so that equal upper Symbol subgraph structure representing the variables on the group G ₂ the edge A subgraph duplication unit that duplicates the subgraph by connecting with
An edge switching section for connecting the selected edge to a node representing the variables on the group G ₂ corresponding to the first node,
If there is a node that does not have an edge representing an output to another node in the directional graph, a subgraph deletion unit that deletes a subgraph composed of a series of nodes connected to the node by a chain of edges;
A program conversion apparatus including: The program conversion device according to claim 1 or 2,
The g and a generator of the group G _1, and h is a generator of the group G _2, the A and the group member of the group G _1, and the B and group member of the group G _2, the e the pairing operation of the type III ,
The equivalence checking conversion unit replaces the equivalence checking A = B included in the program with the following expression:

Program conversion device. A program conversion method executed by a program conversion apparatus including a duplication unit, a group operation conversion unit, a pairing operation conversion unit, and an equivalence checking conversion unit,
G ₁ , G ₂ , G _T are groups of prime order q, g is a generator of group G ₁ , h is a generator of group G ₂ , and x is a modulo ring Z _{q element} modulo _q And the type I pairing operation is a G ₁ × G ₁ → G _T bilinear map, and the type III pairing operation is a G ₁ × G ₂ → G _T bilinear map,
The duplication unit receives a program including at least one type I pairing operation as an input, and the variable corresponding to the variable X = g ^x on the group G ₁ used in the calculation process of the program on the group G ₂ A duplication step to generate X ~ = h ^x ;
The group arithmetic conversion unit, the group operation using a variable on the group G ₁ that is included in the program, a group operation converting step of generating a group operation using a variable on the group G _2,
The pairing operation conversion part, a pairing computation of type I to type the two variables on the group G ₁ that is included in the program, the variables and variables on the group G ₂ on the group G ₁ A pairing calculation conversion step for converting to an input type III pairing calculation;
The equivalence checking conversion unit inputs equivalence checking between the variable on the group G ₁ and the variable on the group G ₂ included in the program, and the variable on the group G ₁ and the generation source of the group G ₂ An equivalence check conversion step for converting into an equation using a type III pairing operation and a variable on the group G ₂ and a type III pairing operation with the generation source of the group G ₁ as inputs,
A program conversion method including: The program conversion method according to claim 4,
The duplexing unit includes a graph construction unit, a subgraph replication unit, an edge switching unit, and a subgraph deletion unit,
The duplexing step is
The graph construction unit takes the program as an input, represents a variable on the group G ₁ as a node, represents a type I pairing operation included in the program as a pairing node, and includes a group operation included in the program. By connecting the nodes to be operated with an edge representing input / output to the operation, and connecting each node to be operated with the pairing node for the type I pairing operation included in the program by the edge, A graph construction step for converting to a directional graph representing the structure of the program;
The subgraph duplicating unit selects any edge connected to the pairing node, the node connected to the selected edge as a head node, and a subgraph composed of a series of nodes connected to the head node by the chain of edges. based on duplicates nodes representing variables on the group G ₁ generates a node representing the variables on the group G _2, the variables on the group G ₂ so as to be equal to the upper Symbol subgraph structure the node representing by connecting the said edge, and subgraph replication step of replicating the sub-graph,
The edge switching unit, an edge switching step of connecting the selected edge to a node representing the variables on the group G ₂ corresponding to the first node,
The subgraph deletion unit deletes a subgraph composed of a series of nodes connected to the node by a chain of edges if there is a node that does not have an edge representing an output to another node in the directivity graph. Steps,
A program conversion method including: The program conversion method according to claim 4 or 5, wherein
The g and a generator of the group G _1, and h is a generator of the group G _2, the A and the group member of the group G _1, and the B and group member of the group G _2, the e the pairing operation of the type III ,
The equivalence checking conversion step replaces the equivalence checking A = B included in the program with the following equation:

Program conversion method.   The program for functioning a computer as a program conversion apparatus in any one of Claim 1 to 3.

Images