JP6691491B2 - Pairing conversion device, pairing conversion method, program - Google Patents

Description

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

Non-Patent Document 1 is known as a conventional technique for converting an algebraic structure of an algorithm. Non-Patent Document 1, the group G, the pairing on G _T e: an algorithm using G × G → G _T, the group G _0, G _1, pairing on _{G T e: G 0 × G} 1 → A technique of converting to an algorithm using G _T (where G ₀ ≠ G ₁ ) is disclosed. In this technique, the group G ₀ or G ₁ is assigned to a node of the dependency graph of the group operation on the group G, the assignment state is evaluated by an evaluation function, and the assignment with the best evaluation is selected. Further, Non-Patent Document 2 describes a technique for speeding up the selection of the allocation by using an integer programming method.

Masayuki Abe, Jens Groth, Miyako Ohkubo, and Takeya Tango, "Converting cryptographic schemes from symmetric to asymmetric bilinear groups", In Juan A. Garay and Rosario 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. Masayuki Abe, Fumitaka Hoshino, and Miyako Ohkubo, "Design in Type-I, Run in Type-III: Fast and Scalable Bilinear-Type Conversion Using Integer Programming", In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology-CRYPTO 2016 -36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, volume 9816 of Lecture Notes in Computer Science, pages 387 {415. Springer, 2016.

  However, the 0-1 integer programming problem used in the conventional technique generally belongs to a problem class called NP-hardness, and it is not always guaranteed that an exact solution can be obtained in a feasible time. However, if the input problem is limited to a special form, the solution time of the optimization problem may be significantly reduced.

  The present invention is expected to speed up the optimization execution time more than before by controlling the constraints required in the pairing type conversion and limiting the problems input to the 0-1 integer programming problem to a special form. An object of the present invention is to provide a pairing-type conversion device, a pairing-type conversion method, and a program that can be performed.

In order to solve the above problems, according to one aspect of the present invention, a pairing type conversion device for converting an encryption method based on symmetric pairing into an encryption method based on asymmetric pairing is based on symmetric pairing. The input information is the algorithm including the configuration of the cryptosystem, the syntax, the return, and the hypothesis, and the output information is the algorithm including the configuration of the cryptosystem based on the asymmetric pairing, the syntax, the return, and the assumption, and G ₀ and G ₁ are the parts after the division. Graph, x and y are vertices of the graph before division, _b ∈ {0,1}, (x ∈ G _b ) and (y ∈ G _b ) are 1 if the description in () is true and 0 if false The assigned variable, L _y , is a set of descendants of _{y that} are leaves, and a linear constraint setting unit that sets four linear constraints for predetermined division, and the objective function as a linear function for all assigned variables. And the objective function is a nonlinear function of the assigned variable Then, the objective function setting part that converts the objective function into a linear objective function with linear constraints and sets it, and the linear constraint and the linear function or the linear objective function with linear constraints are input to the 0-1 integer programming algorithm to obtain an exact or approximate solution. And an integer programming part that obtains an exact solution or an approximate solution, and one dependency graph that represents an algorithm that includes the configuration, syntax, consequences, and assumptions of a cryptographic method based on symmetric pairing. And a dividing configuration section for dividing into. The linear constraint is that if (1) x is a non-overlapping vertex, (x ∈ G ₀ ) + (x ∈ G ₁ ) = 1, (2) for any x included in L _y , ( _y ∈ G _b ) ≧ (x ∈ G _b ), (3) If x and y are the vertices that are the input pair to the pairing, x + y = 1, (4) x and y are two If it is a non-overlapping vertex, xy = 0.

In order to solve the above problems, according to another aspect of the present invention, a pairing type conversion device is used for converting a cryptographic method based on symmetric pairing into a cryptographic method based on asymmetric pairing. method, structure of the encryption scheme based on symmetric pairing, and syntax, results, input information an algorithm including assumptions, the structure of the encryption scheme based on asymmetric pairing, syntax, return, and output information an algorithm including assumptions, G ₀ And G ₁ are subgraphs after partitioning, x and y are vertices of the graph before partitioning, _b ∈ {0,1}, (x ∈ G _b ) and (y ∈ G _b ) are true in (). Then 1 is an assigned variable that indicates 0 if false, L _y is a set of leaves that are leaves of the descendants of y, and the linear constraint setting step for setting four linear constraints for predetermined division and the objective function are Set as a linear function for all assigned variables and If the number is a nonlinear function of the assigned variable, the objective function setting step that transforms and sets the objective function into a linear objective function with linear constraints, and the linear constraint and linear or linear objective function with linear constraints 0-1 integer programming algorithm And an integer programming step to obtain an exact solution or an approximate solution, and one algorithm expressing the algorithm including the configuration, syntax, consequences, and assumptions of the symmetric pairing-based cryptosystem according to the values of the assigned variables of the exact solution or the approximate solution. A partition configuration step of partitioning the dependency graph into two subgraphs. The linear constraint is that if (1) x is a non-overlapping vertex, (x ∈ G ₀ ) + (x ∈ G ₁ ) = 1, (2) for any x included in L _y , ( _y ∈ G _b ) ≧ (x ∈ G _b ), (3) If x and y are the vertices that are the input pair to the pairing, x + y = 1, (4) x and y are two If it is a non-overlapping vertex, xy = 0.

  According to the present invention, there is an effect that the optimization execution time can be expected to be faster than in the past.

The figure which shows the example of the algorithm which outputs pairing. The figure which shows the dependency graph of the algorithm which outputs pairing. The figure which shows the example of the conversion by the division of the algorithm which outputs pairing. The figure which shows the dependence graph of the conversion by the division | segmentation of the algorithm which outputs pairing. FIG. 5 is a diagram for explaining Constraint 2 for division. The functional block diagram of the pairing type conversion device which concerns on 1st embodiment. The figure which shows the example of the processing flow of the pairing type conversion apparatus which concerns on 1st embodiment. The figure for demonstrating ID-based encryption as the encryption system based on the asymmetric pairing converted using the pairing type conversion apparatus which concerns on 1st embodiment.

  Hereinafter, embodiments of the present invention will be described. In the drawings used in the following description, components having the same function and steps for performing the same process are denoted by the same reference numerals, and duplicate description will be omitted. In the following description, the processing performed for each element of a vector or matrix shall be applied to all the elements of the vector or matrix unless otherwise specified.

<Assumptions>
First, the premise of the first embodiment will be described.
<Preparation>
<Pairing>
In cryptography, pairing is a probabilistic polynomial time algorithm P that generates codes with the following algebraic structure.

1.L, G ₀ , G ₁ and G _T are the same finite commutative ring Q with #Q> 2 ^{Θ (λ)} .
2. The following stochastic polynomial time algorithms are available.
-Samples on L, G ₀ , G ₁ , G _T.
-Addition on L, G ₀ , G ₁ , G _T.
-Multiplication on L.
_-Non -degenerate _bimorphism ^: G _x × L → G _{x, ∀ x ∈ {0,1, T}}
-Non-degenerate bi-homomorphic e: G ₀ × G ₁ → G _T

3. CDH (Computational Diffie-Hellman) problems (multiplication) on G ₀ , G ₁ , and G _T are difficult to calculate.
λ is called a safety variable, and it is expected that some amount of computational complexity of attack on the system will be in exponential order (or quasi-exponential etc.) with respect to λ. G ₀ , G ₁ , and G _T are called groups, and L is called discrete logarithm. Since G ₀ , G ₁ , G _T is called a group, the addition (as the code of the ring) on G ₀ , G ₁ , G _T is also called multiplication, and A, B _∈ G _{x, ∀x ∈ {0, 1, T}} is described as A × B, A / B, AB, etc. Polynomial-time non-degenerate bi-homomorphic ^ is called exponentiation, etc. ^ (g, a) is described as g ^{a for} g ∈ G _x , a ∈ L. Powers and additions on G ₀ , G ₁ , G _T are called group operations. Polynomial-time non-degenerate bi-homogeneous e is called pairing. Also, a pair of codes (L, G ₀ , G ₁ , G _T ) may be called pairing. When we say pairing due to historical circumstances and customs, whether it refers to e, (L, G ₀ , G ₁ , G _T ), P, or not distinguishing between them It needs to be judged according to the context. G ₀ and G ₁ are called a source group and G _T is called a target group. Unless otherwise specified in the present specification, when simply referred to as a group and a group element, etc., they mean an input group and an input group element, respectively. Galbraith et al. Roughly classified the pairing used in the encryption method into the following three types (see Reference 1).
(Reference 1) Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart, "Pairings for cryptographers", Discrete Applied Mathematics, 156 (16): 3113-3121, 2008.

Type1: Polynomial time isomorphism exists bidirectionally between G ₀ and G ₁ .
There is a one-way isomorphism of Type2: G ₁ → G ₀ .
There is no polynomial time isomorphism between Type3: G ₀ and G ₁ in both directions.

Generally, Type1 is called symmetric pairing, and Type2 and Type3 are called asymmetric pairing. In symmetric pairing, G ₀ and G ₁ can always move bidirectionally in polynomial time, so there is no need to distinguish between them, and they are simply described as G. Since Type2 can be implemented using Type3, Type2 rarely appears except when considering special functions and safety proof. In the present specification, Type 3 is particularly assumed as the asymmetric pairing.

At this time, G ₀ and G ₁ are clearly distinguished. Regarding implementation problems such as operation speed and group element size, the existence of asymmetric pairing that is much more efficient than symmetric pairing is known (see Reference 2).
(Reference 2) Paulo SLM Barreto and Michael Naehrig, "Pairing-friendly elliptic curves of prime order", In Bart Preneel and Stafford E. Tavares, editors, Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers, volume 3897 of Lecture Notes in Computer Science, pages 319-331. Springer, 2005.

<Dependency graph (see Non-Patent Document 1 and Reference Document 3)>
(Reference 3) Takeya Tango, Masayuki Abe, and Tatsuaki Okamoto, "Implementation of Automated Translation for Schemes on Symmetric Bilinear Groups", In Proc. Of SCIS 2014 The 31st Symposium on Cryptography and Information Security kagoshima, Japan, Jan. 21- 24, 2014. IEICE, 2014.

  For a method, the dependency graph is the flow of information (data) of group element variables used in the method's construction, syntax, reduction, assumption, etc. is a directed graph that abstracts flow). Each vertex represents a group element variable used in the program, and each edge represents its dependency (the end point depends on the start point). Fig. 1 is an example of an algorithm that inputs group elements A, B, D and calculates C, E using group operations and outputs the pairing e (C, E). Fig. 2 shows its dependency graph. is there.

  In the dependency graph, only the relationships between group elements via group operations are described, and the structure of the program such as "if-then-else" instruction and variables or targets other than group elements such as a ∈ Z / pZ All operations on the group are discarded.

Since pairing is a function that inputs two input group elements (group element 91 and group element 92 in the example of FIG. 2) and outputs one target group element, it becomes a pair having no output side in the dependency graph. Expressed as two vertices. Group element variables in the method corresponding to input to pairing shall be implicitly declared and defined. For example, five group element variables A, B, C, D, and E are declared and defined in the algorithm of Fig. 1, but two group element variables corresponding to the inputs to pairing are neither declared nor defined. It has not been. This implicit group element variable is expressed as p ₁ [0] and p ₁ [1] in FIG. If there are multiple pairings, the i-th pairing has implicit group element variables p _i [0] and p _i [1]. Further, it is assumed that, in general, an implicit group element variable is appropriately declared and defined if necessary in the context of a dependency relationship from an expression composed of group operations and group element comparisons in a program.

Abe et al. Proposed a framework for converting an encryption method based on symmetric pairing into an encryption method based on asymmetric pairing while maintaining security (see Non-Patent Document 1 and Reference Document 3). In the framework of Abe et al., We derive two subgraphs that follow certain constraints from one dependency graph that summarizes the composition, syntax, consequences, assumptions, etc. of the method defined on symmetric pairing. Derivation of these subgraphs is called division. Each subgraph abstracts the method after conversion, and becomes a dependency graph for group elements of G ₀ and G ₁ , respectively. Then, the composition, syntax, consequences, assumptions, etc. of the method defined on the asymmetric pairing are reconstructed from the two subgraphs and the original method. An example of conversion by division of the algorithm of FIG. 1 is shown in FIG. 3, and its dependency graph is shown in FIG. In order to consider conversion by division, some terms and notations are generally defined according to Non-Patent Documents 1 and 2 and Reference Documents 3 and 4.
(Reference 4) Fumitaka Hoshino, Masayuki Abe, and Miyako Ohkubo, "Optimal Conversion from Symmetric Pairing-based Scheme to Asymmetric One", In Proc. Of SCIS 2016 2016 Symposium on Cryptography and Information Security Kumamoto, Japan, Jan. 19- 22, 2016. IEICE, 2016.

Definition 1 (G, G ₀ , G ₁ ) Although the pairing input group in Type 1 was defined as G in the above <Pairing>, G is redefined as a dependency graph or its vertex set. Although the input group pairing in the general settings in the above <Pairing> was defined as G ₀ and G _1, the following G ₀ and G ₁ subgraphs or redefine its vertex set of dependency graph G To do.

Hereinafter, it is assumed that two subgraphs G _b , b∈ {0,1} are generated from the dependency graph G by division.
Definition 2 (ancestor) A vertex y ∈ G (but not including x) that can reach x with respect to vertex x ∈ G is called an ancestor of x. At this time, vertex x is said to have vertex y as an ancestor.
Definition 3 (Descendants) A vertex y ∈ G (not including x) that can be reached from x with respect to vertex x ∈ G is called a descendant of x. At this time, vertex x is said to have vertex y as a descendant.

  In general, the data flow of a single algorithm constructed by a chain of valid variable definitions forms a directed acyclic graph, and thus has no cycle. However, the dependency graph may have a cycle when a plurality of algorithms such as the scheme configuration, the syntax, the consequences, the assumptions, etc. are integrated. When a dependency graph has a cycle, it is possible that a vertex y is an ancestor and a descendant of a vertex x. Since the vertices that make up a cycle are both ancestors and descendants of each other, the cycle itself may be equated to a single vertex in the context of a dependency relationship. Considering this property, the concept of leaf in a directed graph is expanded a little and is defined as follows.

Definition 4 (Leaf) A vertex with no output or a vertex that represents a closed cycle with no output (reachable to other leaves) is called a leaf. By definition, the inputs to pairing are always leaves.

  In the present specification, the set of integers {0,1} is equated with the set of logical values, and 0 is regarded as false and 1 as true. All logical expressions can be deduced according to classical logic (Boolean algebra). Generally, the following notation is used according to the convention.

とも記述する。 Definition 5 (∧, ∨, xor, ⇒, ⇔, ¬, ^- ) For two logical expressions x and y, their logical product, logical sum, exclusive disjunction, implication, and equivalence are x∧y and x∨, respectively. Write y, x xor y, x ⇒ y, x ⇔ y. Described as x ^- the negation ¬x or to the logical expression x. Also, the exclusive OR

Also described.

である。割り当て変数(x∈G_b)に関して、写像{(x∈G_b)}→{0,1}を割り当て変数(x∈G_b)への割り当てあるいは代入と呼ぶ。全ての割り当て変数の集合をV_Gとする。即ち
V_G={(x∈G_b)|x∈G,b∈{0,1}}
である。写像V_G→{0,1}を依存関係グラフGへの割り当て、あるいは単に割り当てと呼ぶ。割り当てを決定すれば分割を決定する事が出来る。 To facilitate the traffic between logical assertions and algebraic relations, the following definitions are made.
Definition 6 (Assignment variable (x ∈ G _b )) (x ∈ G _b ) is a logical variable according to its truth value, that is, a variable on {0, 1}. (x ∈ G _b ) is called an assigned variable. That is,

Is. For the assignment variable (x ∈ G _b ), the map {(x ∈ G _b )} → {0,1} is called assignment or substitution to the assignment variable (x ∈ G _b ). Let V _G be the set of all assigned variables. I.e.
V _G = {(x ∈ _{G b} ) | x ∈ _{G, b} ∈ {0,1}}
Is. The mapping V _G → {0,1} is called an assignment to the dependency graph G, or simply an assignment. If you decide the assignment, you can decide the division.

When there are n vertices in the dependency graph G, there are 2n assigned variables. Therefore, there are 2 ²ⁿ assignments to the dependency graph G, that is, the mapping V _G → {0,1}. Some of these assignments are not valid in converting the scheme. It will be discussed later what kind of allocation is effective.

Definition 7 (overlapping vertices)
x ∈ G ₀ ∧ x ∈ G ₁
If x is satisfied, then x is called a duplicated node.

Definition 8 (non-duplicatable vertices) The vertices that have no possibility of becoming duplicate vertices for some reason are called non-duplicatable nodes. The non-overlapping vertices may be set by the designer of the method in order to represent the output of the operation in which the output of the hash function becomes a group element in the algorithm or to save the data size. Further, for the reasons described later, all the leaves are non-overlapping vertices in the conversion handled in this specification.

<Abe's framework (see Non-Patent Document 1 and Reference Document 3)>
Since symmetric pairing has a simple algebraic structure, many cryptosystems are designed on the assumption of symmetric pairing. However, from the viewpoint of efficiency such as time complexity and area complexity, it is now considered desirable to use asymmetric pairing. Therefore, Abe et al. Have proposed the following framework for automatically converting an encryption method based on symmetric pairing into an encryption method based on asymmetric pairing while maintaining security (see Non-Patent Document 1 and Reference Document 3).

Step1: Each algorithm such as configuration, syntax, consequents, assumptions, etc. of the encryption method on Type1 pairing is input.
Step2: Construct dependency graphs (directed graphs) of group element variables in each algorithm, and integrate them into one.
Step3: Divide the dependency graph into two subgraphs under the constraints described below. If there is no division, this framework cannot convert it.
Step4: Based on the division, each algorithm such as the configuration of the encryption method on Type3 pairing, the syntax, the reduction, and the assumption is output.

Abe et al. Proved the following theorem regarding the above division.
Theorem 1 (see Non-Patent Document 1) When the above division satisfies the following four constraints, the derived method realizes the function and security of the original method on Type3.
Constraint 1 The union of the two subgraphs divided is consistent with the original graph.
Constraint 2 If the subgraph contains vertex x, then the subgraph contains all paths to vertex x.
Constraint 3 Two vertices included in one pairing are included in different subgraphs.
Constraint 4 If one subgraph contains a non-overlapping vertex, the other subgraph does not contain that vertex.

  The split satisfying these four constraint conditions is called a valid split, and the assignment is called a valid assignment. In Non-Patent Document 1 and Reference Document 3, the division of Step 3 is determined by evaluating some evaluation function such as a time calculation amount and a region calculation amount related to the method by a brute force search.

は成立しない。式(1)の選言は
(x∈G₀)+(x∈G₁)≧1 (2)
と同義である。xが重複不可頂点である場合は
(x∈G₀)+(x∈G₁)=1 (3)
が成立する。

としても良い。記述を簡素化するため、本発明では重複不可頂点xに関しては、論理変数(x∈G₁)を改めて論理変数xと略記する事があるとする。即ち重複不可頂点x∈Gおよびb∈{0,1}に関して

である。 <Effective partitioning and assumption of optimality>
The effective division will be considered below.
Constraint 1 The union of the two subgraphs divided is consistent with the original graph.
Constraint 1 is clear
G = G ₀ ∪G ₁
Means This means that if the vertex x is x ∈ G
x ∈ G ₀ ∨ x ∈ G ₁ (1)
Which means that

Does not hold. The disjunction of formula (1) is
(x ∈ G ₀ ) + (x ∈ G ₁ ) ≧ 1 (2)
Is synonymous with. if x is a non-overlapping vertex
(x ∈ G ₀ ) + (x ∈ G ₁ ) = 1 (3)
Is established.

Also good. In order to simplify the description, in the present invention, regarding the non-overlapping vertex x, the logical variable (xεG ₁ ) may be abbreviated as the logical variable x again. That is, for non-overlapping vertices x ∈ G and b ∈ {0,1}

Is.

In this specification, the following assumptions are made regarding the evaluation function.
Assumption 1 (Assumption of Optimality) Suppose there are two effective partitions for G, and the only difference is "whether a certain vertex x is an overlapping vertex". At this time, the evaluation value of the division in which x is the overlapping vertex is always equal to or worse than the evaluation value of the other division.

  This assumption is based on the observation that the smaller the number of overlapping vertices, the smaller the amount of area calculation and time calculation required for the method, and the more efficient the method. This method cannot be applied when the evaluation function has different values from those evaluation criteria (for example, having as many overlapping vertices as possible). In this method, this assumption is called the optimality assumption. With this assumption, partitions containing redundant overlapping vertices can be excluded from consideration. Below, we consider the effective partitioning under this assumption.

Constraint 2 If the subgraph contains vertex x, then the subgraph contains all paths to vertex x. Let y be the ancestor of x.
Constraint 2 is clear
(x ∈ G _b ) ⇒ (y ∈ G _b )
Means As shown in FIG. 5, the implication is synonymous with the inequality sign according to the truth table. Therefore, it is expressed by the following equation.
(x ∈ G _b ) ≦ (y ∈ G _b ) (5)

最適性の仮定により等号のみを考えれば良い。

Let y be the vertex and D _{y be} the whole descendant of y. The assignment (y ∈ G _b ) ∈ {0,1} must satisfy the following.
( _y ∈ G _b ) ≧ (x ∈ G _b ), ∀x _∈ D _y (6)
I.e.

Only the equal sign needs to be considered according to the assumption of optimality.

Now, assuming that y has no descendants, there is no x such that x ∈ D _y, so the value of (y ∈ G _b ) can be determined without considering equation (7). At this time, it can be excluded that y is an overlapping vertex due to the assumption of optimality. That is, if y is a leaf, y can be unique.

Next, assume that all leaf assignments have been determined. We would like to repeatedly go upstream from the leaf and determine the assignment of the vertex y on the upstream side by using equation (7). Due to optimality assumptions, all vertex assignments may be determined by all leaf assignments reachable from that vertex. That is, the value (y ∈ G _b ) ∈ {0,1} depends only on the leaf value. Let L _y be the entire leaf contained in D _y . From equation (7)

を意味する。x,yが{0,1}変数なので
x+y=1 (9)
として良い。 Constraint 3 Two vertices included in one pairing are included in different subgraphs.
Let x, y be the vertices that form the input pair for pairing. Since x and y are leaves, they can be unique. Therefore, x, y can be {0,1} variables. Obviously constraint 3

Means x, y are {0,1} variables
x + y = 1 (9)
As good as.

Constraint 4 If one subgraph contains a non-overlapping vertex, the other subgraph does not contain that vertex.

式(5)より

が成立する。(x∈G_b)≠(y∈G_b)を仮定すると、直ちに(x∈G_b)=0および(y∈G_b)=1が成立する。なぜなら
0≦(x∈G_b)<(y∈G_b)≦1
であるから、式(10)により

が成立する。従って式(5)即ち

が成立しない。従って(x∈G_b)≠(y∈G_b)なる仮定は成立しない。よって(x∈G_b)=(y∈G_b)即ちx=yである。即ち、もしx,yが一つの路上の二つの重複不可頂点であるなら
x-y=0 (11)
が成立する。

としても良い。 Let x, y be non-overlapping vertices and x be a descendant of y. From equation (4)

From equation (5)

Is established. Assuming (xεG _b ) ≠ (yεG _b ), (xεG _b ) = 0 and (yεG _b ) = 1 are immediately established. Because
0 ≦ (x ∈ G _b ) <(y ∈ G _b ) ≦ 1
Therefore, according to equation (10)

Is established. Therefore, equation (5)

Does not hold. Therefore, the assumption that (x ∈ G _b ) ≠ (y ∈ G _b ) does not hold. Therefore, (x ∈ G _b ) = (y ∈ G _b ), that is, x = y. That is, if x, y are two non-overlapping vertices on a road
xy = 0 (11)
Is established.

Also good.

<Abe et al. Algorithm (Non-Patent Document 2 and Reference 4)>
In Non-Patent Document 1 and Reference Document 3, the division of Step3 is determined by evaluating some function such as the amount of time calculation and the amount of area calculation related to the method by brute force search. If the sum of the number of pairings and the number of leaves that are not input to the pairing is n, the above brute force search requires 2 ⁿ operations, and when n is large, the calculation amount becomes too large and executed. It will be difficult. Abe et al. Separated this problem into a solution problem of effective division and an optimization problem, and proposed a polynomial time solution algorithm and the following optimization algorithm (Non-patent document 2 and reference document 4).

Step1: Write down all constraints (3), (8), (9), and (11).
Step2: Convert (8) into linear constraints by the following well-known methods.
Step3: Write down the linear objective function using the assigned variables.
Step4: Input all linear constraints and linear objective functions into any 0-1 integer programming algorithm to obtain exact or approximate solutions.
Step 5: Configure the partition according to the value of the assigned variable.

と記述できる。ところで{0,1}上の変数y₀,y₁,zについて、

である。即ち{0,1}変数の任意の連言と否定は線型制約の元で変数に置き換え可能で、従ってどのような命題変数の論理式もこの置き換えを繰り返す事によって{0,1}変数の線型制約付き線型式に変換出来る事が良く知られている。特にy₁,…,y_k,z∈{0,1}の時

Conversion to linear constraint: (d ∈ G ₁ ) is abbreviated as d

Can be described as By the way, for variables y ₀ , y ₁ , z on {0,1},

Is. That is, arbitrary conjunctions and negations of {0,1} variables can be replaced by variables under linear constraints, and thus any logical expression of a propositional variable can be linearly changed by repeating this replacement. It is well known that it can be converted into a constrained linear form. Especially when y ₁ ,…, y _k , z ∈ {0,1}

と同値である。 Is. Therefore constraint (12) is a linear constraint

Is the same value as.

<Points of the first embodiment>
In the pairing type conversion apparatus according to the present embodiment, by optimizing the constraints required in the pairing type conversion and limiting the problem input to the 0-1 integer programming problem to a special form, the optimization execution time is reduced. Speed up.

Integer programming problem defined by integer matrix A, integer vector b, f, and vector variable x
max {f ・ x | Ax ≧ b, 0 ≦ x ≦ 1, x ∈ Z ⁿ }
Linear relaxation
max {f ・ x | Ax ≧ b, 0 ≦ x ≦ 1, x ∈ R ⁿ }
think of. The matrix A is called totally unimodular when any subdeterminant is 0, 1, or -1. It is known that the solution of an integer programming problem matches the solution of its linear relaxation when the matrix A is perfect simple. Generally, a linear programming problem belongs to a problem class called P, and therefore if the matrix A is a perfect simple pattern, it can be solved in polynomial time by reconsidering an integer programming problem as a linear programming problem.

  The linear constraint A required for the pairing conversion is not necessarily a perfect simple pattern, so this method cannot be applied directly, but as many small determinants of the matrix A as possible are 0,1, -1. If A can be constructed so that, it can be expected that integer programming can be speeded up.

By the way, it is known that the matrix A that satisfies the following four conditions is a perfect imitation.
Condition 1: All components of A are 0, 1, or -1.
Condition 2: Every row of A has at most two non-zero components.
Condition 3: If two non-zero components of a row of A have the same sign, then one column belongs to some subscript set B and the other column belongs to a subscript set C that does not belong to B. .
Condition 4: If two non-zero components of a row of A have different signs, then both columns belong to either B or C.

  In general, if A that satisfies the conditions 1 and 2 does not satisfy the conditions 3 and 4, the matrix A ', which is a row that causes a contradiction in the conditions 3 and 4 is appropriately removed from A, should be a perfect simple pattern. You can

  Although A generated by the method of Abe et al. Satisfies the condition 1, it does not satisfy the condition 2 in most cases because of the first and third formulas of the formula (14). Therefore, in general, it is necessary to remove all rows that do not satisfy the condition 2 except the rows that cause the contradictions in the condition 3 and the condition 4 because the submatrix A ′ is a perfect simple pattern.

  In the algorithm of Abe et al. (Non-patent document 2, Reference document 4), the formula (8) obtained from the formula (7) was forcedly replaced with the linear constraint by using the formula (13). In the present embodiment, this replacement is terminated and the following is directly obtained from the equation (6) using the assumption of optimality.

Let y be the vertex and L _{y be the} whole of the descendants of _y that are leaves. The assignment (y ∈ G _b ) ∈ {0,1} must satisfy the following.
( _y ∈ G _b ) ≧ (x ∈ G _b ), ∀x _∈ L _y (15)
The first and third equations of constraint (14), which were the problem in Abe's method, do not appear.

In this embodiment, the following steps are executed.
Step1: Write down all constraints (3), (15), (9), and (11) to set linear constraints.
Step2: Write down the linear objective function using the assigned variables.
Step3: Input all linear constraints and linear objective functions into any 0-1 integer programming algorithm to obtain exact or approximate solutions.
Step 4: Configure the partition according to the value of the assigned variable.

A pairing type conversion device that realizes the above will be described.
<First embodiment>
FIG. 6 is a functional block diagram of the pairing type conversion device 100 according to the first embodiment, and FIG. 7 shows its processing flow.

  The pairing type conversion device 100 is configured by a computer including a CPU, a RAM, and a ROM recording a program for executing the following processing, and is functionally configured as shown below.

  The pairing type conversion device 100 includes a linear constraint setting unit 110, an objective function setting unit 120, an integer planning unit 130, and a division configuration unit 140.

  The pairing type conversion device 100 converts an encryption method based on symmetric pairing into an encryption method based on asymmetric pairing. For example, the pairing type conversion device 100 receives an algorithm including a configuration, syntax, reduction and assumption of a cryptosystem based on symmetric pairing as input information and includes a configuration, syntax, reduction and assumption of a cryptosystem based on asymmetric pairing. Converted to an algorithm and output as output information.

<Linear constraint setting unit 110>
The linear constraint setting unit 110 sets four linear constraints for predetermined division (S110). The four linear constraints are
(1) When x is a non-overlapping vertex, (x ∈ G ₀ ) + (x ∈ G ₁ ) = 1
(2) For any x included in L _y , ( _y ∈ G _b ) ≧ (x ∈ G _b ).
(3) If x and y are vertices that are the input pair to pairing, x + y = 1
(4) If x and y are two non-overlapping vertices on one road, xy = 0
And correspond respectively to the four constraints for partitioning below.
Constraint 1 The union of the two subgraphs divided is consistent with the original graph.
Constraint 2 If the subgraph contains vertex x, then the subgraph contains all paths to vertex x.
Constraint 3 Two vertices included in one pairing are included in different subgraphs.
Constraint 4 If one subgraph contains a non-overlapping vertex, the other subgraph does not contain that vertex.

<Objective function setting unit 120>
The objective function setting unit 120 sets the objective function as a linear function for all assigned variables (S120). If the objective function is a non-linear (logical) function of assigned variables, the objective function is converted into a linear objective function with a linear constraint and set based on the following equation.

<Integer planner 130>
The integer planning unit 130 inputs the linear constraint and the linear function or the linear objective function into the 0-1 integer programming algorithm, and obtains an exact solution or an approximate solution of the optimal partition of the dependency graph (S130).

<Division configuration unit 140>
The division configuration unit 140 divides one dependency graph that summarizes the configuration, syntax, consequences, assumptions, etc. of the method defined on the symmetric pairing into two subgraphs according to the value of the assigned variable of the exact solution or the approximate solution. (S140), the two subgraphs and the original method are reconstructed from the method configuration, syntax, consequences, assumptions, etc. of the method defined on the asymmetric pairing, and the algorithm is output.

<Effect>
With the above configuration, the optimization execution time can be expected to be faster than before. Since Expression (15) is a two-variable inequality with all ± 1 coefficients, A that satisfies Condition 1 and Condition 2 can be constructed. Therefore, the integer programming method in the integer planning unit 130 can be expected to be speeded up.

For example, the pairing type conversion device of the present embodiment can convert an ID-based encryption based on symmetric pairing (see Reference 5) into an ID-based encryption based on asymmetric pairing.
(Reference 5) Tetsutaro Kobayashi, Tsuyoshi Yamamoto, Kotaro Suzuki, Shinichi Hirata, "Application of ID-based encryption and keyword search", NTT Technical Journal, 2010.2, pp.17-20

Here, the converted ID-based encryption can be industrially used as follows. For example, consider a case where a certain user A encrypts and transmits a plaintext m to another user B (see FIG. 8). The user terminal 10A of the user A calculates the encryption key PK _B from the public information of the key issuing center 20 and the ID of the user B, and encrypts the plaintext m using the calculated encryption key PK _B (at this time, , Perform pairing calculation, for example, c = enc (PK _B , m)), and transmit the ciphertext c to the user terminal 10B of the user B. The user terminal 10B requests the key issuing center 20 for the private key (decryption key) for the user B. On the basis of the request, the key issuing center 20 uses the master secret key SK from the encryption key (public key) PK _{B of} the user _B and the ID to generate the secret key SK _B for the user B and sends it to the user terminal 10B. To do. The user terminal 10B receives the secret key for the user B SK _B and decrypts the ciphertext c (at this time, a pairing operation is performed, for example, m ′ = dec (SK _B , c)). In this way, the user A can encrypt and transmit the plaintext m to the user B safely.

In addition, for example, the pairing type conversion apparatus of the present embodiment converts a digital signature based on symmetric pairing (see Reference 6), an attribute-based encryption, and a function encryption into a digital signature based on asymmetric pairing, an attribute-based encryption, It can be converted into a function cipher. Naturally, the converted electronic signature, attribute-based encryption, and function encryption can also be industrially used.
(Reference 6) Dan Boneh, Ben Lynn, and Hovav Shacham, "Short signatures from the Weil pairing", 2004.

<Other modifications>
The present invention is not limited to the above embodiments and modifications. For example, the various processes described above may be executed not only in time series according to the description, but also in parallel or individually according to the processing capability of the device that executes the process or the need. Other changes can be made as appropriate without departing from the spirit of the present invention.

<Program and recording medium>
Further, various processing functions in each device described in the above-described embodiment and modification may be realized by a computer. In that case, the processing content of the function that each device should have is described by the program. By executing this program on a computer, various processing functions of the above-described devices are realized on the computer.

  The program describing the processing contents can be recorded in a computer-readable recording medium. The computer-readable recording medium may be any recording medium such as a magnetic recording device, an optical disc, a magneto-optical recording medium, or a semiconductor memory.

  The distribution of this program is performed by selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM in which the program is recorded. Further, the program may be stored in a storage device of a server computer and transferred from the server computer to another computer via a network to distribute the program.

  A computer that executes such a program first stores, for example, the program recorded on a portable recording medium or the program transferred from the server computer in its own storage unit. Then, when executing the process, this computer reads the program stored in its own storage unit and executes the process according to the read program. Further, as another embodiment of this program, the computer may directly read the program from the portable recording medium and execute processing according to the program. Further, each time the program is transferred from the server computer to this computer, the processing according to the received program may be executed successively. Further, the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by executing the execution instruction and acquiring the result without transferring the program from the server computer to the computer. May be Note that the program includes information that is used for processing by an electronic computer and that conforms to the program (such as data that is not a direct command to the computer but has the property of defining the processing of the computer).

  Further, although each device is configured by executing a predetermined program on a computer, at least a part of the processing contents may be realized by hardware.

Claims (3)

A pairing type conversion device for converting an encryption method based on symmetric pairing into an encryption method based on asymmetric pairing,
Input information is an algorithm including the configuration, syntax, return, and assumption of the cryptosystem based on the symmetric pairing, and output information is an algorithm including the configuration, syntax, return, and the assumption of the cryptosystem based on the asymmetric pairing,
G ₀ and G ₁ are subgraphs after division, x and y are vertices of the graph before division, _b ∈ {0,1}, (x ∈ G _b ) and (y ∈ G _b ) are descriptions in () Is 1 if false is true and 0 is false if false, and L _y is the set of descendants of y that are leaves, and
A linear constraint setting unit that sets four linear constraints for predetermined division,
An objective function setting unit that sets the objective function as a linear function for all assigned variables, and if the objective function is a non-linear function of assigned variables, converts the objective function into a linear objective function with linear constraints and sets it.
An integer programming unit for obtaining an exact solution or an approximate solution by inputting the linear constraint and the linear function or the linear objective function with the linear constraint into a 0-1 integer programming algorithm,
According to the value of the assigned variable of the exact solution or the approximate solution, one dependency graph expressing an algorithm including the configuration, syntax, reduction, and assumptions of the cryptosystem based on the symmetric pairing is divided into two subgraphs, and two A partitioning component that reconstructs the configuration, syntax, consequent, and assumptions of the scheme defined on the asymmetric pairing from the subgraph and the original cryptosystem ,
Equipped with
The linear constraint is
(1) When x is a non-overlapping vertex, (x ∈ G ₀ ) + (x ∈ G ₁ ) = 1
(2) For any x included in L _y , ( _y ∈ G _b ) ≧ (x ∈ G _b ).
(3) If x and y are vertices that are the input pair to pairing, x + y = 1
(4) If x and y are two non-overlapping vertices on one road, xy = 0
Is,
Pairing type conversion device. A Lupe bearings type conversion method converts the encryption scheme based encryption scheme based on symmetric pairing asymmetrically pairing,
Input information is an algorithm including the configuration, syntax, return, and assumption of the cryptosystem based on the symmetric pairing, and output information is an algorithm including the configuration, syntax, return, and the assumption of the cryptosystem based on the asymmetric pairing,
G ₀ and G ₁ are subgraphs after division, x and y are vertices of the graph before division, _b ∈ {0,1}, (x ∈ G _b ) and (y ∈ G _b ) are descriptions in () Is 1 if false is true and 0 is false if false, and L _y is the set of descendants of y that are leaves, and
The linear constraint setting unit sets a linear constraint setting step for setting four linear constraints for predetermined division,
The objective function setting unit sets the objective function as a linear function for all the assigned variables, and if the objective function is a non-linear function of the assigned variables, an objective function setting step of converting the objective function into a linear objective function with a linear constraint and setting the objective function. ,
An integer programming step, an integer programming step in which the linear constraint and the linear function or the linear objective function with the linear constraint are input to a 0-1 integer programming algorithm to obtain an exact solution or an approximate solution,
Partitioning component, according to the value of the assigned variable of the exact solution or approximate solution, the configuration of the cryptosystem based on the symmetric pairing, syntax, return, one dependency graph expressing an algorithm including assumptions into two subgraphs. A partitioning configuration step of partitioning and reconstructing the configuration, syntax, consequent, and assumptions of the scheme defined on the asymmetric pairing from the two subgraphs and the original cryptosystem ;
Equipped with
The linear constraint is
(1) When x is a non-overlapping vertex, (x ∈ G ₀ ) + (x ∈ G ₁ ) = 1
(2) For any x included in L _y , ( _y ∈ G _b ) ≧ (x ∈ G _b ).
(3) If x and y are vertices that are the input pair to pairing, x + y = 1
(4) If x and y are two non-overlapping vertices on one road, xy = 0
Is,
Pairing type conversion method.   A program for causing a computer to function as the pairing type conversion device according to claim 1.

Images