JP6791820B2 - Pairing equation batch verification device, pairing equation batch verification generation method, program - Google Patents

Description

The present invention relates to a signature / authentication / zero-knowledge proof or a design of a general cryptographic authentication technique, and relates to a pairing equation batch verification device, a pairing equation batch verification generation method, and a program.

<Pairing>
In the design of cryptographic authentication technology, pairing is a cryptographic primitive (primitive function for cryptography) that can be applied to various methods, and formally, it is a probabilistic polynomial that outputs a code having an algebraic structure as follows. It is defined as the time algorithm G (G expressed in italic form in mathematical formulas, and so on).

1) L is

The sign of the finite commutative ring L (italic).

G ₀ , G ₁ , G _T are respectively

The same L (italic)-sign of possible group M (italic). aux is an auxiliary output.

2) A stochastic polynomial time algorithm for the following λ is available.
− Sample on L, G ₀ , G ₁ , G _T − Ring operation on L − Sum: G _x × G _x → G _{x, ∀x ∈ {0,1, T}}
− Scalar times: L × G _x → G _{x, ∀x ∈ {0,1, T}}
− Non-degenerate bilinear homomorphism e: G ₀ × G ₁ → G _T

In general, when proving security in the design of cryptographic authentication technology, some cryptographic problems defined for cryptographic primitives are considered. λ is called a safety variable, and the gain defined for a stochastic polynomial time attacker A (italic) trying to solve a cryptographic problem is ignored for any A (italic). What is possible is the immediate definition that a cryptographic primitive is secure. Mathematically proving the security of cryptographic primitives is often difficult, and hypotheses that are usually expected to hold empirically are used. Such a hypothesis is called a cryptographic assumption. By convention, L is called the discrete logarithm, and G _{x, ∀x ∈ {0,1, T}} are called groups, respectively. In particular, G ₀ and G ₁ are called the input group (source group), and G _T is called the target group (target group). Auxiliary output aux is a suitable function of G (italic) input and random tape. The specific output (L, G ₀ , G ₁ , G _T , aux) of G (italics) is called a common reference character string or parameter in a broad sense, but this is sometimes called pairing. The sum of G _{x as} a module is called product or multiplication, and is described as g × h, g · h, gh, etc. for g, h _∈ G x. L (italic) of G _x- Scalar multiples as modules are called exponentiation and are described as g ^a for ^a ∈ L, g ∈ G _x . The product and power are collectively called group operations. Non-degenerate homomorphism e is also called pairing. The q q> 2 Θ ^(λ) consists taken enough from a large prime number, the Z / qZ as L, and G _0, a cyclic subgroup of order q of a rational point groups respectively suitable elliptic curve as G _1, G _T It is known that the above G (italic form) can be concretely constructed by taking a cyclic subgroup of the order q of the multiplicative group of an appropriate finite field. Cryptographic assumptions about pairing are defined by abstracting the properties that some of such configurations are expected to have, and such cryptographic assumptions imply at least the following:

3) The CDH problem on G ₀ , G ₁ , G _T with L as the discrete logarithm is difficult to calculate.
Therefore, if a polynomial time algorithm that violates condition 3) with a significant probability is found for a specific configuration of a certain G (italic type), it can be said that G (italic type) is not a safe pairing. If it is believed that the specific configuration of a G (italic) satisfies conditions 1) and 2) and the cryptographic assumption holds, then such a G (italic) is called a safe pairing candidate. Due to historical background and customs, safe pairing candidates are often referred to simply as pairing. Also, when we say pairing, it does not distinguish between e, (L, G ₀ , G ₁ , G _T , aux), G (italics), or in particular. It needs to be judged by the context. Galbraith et al. Roughly classified the pairings used in cryptographic protocols into the following three types (Non-Patent Document 1).
There is a polynomial time isomorphism in both directions between Type1: G ₀ and G ₁ .
Type2: G ₁ → G ₀ There is a one-way isomorphism.
Type3: There is no polynomial time isomorphism in both directions between G ₀ and G ₁ .

Generally, Type1 is called symmetric pairing, and Type2 and Type3 are called asymmetric pairing. In symmetric pairing, G ₀ and G ₁ can be exchanged in both directions at any time in polynomial time, so they are not particularly distinguished in the design of the cryptosystem, and are simply described as G.

<Batch verification>
Generalized cryptographic authentication methods such as signatures and zero-knowledge proofs using pairing are included in the algorithms that make up the method.

Generally this when including validation of the type expression of

Can be regarded as a verification of.

If it is determined, the above verification formula is

Can be described as. Therefore, in the following, we consider this type of verification formula. Now, the set of pairing input group variables that make up the method

When is in the validation algorithm

Consider the case where many verification expressions of the type (however, α _l ≠ 0, β _l ≠ 0) are included. That is, for the integer k ∈ {1, ..., k _max }

age

Suppose that the verification of the proposition is included in the verification algorithm. About the truth value of this proposition

However, the opposite is not always true. However, when cryptographically secure pairing is used, if R (italic type) is a sufficiently large subset of the discrete logarithm L, the opposite can be established with high probability. In general, rather than verifying the proposition E _k = 1 one by one for k ∈ {1, ..., k _max }

It is more efficient to verify all at once. This is called batch verification.

Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156 (16): 3113-3121, 2008. Joseph A. Akinyele, Matthew Green, Susan Hohenberger, and Matthew W. Pagano. Machine-Generated Algorithms, Proofs and Software for the Batch Verication of Digital Signature Schemes. In CCS'12 Proceedings of the 2012 ACM conference on Computer and communications security, Pages474-487. Der-San Chen, Robert G. Batson, and Yu Dang. Applied Integer Programming: Modeling and Solution. ISBN: 978-0-470-37306-4, pp.54-58, December 2009. Mikio Kubo, Akihisa Tamura, Tomomi Matsui [edit], "Handbook of Applied Mathematical Planning", Asakura Shoten Co., Ltd., May 2012, p.243-244,2002.

Generally, e (X, Y) ^r = e (X ^r , Y) = e (X, Y ^r ), and there is no single calculation method for e (X, Y) ^r . further

Or

Therefore, pairings in which one of the arguments is the same can be combined. Therefore, batch verification formula

There are many calculation methods depending on how the random numbers r _k used are arranged and how the pairings are put together, and the number generally increases exponentially with respect to the number of pairings. Then, depending on the calculation method, the number of pairings that can be combined and the type of the formula input to the pairing change, so the efficiency of the calculation changes greatly. Simply searching for the best or comparable calculation method from a large number of exponential calculation method candidates becomes virtually infeasible as the scale of batch verification increases.

For example, Non-Patent Document 2 discloses a method capable of efficiently calculating batch verification by exploratory application of various calculation methods based on experience, but a calculation method that is optimal or comparable to it. There is a problem that it cannot be obtained by a unified method.

Therefore, given a predetermined E _k type for k ∈ {1, ..., k _max }, the best or comparable calculation method from this exponentially large number of calculation method candidates. Finding out is an important issue.

Therefore, an object of the present invention is to provide a pairing equation batch verification device capable of realizing batch verification by an efficient calculation method.

The pairing equation batch verification device of the present invention has a configuration including an objective function generation unit, a linear objective function conversion unit, an integer programming algorithm execution unit, and a batch verification method configuration unit.

The objective function generator takes k as the index of the validation formula and l as the index of the pairing existing in each validation formula, obtains the set {E _k } of the validation formulas that is the product of the pairings, and obtains the kth validation. In the l-th pairing in an expression, the purpose of expressing the amount of calculation as the linear sum of the logical expressions of the variable b _kl , which represents either the powers in one input group element or the powers in the other input group element. Generate function B.

The linear objective function conversion unit converts the objective function B into a linear objective function with linear constraints.

The integer programming algorithm execution unit inputs all linear constraints and linear objective functions into any 0-1 integer programming algorithm to obtain at least one of an exact solution and an approximate solution.

The batch verification method component constructs the batch verification method according to the value of the variable b _kl determined by the exact solution or the approximate solution.

According to the pairing equation batch verification device of the present invention, batch verification by an efficient calculation method can be realized.

The block diagram which shows the structure of the pairing equation batch verification apparatus of embodiment. The flowchart which shows the operation of the pairing equation batch verification apparatus of embodiment.

Hereinafter, embodiments of the present invention will be described in detail. The components having the same function are given the same number, and duplicate description is omitted.

≪Preparation: {0,1} variable b _kl , objective function B≫
Now, for the pairing e (X ^α , Y ^β ) ^r , consider a variable b ∈ {0,1} for convenience, and if b = 0, collect all the powers in Y, and if b = 1, then the powers. Are all collected in X. Therefore, ε = αβ,

given that,

Can be expanded. Now, batch verification assuming the case of asymmetric pairing

Applying the above expansion to all pairings of

To get. G ₀ The function I of the subscript _i ∈ {1, ..., i _max } of the variable X _i

By exchanging the arithmetic order of the product of a finite number of pairings for the underlined part, and grouping the pairings with the same basis X _i ,

As good as. The function δ of proposition P

By exchanging the arithmetic order of the product of a finite number of powers for the underlined part,

As good as. About the underlined part above

If you define

Can be done. Similarly, the function J of the subscript _j ∈ {1, ..., j _max } of the G ₁ variable Y _j

Defined as

And if the above underlined part is deformed

Can be done. A rough estimate is that the computational cost of this batch validation is the sum of the cost of multiple pairings, which consists of the product of up to i _max + j _max, and the cost of multiple powers, which make up the arguments of each pairing. It is determined. At this time,

Or

Since it is known in advance that the value of each pairing is 1, the number n of valid pairings that actually compose multiple pairings is generally smaller than i _max + j _max . If L is the cost of Miller loop when calculating pairing and F is the cost of the final power when calculating pairing, the calculation cost required for multiple pairing is roughly.
F + n ・ L
Can be estimated. Also G ₁ multiple power

Let s _{1 and i be} the maximum number of bits of all exponents, m _{1 and i be} the total number of bits of all exponents, and S _{1 be} the cost of squared G _{1 and} M _{1 be} the cost of G ₁ multiplication. , A constant

Exists,
s _{1, i}・ S ₁ + c ₁・ m _{1, i}・ M ₁
Can be estimated. Similarly G ₀ multiple powers

Maximum bit number of all index computation cost s _{0, j} necessary, m _0, and the total bit number of all index _j, the cost of the S ₀ G ₀ squares, when the M ₀ to the cost of G ₀ multiplied , A constant

Exists
s _{0, j}・ S ₀ + c ₀・ m _{0, j}・ M ₀
Can be estimated.

If you define, the total cost B of batch verification is

Can be done. A similar evaluation can be made in the case of symmetric pairing (described later).

<< Preparation: Conversion to a linear objective function with linear constraints (S12 described later) >>
By the way, about the variables x, x ₁ , x ₂ , y on {0,1}

Is. That is, any conjunction and negation of the {0,1} variable can be replaced with a new {0,1} variable under some linear constraint, so any formula of a propositional variable can be replaced by repeating this replacement. It is well known that 0,1} variables can be converted into linearly constrained linear formulas (Non-Patent Document 3).

Therefore, if B can be estimated by the linear sum of the logical expressions of the {0,1} variable b _kl , then B can be converted to the linear constrained linear expression of the {0,1} variable using the above transformation. The allocation of b _kl that gives the optimal value of B or the approximate optimal value can be obtained by using an arbitrary integer linear programming algorithm. Algorithms for solving integer linear programming problems include, for example, rigorous solutions such as dynamic programming, simulated annealing, cut plane method, and branch cut, approximate solutions such as random rounding and random extraction, greedy solutions, and local search. Heuristic solutions such as tabu search, simulated annealing, and genetic algorithms are well known (Non-Patent Document 4).

<< Preparation: Generation of objective function B-In the case of asymmetric pairing (S11 described later) >>
The number of valid pairings n that actually configure multiple pairings with r _k as a random variable

Is. G ₁ multiple power

The maximum number of bits s _{1, i} of all indexes of

Can be estimated. However,

And. Since we know in advance from what set ε _kl and r _k are selected, we assume that the values of | ε _kl r _k | can be estimated and therefore aligned. For example, when L = Z / qZ, it is generally assumed that | ε _kl | is very small (for example, | ε _kl | ~ 1) or very large (for example, | ε _kl | ~ | q |). It is possible to assume that | r _k | is | r _k | ~ | q | / 2 or | r _k | ~ 1 etc. for a specific k. At this time, | ε _kl r _k | is estimated as shown in Table 1.

Similarly G ₀ multiple powers

The maximum number of bits s _{0, j} of all indexes of

Can be estimated. However,

And. G ₁ multiple power

The total number of bits m _{1, i} of all indexes of

Can be estimated. However,

And. Similarly G ₀ multiple powers

The total number of bits m _{0, j} of all indexes of

Can be estimated. However,

And. Therefore,

And the total cost of bulk verification

Considering, B could be described by the linear sum of the formulas of the {0,1} variable b _kl .

<< Preparation: Generation of objective function B-Symmetric pairing (S11 described later) >>
In symmetric pairing, G ₀ = G ₁ = G can be considered. Therefore, a set of pairing input group variables that make up the method

and

Is equated with i _max = j _max , and all i ∈ {1, ..., i _max } are redefined as X _i = Y _i . Also, disjoint union U (i) of I (i) and J (i)
U (i) = I (i) _└┘ J (i) = {(k, l, t) | (k, l) _∈ I (i) _∧ t = 1 ∨ (k, l) ∈ J (i) ∧ t = 0}
Defined as

Defined as

Is defined as.

Is. However,

And. At this time, the number of valid pairings n is

G multiple power

The maximum number of bits s _i of all indexes of

Can be estimated. However,

And. Also, G multiple power

The total number of bits of all indices of m _i is

Can be estimated. However,

And. Let S be the cost of G square and M be the cost of G multiplication.

Exists and G multiple power

Computation cost
s _i・ S + c ・ m _i・ M
Can be estimated. Therefore,

Then the total cost of batch verification
B = F + n ・ L + s ・ S + c ・ m ・ M
Considering, B could be described by the linear sum of the formulas of the {0,1} variable b _kl .

<Pairing equation batch verification device>
Hereinafter, the configuration and operation of the pairing equation batch verification device according to the embodiment will be described with reference to FIGS. 1 and 2. As shown in FIG. 1, the pairing equation batch verification device 1 of the present embodiment includes an objective function generation unit 11, an objective function storage unit 11a, a linear objective function conversion unit 12, and a linear objective function storage unit 12a. , An integer programming algorithm execution unit 13, an exact solution / approximate solution storage unit 13a, and a batch verification method configuration unit 14.

As shown in FIG. 2, the objective function generation unit 11 sets k as the index of the verification formula, l as the index of the pairing existing in each verification formula, and sets {E _k } of the verification formulas which are the products of the pairings. Obtain and in the l-th pairing in the k-th validation expression, the {0,1} variable b _kl represents either to collect exponentiation to one input group element or to collect exponentiation to the other input group element. As a linear sum of the logical expressions of, an objective function B representing the amount of calculation is generated (S11). The objective function generation unit 11 stores the generated objective function B in the objective function storage unit 11a.

The linear objective function conversion unit 12 converts the objective function B into a linear objective function with linear constraints (S12). The linear objective function conversion unit 12 stores the converted linear constrained linear objective function in the linear objective function storage unit 12a.

The integer programming algorithm execution unit 13 inputs all the linear constraints and linear objective functions into an arbitrary 0-1 integer programming algorithm, and acquires at least one of an exact solution and an approximate solution (S13). The integer programming algorithm execution unit 13 stores the acquired exact solution or approximate solution in the exact solution / approximate solution storage unit 13a.

The batch verification method configuration unit 14 configures the batch verification method according to the value of the variable b _kl determined by the exact solution or the approximate solution (S14). Specifically, a batch verification method according to the value of b _kl

(For asymmetric pairing), or

(In the case of symmetrical pairing) etc. The batch verification method configuration unit 14 outputs the configured batch verification method.

In the past, the idea of different ways of collecting powers between pairings was not very common. In the past, the same type of data was often handled, so for example, if it was decided to collect powers in X in one pairing, it was usual to collect powers in X in other pairings as well. .. For this reason, in the past, there was no idea of the {0,1} variable b _kl, which is a variable that describes how to collect exponentiation in each pairing. Also, since the idea of using an arbitrary 0-1 integer programming algorithm in the batch verification method was not common, the objective function B representing the amount of calculation was expressed as the linear sum of the logical expressions of the {0,1} variable b _kl . Above, there was no idea to convert this to a linear constrained linear objective function so that it could be handled by a 0-1 integer programming algorithm. Since the pairing equation batch verification device 1 of the present embodiment adopts the above-mentioned new idea, batch verification by an efficient calculation method can be realized.

<Supplement>
The device of the present invention is, for example, an input unit to which a keyboard or the like can be connected, an output unit to which a liquid crystal display or the like can be connected, and a communication device (for example, a communication cable) capable of communicating outside the hardware entity as a single hardware entity. Communication unit to which can be connected, CPU (Central Processing Unit, cache memory, registers, etc.), RAM and ROM as memory, external storage device as hard hardware, and input, output, and communication units of these , CPU, RAM, ROM, has a connecting bus so that data can be exchanged between external storage devices. Further, if necessary, a device (drive) or the like capable of reading and writing a recording medium such as a CD-ROM may be provided in the hardware entity. A general-purpose computer or the like is a physical entity equipped with such hardware resources.

The external storage device of the hardware entity stores the program required to realize the above-mentioned functions and the data required for processing this program (not limited to the external storage device, for example, reading a program). It may be stored in a ROM, which is a dedicated storage device). Further, the data obtained by the processing of these programs is appropriately stored in a RAM, an external storage device, or the like.

In the hardware entity, each program stored in the external storage device (or ROM, etc.) and the data necessary for processing each program are read into the memory as needed, and are appropriately interpreted, executed, and processed by the CPU. .. As a result, the CPU realizes a predetermined function (each configuration requirement represented by the above, ... Department, ... means, etc.).

The present invention is not limited to the above-described embodiment, and can be appropriately modified without departing from the spirit of the present invention. Further, the processes described in the above-described embodiment are not only executed in chronological order according to the order described, but may also be executed in parallel or individually depending on the processing capacity of the device that executes the processes or if necessary. ..

As described above, when the processing function in the hardware entity (device of the present invention) described in the above embodiment is realized by a computer, the processing content of the function that the hardware entity should have is described by a program. Then, by executing this program on the computer, the processing function in the hardware entity is realized on the computer.

The program describing the processing content can be recorded on a computer-readable recording medium. The computer-readable recording medium may be, for example, a magnetic recording device, an optical disk, a photomagnetic recording medium, a semiconductor memory, or the like. Specifically, for example, a hard disk device, a flexible disk, a magnetic tape, or the like as a magnetic recording device is used as an optical disk, and a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), or a CD-ROM (Compact Disc Read Only) is used as an optical disk. Memory), CD-R (Recordable) / RW (ReWritable), etc., MO (Magneto-Optical disc), etc. as a magneto-optical recording medium, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), etc. as a semiconductor memory Can be used.

Further, the distribution of this program is performed, for example, by selling, transferring, renting, or the like 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 the storage device of the server computer, and the program may be distributed by 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. Then, when the process is executed, the computer reads the program stored in its own recording medium and executes the process according to the read program. Further, as another execution form of this program, a computer may read the program directly from a portable recording medium and execute processing according to the program, and further, the program is transferred from the server computer to this computer. It is also possible to execute the process according to the received program one by one each time. Further, the above-mentioned processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and the result acquisition without transferring the program from the server computer to this computer. May be. The program in this embodiment includes information used for processing by a computer and equivalent to the program (data that is not a direct command to the computer but has a property of defining the processing of the computer, etc.).

Further, in this form, the hardware entity is configured by executing a predetermined program on the computer, but at least a part of these processing contents may be realized in terms of hardware.

In addition, each step described in the specification and claims corresponds to each step of the method of generating various information. The various types of information referred to here correspond to the programs, etc. (programs ... Other information used for processing by computers and equivalent to the programs) specified in Article 2, Paragraph 4 of the Patent Act. The information in is applicable to the information prescribed in Article 2, Paragraph 3, Item 1 of the Patent Act. Therefore, it goes without saying that the method of generating various types of information described in the description and claims corresponds to the method of producing the product prescribed in Article 2, Paragraph 3, Item 3 of the Patent Act. Absent.

Claims (5)

Let _{k be} the index of the validation expression, l be the index of the pairing existing in each validation expression, get the set {E _k } of the validation expression that is the product of the pairing, and get the lth pair in the kth validation expression. In the ring, the purpose of generating the objective function B, which represents the amount of computation, as the linear sum of the well-formed formulas of the variable b _kl , which represents either the powers on one input group element or the powers on the other input group element. Function generator and
A linear objective function converter that converts the objective function B into a linear objective function with linear constraints,
An integer programming algorithm execution unit that inputs all the linear constraints and the linear objective function into an arbitrary 0-1 integer programming algorithm and obtains at least one of an exact solution and an approximate solution.
A batch verification method component that configures a batch verification method according to the value of the variable b _kl determined by the exact solution or the approximate solution,
Pairing equation batch verification device including. The pairing equation batch verification device according to claim 1.
The objective function B is a pairing equation batch verification device that includes a term related to the calculation cost required for multiple pairing and a term related to the calculation cost required for multiple powers. It is a pairing equation batch verification generation method executed by the pairing equation batch verification device.
Let _{k be} the index of the validation formula, l be the index of the pairing existing in each validation formula, get the set {E _k } of the validation formulas that is the product of the pairings, and get the lth pair in the kth validation formula. In the ring, the step of generating the objective function B, which represents the amount of computation, as the linear sum of the formulas of the variable b _kl , which represents either the powers on one input group element or the powers on the other input group element. When,
The step of converting the objective function B into a linear objective function with linear constraints,
A step of inputting all the linear constraints and the linear objective function into an arbitrary 0-1 integer programming algorithm to obtain at least one of an exact solution and an approximate solution.
A step of constructing a batch verification method according to the value of the variable b _kl determined by the exact solution or the approximate solution, and
Pairing equation batch verification generation method including. The pairing equation batch verification generation method according to claim 3.
The objective function B is a pairing equation batch verification generation method including a term related to the calculation cost required for multiple pairing and a term related to the calculation cost required for multiple powers. A program that causes a computer to function as the pairing equation batch verification device according to claim 1 or 2.

Images