JP5907906B2 - Certification system, certification device, verification device, certification method - Google Patents

Description

  The present invention relates to a proof system that proves to a verification device that a proof device has values of variables that hold all proof equations included in at least one proof equation set of two proof equation sets. , A verification device, a verification device, and a verification method.

  An expression to be proved composed of a pairing product of elements of group G is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set. Then, as a technique to prove non-interactively without revealing the value that satisfies the value of any pairing product equation, Groth-Sahai non-dialogue proof (hereinafter " (Referred to as “GS certification”) (Non-Patent Document 1). In addition, as a method for proving using a GS proof that a proof device has values of variables that hold all proof expressions included in at least one proof expression set of two proof expression sets, The methods of Patent Documents 2 and 3 are known.

e is a pairing between elements of group G, W ₀ , W ₁ , W, U, V, X are variables of elements of group G, g is an element of group G and is a constant other than 1, and A is a group G It is a constant of the element of. The method of Non-Patent Document 2 is
e (g, gW ₀ W ₁ ) = 1
Is adopted as a switcher type, and is proved by adding a formula including pairing. In the method of Non-Patent Document 3, e (A, U) e (V, X) = 1 and e (A, X) = e (g, g)
Limited to the shape of
e (W, W / g) = 1
Is adopted as a switcher type, and is proved by adding a formula including pairing.

  A specific example of a proof expression or a proof expression set is a signature as described in Non-Patent Document 4. The signature of Non-Patent Document 4 is

という２つのペアリングの積で構成された式からなる。また、これらの式の中のそれぞれの値は、公開鍵から計算できる定数または検証装置には秘匿された秘密鍵から計算できる変数である。

It consists of an expression composed of the product of two pairings. Each value in these equations is a constant that can be calculated from the public key or a variable that can be calculated from the secret key that is concealed by the verification device.

Jens Groth and Amit Sahai, “Ecient non-interactive proof systems for bilinear groups”, In EUROCRYPT 2008, pages 415-432, 2008. Jens Groth, “Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures”, Asiacrypt 2006, Springer-Verlag, 2006. Jan Camenisch, Nishanth Chandran and Victor Shoup, “A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks”, Eurocrypt 2009, Springer-Verlag, 2009. Masayuki Abe, Kristiyan Haralambiev and Miyako Ohkubo, “Signing on Elements in Bilinear Groups for Modular Protocol Design”, IACR e-print 2010/133 [searched January 30, 2013], Internet <URL: http: // eprint. iacr.org/2010/133>.

  However, the method of Non-Patent Document 2 has a problem in that the number of expressions including variables to be added and pairing is large, and the efficiency of proof is poor. In addition, the method of Non-Patent Document 3 requires that the proof expression can be decomposed into a specific format, and there is a problem that the usage is limited.

  SUMMARY OF THE INVENTION An object of the present invention is to provide a technique that allows a proof expression expressed by a general pairing product to be proved and can be proved efficiently.

In this specification, an expression to be proved composed of a product of pairing of elements of group G is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set. . The proof system of the present invention proves to the verification device that the proof device has information on variables that make up all of the proof equations included in at least one of the two proof equation sets. To do. In addition, a value that is a value in the expression and is held by both the proving apparatus and the verification apparatus is called a constant, and a value that is in the expression and is hidden from the verification apparatus is called a variable. W is a variable of an element of group G, g is an element of group G and a constant other than 1, and i and j are numbers indicating correspondence. The proof device includes a proof object acquisition unit, an evidence acquisition unit, a conversion unit, a switcher generation unit, a conversion variable expression generation unit, a GS proof execution unit, and a proof output unit. The verification device includes a verification target acquisition unit, a proof input unit, a GS certification confirmation unit, and a target confirmation unit. The proof object acquisition unit acquires proof object information that is information on all constants included in all proof expressions included in the two proof expression sets. The evidence acquisition unit acquires evidence that is information of variables that make up all the proof expressions included in any one proof expression set. For each proof expression set, the conversion unit generates a conversion expression that converts all constant-constant pairings into constant-variable pairings for all proof expressions included in each proof-expression set. Generate a corresponding set of transformation expressions. The switcher generation unit generates an equation of pairing product that holds only when W is 1 or g as a switcher equation. Converting the variable expression generating unit, for one of the conversion equation set for each transformed variables Y _i from the constant B _i in the conversion unit, when the W = g holds only in Y _{i =} B _i, when the W = 1 Y _A pairing product equation that holds only when _i = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is defined as a first conversion variable expression set, and the other conversion expression set is converted from the constant B _{j by the} conversion unit. For each transformed variable Y _j , a pairing product equation that holds only when Y _j = B _j when W = 1 and holds only when Y _i = 1 when W = g is generated as a conversion variable expression, This set of conversion variable expressions is defined as a second conversion variable expression set. The GS certification execution unit
(A) When the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the first conversion variable expression set, W = g is assigned to the switcher expression, and the conversion expression corresponding to the first conversion variable expression set A value obtained from evidence and Y _i = B _i are assigned to variables of all conversion expressions included in the set and all conversion variable expressions included in the first conversion variable expression set, and the second conversion variable expression set is assigned to the second conversion variable expression set. Assign a value that results in a pairing result of 1 to all variables of all conversion expressions included in the corresponding conversion expression set and to all conversion variable expression variables included in the second conversion variable expression set;
(B) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the second conversion variable expression set, W = 1 is assigned to the switcher expression, and the conversion expression corresponding to the second conversion variable expression set A value obtained from evidence and Y _j = B _j are assigned to variables of all conversion expressions included in the set and variables of all conversion variable expressions included in the second conversion variable expression set, and the first conversion variable expression set is assigned to the first conversion variable expression set. Assigning a value that results in a pairing result of 1 to all variables of all conversion expressions included in the corresponding conversion expression set and all variables of the conversion variable expressions included in the first conversion variable expression set;
(C) GS proof is performed for each of the switcher formulas, all transformation formulas, and all transformation variable formulas in which values are assigned to the variables in the processing of (a) or (b). The proof output unit outputs information on all results of the switcher formula, the two conversion formula sets, the first conversion variable formula set, the second conversion variable formula set, and the GS proof. The verification object acquisition unit acquires proof object information that is information on all constants included in all proof expressions included in the two proof expression sets. The proof input unit acquires information of all results of the switcher type, the two conversion formula sets, the first conversion variable formula set, the second conversion variable formula set, and the GS proof output from the verification device. The GS proof confirmation unit confirms the results of the GS proof for the switcher type, all the conversion expressions included in the two conversion expression sets, and all the conversion variable expressions included in the first conversion variable expression set and the second conversion variable expression set. To do. The target confirmation unit is configured to switch the switcher formula, all the conversion formulas included in the two conversion formula sets, and all the conversion variable formulas included in the first conversion variable formula set and the second conversion variable formula set corresponding to the certification target information. Make sure.

  In the proof system of the present invention, there is no limitation on the form of the proof expression expressed by the product of pairing. Further, according to the proof system of the present invention, conversion processing is performed only for the pairing of constants in the proof expression, and one conversion variable expression (an expression including pairing) is performed for each conversion from the constant to the variable. ). Therefore, the number of formulas including pairing that must be added can be reduced as compared with the method of Non-Patent Document 2 on the assumption that conversion processing is performed on all pairings in the proof formula.

The figure which shows the structural example of the certification | authentication system of this invention. The figure which shows the example of the processing flow of a certification | authentication apparatus. The figure which shows the example of the processing flow of a verification apparatus.

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

In the following, an expression to be proved composed of a product of pairing of elements of group G is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set. The proof system of the present invention proves to the verification device that the proof device has information on variables that make up all of the proof equations included in at least one of the two proof equation sets. To do. Further, in the specification, “constant” is a value in a mathematical formula and indicates a value (known value) possessed by both the proving device and the verification device, and “variable” is a value in the mathematical formula. The value concealed from the verification device is shown. Furthermore, the group of the group G, G _T the prime order q, e pairing that maps between elements of the group G to an element of the group G _T, W variables of the elements of the group G, g is an element of the group G Therefore, constants other than 1 and i and j are numbers indicating correspondence. Note that when g ₁ and g ₂ are elements of group G and constants other than 1 and m and n are integers of 0 to q−1, pairing e is e (g ₁ , g ₂ ). ≠ 1, e (g ₁ ^m , g ₂ ⁿ ) = e (g ₁ , g ₂ ) This is a mapping having a property of ^mn .

A _a , B _f , and C _f are constants that are elements of the group G, U _a , V _b , and X _c are variables that are elements of the group G, and d _bc is a constant that is an integer of 0 to q−1. , A, b, c, f are numbers for indicating correspondence,

または、この式の項を移項することで表現できる式である。つまり、ペアリングの積で表現されたすべての式は、移項によって整理すれば式（１）の形に変形できる。そこで、以下での一般化した説明では、式（１）を用いて説明する。

Or, it is an expression that can be expressed by shifting the term of this expression. That is, all the expressions expressed by the product of pairing can be transformed into the form of expression (1) if they are arranged by transposition. Therefore, in the generalized description below, the description will be made using Equation (1).

  An expression expressed by such a product of pairing is used in the signature shown in Non-Patent Document 4, for example. One signature is composed of one or more expressions (two expressions in the case of Non-Patent Document 4) expressed by a pairing product, and the signature is verified by confirming that all the expressions are satisfied. Is done. That is, one expression in the signature corresponds to a proof expression in this specification, and the signature corresponds to a proof expression set. Then, the above-described “proving apparatus proves that the proving apparatus has the values of variables that hold all the proving expressions included in at least one of the two proving expression sets. Is applied to the signature, it means “proving to the verification device that the certification device has at least one valid signature of the two signatures”. However, the present invention can be applied without being limited to a signature, and expressions such as proof expressions and proof expression sets are used as general expressions.

<Configuration and processing of certification system>
FIG. 1 shows a configuration example of a proof system of the present invention. FIG. 2 shows an example of the processing flow of the certification device, and FIG. 3 shows an example of the processing flow of the verification device. The proof system includes at least a proof device 100 and a verification device 200. In FIG. 1, the certification device 100 and the verification device 200 are connected via a network 900. However, information exchange between the certification device 100 and the verification device 200 does not have to be limited to the network 900. Delivery may be performed.

  The certification device 100 includes a certification target acquisition unit 110, an evidence acquisition unit 120, a conversion unit 130, a switcher generation unit 140, a conversion variable expression generation unit 150, a GS certification execution unit 160, a certification output unit 170, and a recording unit 190. The verification device 200 includes a verification target acquisition unit 210, a proof input unit 220, a GS certification confirmation unit 230, a target confirmation unit 240, and a recording unit 290.

  The certification target acquisition unit 110 acquires certification target information, which is information on all constants included in all certification formulas included in the two certification formula sets, and records the certification target information in the recording unit 190 (S110). The form of the proof expression may be determined in advance or may be acquired during the process of step S110. The “constant information” may be a constant value itself or a value necessary for calculation by a predetermined method. For example, in step S110, information such as a public key is acquired. In this specification, “acquisition” is used not only to obtain from the outside but also to include generation by the certification device 100. The term “set” means a group representing a group, and the proof expression set means a group of one or more proof expressions. One of the proof expression sets is called a first proof expression set, and the other is called a second proof expression set.

  The evidence acquisition unit 120 acquires evidence that is variable information that holds all the proof expressions included in any one proof expression set, and records the evidence in the recording unit 190 (S120). The “variable information” may be a variable value itself or a value necessary for calculation by a predetermined method. For example, in step S120, information such as a secret key is acquired. In addition, when the proving apparatus 100 is an apparatus that generates a signature, it also includes that the proving apparatus 100 generates evidence.

For each proof expression set, the conversion unit 130 generates a conversion expression obtained by converting all of the constant-constant pairings into constant-variable pairings for all included proof expressions. Is generated and recorded in the recording unit 190 (S130). In the case of Expression (1), it means that B _f or C _f is converted to a variable Y _f . Further, even when the expression is transformed by the shift, it means that the constant corresponding to B _f or the constant corresponding to C _f in the expression after the shift is converted to the variable Y _f . For example,

のように変換する。つまり、変換式では、定数と定数のペアリングが存在しない。以下の説明のために、第１証明式集合の証明式において、変数に変換した定数をＢ_ｉとし、変換後の変数をＹ_ｉとする。また、第２証明式集合の証明式において、変数に変換した定数をＢ_ｊとし、変換後の変数をＹ_ｊとする。つまり、変換部１３０は、証明式のＢ_ｆもしくはＣ_ｆ、または移項後の表現でのＢ_ｆに対応する定数もしくはＣ_ｆに対応する定数を、定数Ｂ_ｉまたは定数Ｂ_ｊとして、変数に変換する。なお、第１証明式集合に対応した変換式集合を第１変換式集合、第２証明式集合に対応した変換式集合を第２変換式集合と呼ぶことにする。また、ｉとｊは対応関係を示す番号であって、第１変換式集合の中で定数から変数に変換された数だけ番号ｉの数は存在し、第２変換式集合の中で定数から変数に変換された数だけ番号ｊの数は存在する。さらに、「集合を生成する」とは、１つ以上の式を何らかの方法でまとまりとして扱えるようにすることを意味しており、同じ集合に属する式を同じテーブルに記録することや、関連付けるための番号を付与することなどを含んでいるが、これらに限定するものではない。

Convert as follows. In other words, there is no constant-constant pairing in the conversion formula. For the following explanation, in the proof expression of the first proof expression set, a constant converted to a variable is B _i and a converted variable is Y _i . In the proof expression of the second proof expression set, a constant converted to a variable is B _j, and a variable after conversion is Y _j . That is, the conversion unit 130 converts B _f or C _{f in the} proof expression or a constant corresponding to B _f in the expression after the transfer or a constant corresponding to C _f into a variable as a constant B _i or a constant B _j. To do. A conversion formula set corresponding to the first proof formula set is referred to as a first conversion formula set, and a conversion formula set corresponding to the second proof formula set is referred to as a second conversion formula set. Also, i and j are numbers indicating correspondence relationships, and there are as many numbers as the number i converted from constants to variables in the first conversion formula set, and from the constants in the second conversion formula set. There are as many numbers j as the number converted into variables. Furthermore, “generate a set” means that one or more expressions can be handled as a group in some way, and the expressions belonging to the same set can be recorded in the same table or associated with each other. This includes, but is not limited to, assigning numbers.

The switcher generation unit 140 sets the switcher equation as an equation of a pairing product that holds only when W is 1 or g, and records it in the recording unit 190 (S140). For example,
e (W, W / g) = 1 (3)
Can be a switcher type,
e (g / W, W) = 1 (4)
May be a switcher type.

For each variable Y _i converted from the constant B _i by the conversion unit 130 for the first set of conversion expressions, the conversion variable expression generation unit 150 includes only Y _i = B _i when W = g, and W = 1. Sometimes a pairing product equation that holds only when Y _i = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is defined as a first conversion variable expression set. For example,
e (B _i , W) = e (Y _i , g) (5)
You just need to generate a conversion variable expression like
e (B _i , W) e (Y _i , g ⁻¹ ) = 1 (6)
A conversion variable expression may be generated as follows. In addition, the conversion variable expression generation unit 150 holds only Y _j = B _j when W = 1 for each variable Y _j converted from the constant B _j by the conversion unit 130 for the second conversion expression set, and W = When g, a pairing product equation that holds only when Y _j = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is set as a second conversion variable expression set (S150). For example,
e ( _Bj , g / W) = e ( _Yj , g) (7)
You can create a transformation variable expression like
e (B _j , g / W) e (Y _j , g ⁻¹ ) = 1 (8)
A conversion variable expression may be generated as follows.

The GS certification execution unit 160 performs the following processes (a) to (c) (S160).
(A) If the evidence acquired by the evidence acquisition unit 120 is evidence of a first proof expression set (a proof expression set corresponding to the first conversion variable expression set), W = g is assigned to the switcher expression and the first conversion Values obtained from evidence and Y _i = B _i are assigned to variables of all conversion expressions included in the expression set and variables of all conversion variable expressions included in the first conversion variable expression set. That is, a value obtained from evidence is assigned to a variable that is also a variable in the proof expression, and Y _i = B _i is assigned to a variable converted from a constant to a variable by the conversion unit 130. Then, a value for which the pairing result is 1 is assigned to all the variables of all the conversion expressions included in the second conversion expression set and all the variables of the conversion variable expressions included in the second conversion variable expression set (S161). .

(B) If the evidence acquired by the evidence acquisition unit 120 is evidence of the second proof expression set (proof expression set corresponding to the second conversion variable expression set), W = 1 is assigned to the switcher expression and the second conversion Values obtained from evidence and Y _j = B _j are assigned to variables of all conversion expressions included in the expression set and variables of all conversion variable expressions included in the second conversion variable expression set. That is, a value obtained from evidence is assigned to a variable that is also a variable in the proof expression, and Y _j = B _j is assigned to a variable converted from a constant to a variable by the conversion unit 130. A value with a pairing result of 1 is assigned to all variables of all conversion expressions included in the first conversion expression set and all conversion variable expressions included in the first conversion variable expression set (S162).

(C) GS proof (Groth-Sahai non-dialogue proof) is performed for each of the switcher expression, the conversion expression, and the conversion variable expression in which values are assigned to the variables in the process of (a) or (b) ( S163).
Note that “assign a value that results in a pairing result of 1 to a variable” means that the value of the variable is set to 1 in the case of pairing a constant and a variable, and at least one of the variables is paired in the case of a pairing of a variable and a variable. This means that the value of the variable is 1. In this way, the pairing result is 1.

For example, a case where equation (2) is a conversion equation, equation (3) is a switcher equation, and equations (5) and (7) are conversion variable equations is as follows. When the evidence acquired by the evidence acquisition unit 120 is evidence of the first proof expression set (in the case of the process (a)), the switcher expression is
e (g, g / g) = 1
And it holds. The conversion formula of the first conversion formula set is

のＵ_ａ，Ｖ_ｂ，Ｘ_ｃに証拠から得られる値を代入した式となり、成り立つ。第１変換変数式集合の変換変数式は、
ｅ（Ｂ_ｉ，ｇ）＝ｅ（Ｙ_ｉ，ｇ）
となるので成り立つ。また、第２変換式集合の変換式は、

This is a formula obtained by substituting values obtained from evidence into U _a , V _b , and X _c of The transformation variable expression of the first transformation variable expression set is
e (B _i , g) = e (Y _i , g)
Since it becomes, it is formed. Also, the conversion formula of the second conversion formula set is

となる。この式では、すべてのペアリングで一方の要素が“１”なので、すべてのペアリングの結果が１となる。よって、右辺も左辺も１となり、成り立つ。第２変換変数式集合の変換変数式は、
ｅ（Ｂ_ｊ，ｇ／ｇ）＝ｅ（１，ｇ）
となり、やはり右辺も左辺も１となるので成り立つ。

It becomes. In this equation, since one element is “1” in all pairings, the result of all pairings is 1. Therefore, the right side and the left side are 1 and hold. The transformation variable expression of the second transformation variable expression set is
e (B _j , g / g) = e (1, g)
This is also true because both the right side and the left side are 1.

When the evidence acquired by the evidence acquisition unit 120 is evidence of the second proof expression set (in the case of the process (b)), the switcher expression is
e (1,1 / g) = 1
And it holds. The conversion formula of the first conversion formula set is

となる。この式では、すべてのペアリングで一方の要素が“１”なので、すべてのペアリングの結果が１となる。よって、右辺も左辺も１となり、成り立つ。第１変換変数式集合の変換変数式は、
ｅ（Ｂ_ｉ，１）＝ｅ（１，ｇ）
となり、やはり右辺も左辺も１となるので成り立つ。また、第２変換式集合の変換式は、

It becomes. In this equation, since one element is “1” in all pairings, the result of all pairings is 1. Therefore, the right side and the left side are 1 and hold. The transformation variable expression of the first transformation variable expression set is
e (B _i , 1) = e (1, g)
This is also true because both the right side and the left side are 1. Also, the conversion formula of the second conversion formula set is

のＵ_ａ，Ｖ_ｂ，Ｘ_ｃに証拠から得られる値を代入した式となり、成り立つ。第２変換変数式集合の変換変数式は、
ｅ（Ｂ_ｊ，ｇ／１）＝ｅ（Ｙ_ｊ，ｇ）
となり、成り立つ。

This is a formula obtained by substituting values obtained from evidence into U _a , V _b , and X _c of The transformation variable expression of the second transformation variable expression set is
e (B _j , g / 1) = e (Y _j , g)
And it holds.

  That is, regardless of which proof expression set the evidence acquired by the evidence acquisition unit 120 is, the switcher expression to which variables are assigned, all conversion expressions, and all conversion variable expressions hold. Since the GS proof is performed for the switcher formula, all conversion formulas, and all conversion variable formulas in the process (c), it can be proved that all formulas are established.

  The proof output unit 170 outputs information on all results of the switcher formula, the two conversion formula sets, the first conversion variable formula set, the second conversion variable formula set, and the GS proof (S170). Specifically, it may be transmitted to the verification device 200 via the network 900, or may be recorded on a portable recording medium.

  Next, processing of the verification apparatus 200 will be described. The verification object acquisition unit 210 acquires proof object information that is information on all constants included in all the proof expressions included in the two proof expression sets, and records the proof object information in the recording unit 290 (S210). This process is the same as the process performed by the certification target acquisition unit 110 of the certification device 100.

  The proof input unit 220 acquires information on all results of the switcher type, the two conversion formula sets, the first conversion variable formula set, the second conversion variable formula set, and the GS proof output from the verification apparatus 100 (S220). The acquisition method may be via the network 900 or via a recording medium.

  The GS proof confirmation unit 230 displays the GS proof results for the switcher type, all the conversion formulas included in the two conversion formula sets, and all the conversion variable formulas included in the first conversion variable formula set and the second conversion variable formula set. Confirm (S230). This confirmation confirms that all the expressions hold.

  The object confirmation unit 240 corresponds to the proof object information for the switcher expression, all the conversion expressions included in the two conversion expression sets, and all the conversion variable expressions included in the first conversion variable expression set and the second conversion variable expression set. (S240). By confirming the conversion variable expression set, among the variables of the conversion expression, it is possible to distinguish the variable variable and the variable converted from the constant to the variable by the conversion unit 130 even in the proof expression. By confirming the conversion expression set, it can be confirmed that the conversion expression set and the conversion variable expression set correspond to the proof expression set.

  Since the proof system of the present invention performs such processing, the verification device 200 does not know which proof expression set the proof device 100 holds, while the proof device 100 has at least one of them. We can prove that we have evidence for a proof formula set. If such a method is used, the security of the signature system can be enhanced, for example. Moreover, in the proof system of this invention, there is no restriction | limiting of the form of the proof formula expressed by the product of pairing. Furthermore, according to the proof system of the present invention, the conversion process is performed only for the constant-constant pairing in the proof expression, and one conversion variable expression (an expression including pairing) is performed for each conversion from the constant to the variable. ). Therefore, the number of formulas including pairing that must be added can be reduced as compared with the method of Non-Patent Document 2 on the assumption that conversion processing is performed on all pairings in the proof formula.

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

  Further, when the above-described configuration is realized by a computer, processing contents of functions that each device should have are described by a program. The processing functions are realized on the computer by executing the program 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.

  The present invention can be used for security enhancement of a signature system and a system to which a signature is applied.

DESCRIPTION OF SYMBOLS 100 Proof device 110 Proof object acquisition part 120 Evidence acquisition part 130 Conversion part 140 Switcher generation part 150 Conversion variable formula generation part 160 GS proof execution part 170 Proof output part 190,290 Recording part 200 Verification apparatus 210 Verification object acquisition part 220 Proof input Unit 230 GS certification confirmation unit 240 target confirmation unit 900 network

Claims (6)

An expression to be proved composed of a pairing product between elements of a group is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set.
A proof system that proves to a verification device that a proof device has information on variables that hold all proof equations included in at least one proof equation set of two proof equation sets,
A value that is a value in an expression and is held by both the proving device and the verification device is called a constant, a value in the equation that is concealed from the verification device is called a variable, and W is a group Variable of element, g is a group element and a constant other than 1, i and j are numbers indicating correspondence,
The proving device is
A proof object acquisition unit for acquiring proof object information which is information of all constants included in all proof expressions included in the two proof expression sets;
An evidence acquisition unit that acquires evidence that is information on variables that make up all the proof expressions included in any one proof expression set;
For each proof expression set, by generating a conversion expression that converts all constant-constant pairings into constant-variable pairings for all included proof expressions, conversion expressions corresponding to each proof expression set A transform unit for generating a set;
A switcher generating unit that generates an equation of a pairing product that holds only when W is 1 or g as a switcher equation;
For one conversion equation set, for each variable Y _i converted from the constant B _{i by the} conversion unit, only Y _i = B _i holds when W = g, and only Y _i = 1 holds when W = 1. Generate a pairing product equation as a conversion variable expression, and a set of the conversion variable expressions as a first conversion variable expression set;
For the other set of conversion formulas, for each variable Y _j converted from the constant B _{j by the} conversion unit, only Y _j = B _j is satisfied when W = 1, and only Y _j = 1 is satisfied when W = g. A pairing product equation is generated as a conversion variable expression and a set of the conversion variable expressions is a second conversion variable expression set;
(A) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the first conversion variable expression set, W = g is assigned to the switcher expression, and the first conversion variable expression set Assigning values obtained from the evidence and Y _i = B _i to variables of all the conversion expressions included in the conversion expression set corresponding to, and all the variables of the conversion variable expressions included in the first conversion variable expression set, The pairing result is 1 for all variables of all the conversion expressions included in the conversion expression set corresponding to the second conversion variable expression set and for all the conversion variable expressions included in the second conversion variable expression set. Assigns the value
(B) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the second conversion variable expression set, W = 1 is assigned to the switcher expression, and the second conversion variable expression set Assigning the values obtained from the evidence and Y _j = B _j to all the variables of the conversion expressions included in the conversion expression set corresponding to, and all the variables of the conversion variable expressions included in the second conversion variable expression set, The pairing result is 1 for all variables of all conversion expressions included in the conversion expression set corresponding to the first conversion variable expression set and all variables of the conversion variable expressions included in the first conversion variable expression set. Assigns the value
(C) a switcher expression in which values are assigned to variables in the process of (a) or (b), all conversion expressions, and a GS proof execution unit that performs GS proof on all conversion variable expressions;
A proof output unit that outputs information on all results of the switcher formula, the two transformation formula sets, the first transformation variable formula set, the second transformation variable formula set, and the GS proof,
The verification device includes:
A verification object acquisition unit that acquires proof object information that is information on all constants included in all proof expressions included in the two proof expression sets;
A proof input unit that obtains information on all results of the switcher formula, the two transformation formula sets, the first transformation variable formula set, the second transformation variable formula set, and the GS proof output from the proof device; ,
Confirm the result of the GS proof for the switcher expression, all the conversion expressions included in the two conversion expression sets, and all the conversion variable expressions included in the first conversion variable expression set and the second conversion variable expression set. A GS certification confirmation unit,
The switcher expression, all the conversion expressions included in the two conversion expression sets, and all the conversion variable expressions included in the first conversion variable expression set and the second conversion variable expression set correspond to the proof object information. And a target confirmation unit for confirming that the certification system is provided. The certification system according to claim 1,
e is a pairing of elements of the group,
The switcher type is
e (W, W / g) = 1
And
The conversion variable expression of the first conversion variable expression set is:
e (B _i , W) = e (Y _i , g)
And
The conversion variable expression of the second conversion variable expression set is:
e ( _Bj , g / W) = e ( _Yj , g)
A proof system characterized by The proof system according to claim 1 or 2,
Group G, group _{G T} the prime order q, e pairing that maps between elements of the group G to an element of the group _{G T, A a, B f} , C f is an element of the group G constant, U _a , V _b , and X _c are variables that are elements of the group G, d _bc is a constant that is an integer of 0 to q−1, a, b, c, and f are numbers for indicating correspondence,
The proof formula is

Or an expression that can be expressed by transposing the terms of this expression,
The conversion unit converts B _f or C _f of the proof expression or a constant corresponding to B _f in the expression after the transfer or a constant corresponding to C _f into the variable as the constant B _i or the constant B _j. A proof system characterized by conversion. An expression to be proved composed of a pairing product between elements of a group is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set.
A proof device that proves to a verification device that it has information on variables that hold all proof expressions included in at least one proof expression set of two proof expression sets,
A value that is a value in an expression and is held by both the proving device and the verification device is called a constant, and a value that is in the equation and is hidden from the verification device is called a variable, and e is a group W is a group element variable, g is a group element and a constant other than 1, and i and j are numbers indicating correspondence,
A proof object acquisition unit for acquiring proof object information which is information of all constants included in all proof expressions included in the two proof expression sets;
An evidence acquisition unit that acquires evidence that is information on variables that make up all the proof expressions included in any one proof expression set;
For each proof expression set, by generating a conversion expression that converts all constant-constant pairings into constant-variable pairings for all included proof expressions, conversion expressions corresponding to each proof expression set A transform unit for generating a set;
A switcher generating unit that generates an equation of a pairing product that holds only when W is 1 or g as a switcher equation;
For one conversion equation set, for each variable Y _i converted from the constant B _{i by the} conversion unit, only Y _i = B _i holds when W = g, and only Y _i = 1 holds when W = 1. Generate a pairing product equation as a conversion variable expression, and a set of the conversion variable expressions as a first conversion variable expression set;
For the other set of conversion formulas, for each variable Y _j converted from the constant B _{j by the} conversion unit, only Y _j = B _j is satisfied when W = 1, and only Y _j = 1 is satisfied when W = g. A pairing product equation is generated as a conversion variable expression and a set of the conversion variable expressions is a second conversion variable expression set;
(A) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the first conversion variable expression set, W = g is assigned to the switcher expression, and the first conversion variable expression set Assigning values obtained from the evidence and Y _i = B _i to variables of all the conversion expressions included in the conversion expression set corresponding to, and all the variables of the conversion variable expressions included in the first conversion variable expression set, The pairing result is 1 for all variables of all the conversion expressions included in the conversion expression set corresponding to the second conversion variable expression set and for all the conversion variable expressions included in the second conversion variable expression set. Assigns the value
(B) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the second conversion variable expression set, W = 1 is assigned to the switcher expression, and the second conversion variable expression set Assigning the values obtained from the evidence and Y _j = B _j to all the variables of the conversion expressions included in the conversion expression set corresponding to, and all the variables of the conversion variable expressions included in the second conversion variable expression set, The pairing result is 1 for all variables of all conversion expressions included in the conversion expression set corresponding to the first conversion variable expression set and all variables of the conversion variable expressions included in the first conversion variable expression set. Assigns the value
(C) a switcher expression in which values are assigned to variables in the process of (a) or (b), all conversion expressions, and a GS proof execution unit that performs GS proof on all conversion variable expressions;
A proof device comprising: the switcher equation, the two transformation equation sets, the first transformation variable equation set, the second transformation variable equation set, and a proof output unit that outputs information on all results of the GS proof. An expression to be proved composed of a pairing product between elements of a group is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set.
A verification device that verifies that a proof device has information on variables that hold all proof equations included in at least one proof equation set of two proof equation sets,
A value that is a value in an expression and is held by both the proving device and the verification device is called a constant, and a value that is in the equation and is hidden from the verification device is called a variable, and e is a group W is a group element variable, g is a group element and a constant other than 1, and i and j are numbers indicating correspondence,
For each proof expression set, a set generated for each proof expression set by generating a conversion expression that converts all of the pairings of constants and constants into pairings of constants and variables for all included proof expressions. Is a set of transformation formulas,
The pairing product equation that holds only when W is 1 or g is the switcher type,
For one set of conversion formulas, a pair is generated for each variable Y _i converted from the constant B _i , and only holds when Y _i = B _i when W = g, and only when Y _i = 1 when W = 1. The ring product equation is a transformation variable expression, the set of transformation variable expressions is the first transformation variable expression set,
For the other set of conversion formulas, a pair is generated for each variable Y _j converted from the constant B _j. When W = 1, only Y _j = B _j , and when W = g, only Y _j = 1. The ring product equation is the transformation variable expression, the set of transformation variable expressions is the second transformation variable expression set,
A verification object acquisition unit that acquires proof object information that is information on all constants included in all proof expressions included in the two proof expression sets;
Included in the switcher formula, the two transformation formula sets, the first transformation variable formula set, the information of the second transformation variable formula set, and the switcher formula and the two transformation formula sets output by the proving device A proof input unit for obtaining information on all results of GS proof for all conversion variable expressions included in the first conversion variable expression set and the second conversion variable expression set;
A GS certification confirmation unit for confirming all results of the GS certification;
The switcher expression, all the conversion expressions included in the two conversion expression sets, and all the conversion variable expressions included in the first conversion variable expression set and the second conversion variable expression set correspond to the proof object information. An object confirmation unit to confirm that
A verification apparatus comprising: An expression to be proved composed of a pairing product between elements of a group is called a proof expression, and a set of proof expressions including one or more proof expressions is called a proof expression set.
A proof method for proving to a verification device that a proof device has information on variables that hold all proof equations included in at least one proof equation set of two proof equation sets,
A value that is a value in an expression and is held by both the proving device and the verification device is called a constant, and a value that is in the equation and is hidden from the verification device is called a variable, and e is a group W is a group element variable, g is a group element and a constant other than 1, and i and j are numbers indicating correspondence,
A proof object obtaining step in which the proof device obtains proof object information which is information on all constants included in all proof expressions included in the two proof expression sets;
An evidence acquisition step in which the proof device acquires evidence that is information of variables that make up all the proof expressions included in any one proof expression set;
For each proof expression set, the proof device generates a conversion expression in which all constant-constant pairings are converted into constant-variable pairings for all included proof expressions. A conversion step for generating a set of conversion expressions corresponding to
A switcher generating step for generating, as a switcher equation, a pairing product equation that holds only when W is 1 or g;
The certification device, for one of the conversion equation set for each transformed variables Y _i from the constant B _i by the conversion unit, W = g holds only in Y _{i =} B _i when the, when the W = 1 Y _i A pairing product equation that holds only when = 1 is generated as a conversion variable expression, and a set of the conversion variable expressions is defined as a first conversion variable expression set;
For the other set of conversion formulas, for each variable Y _j converted from the constant B _{j by the} conversion unit, only Y _j = B _j is satisfied when W = 1, and only Y _j = 1 is satisfied when W = g. A pairing product equation is generated as a conversion variable expression, and a set of conversion variable expressions is used as a second conversion variable expression set;
The proof device is
(A) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the first conversion variable expression set, W = g is assigned to the switcher expression, and the first conversion variable expression set Assigning values obtained from the evidence and Y _i = B _i to variables of all the conversion expressions included in the conversion expression set corresponding to, and all the variables of the conversion variable expressions included in the first conversion variable expression set, The pairing result is 1 for all variables of all the conversion expressions included in the conversion expression set corresponding to the second conversion variable expression set and for all the conversion variable expressions included in the second conversion variable expression set. Assigns the value
(B) If the evidence acquired by the evidence acquisition unit is evidence of a proof expression set corresponding to the second conversion variable expression set, W = 1 is assigned to the switcher expression, and the second conversion variable expression set Assigning the values obtained from the evidence and Y _j = B _j to all the variables of the conversion expressions included in the conversion expression set corresponding to, and all the variables of the conversion variable expressions included in the second conversion variable expression set, The pairing result is 1 for all variables of all conversion expressions included in the conversion expression set corresponding to the first conversion variable expression set and all variables of the conversion variable expressions included in the first conversion variable expression set. Assigns the value
(C) a GS proof execution step for performing GS proof for each of the switcher formula, all conversion formulas, and all conversion variable formulas in which values are assigned to variables in the process of (a) or (b);
A proof output step in which the proof device outputs information of all results of the switcher formula, the two transformation formula sets, the first transformation variable formula set, the second transformation variable formula set, and the GS proof; ,
A verification object acquisition step in which the verification device acquires proof object information which is information of all constants included in all proof expressions included in the two proof expression sets;
The verification device obtains information on all the results of the switcher formula, the two transformation formula sets, the first transformation variable formula set, the second transformation variable formula set, and the GS certification output from the proof device. A proof input step,
The verification apparatus includes the switcher formula, all the conversion formulas included in the two conversion formula sets, and the GS for all the conversion variable formulas included in the first conversion variable formula set and the second conversion variable formula set. A GS certification confirmation step for confirming the result of the certification;
The verification device includes the switcher formula, all the conversion formulas included in the two conversion formula sets, all the conversion variable formulas included in the first conversion variable formula set and the second conversion variable formula set, An object confirmation step for confirming that the certification object information is supported;
Proving method with.

Images