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

Description

  The present invention proves to the verification device that the proof device has values of variables that hold all the proof equations included in at least one proof equation set of two or more proof equation sets. The present invention relates to a proof system, a proof device, a verification device, and a proof 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. Further, the methods of Non-Patent Documents 2 and 3 are based on two proof expression sets, and the values of variables that make up all the proof expressions included in any one of the three or more proof expression sets are set. The GS certificate cannot be used to prove that the proving device has it.

  The present invention is not limited to two sets of proof formulas but can be applied to two or more sets of proof formulas (can be applied to two cases, but can also be applied to cases where there are more than two). The purpose is to provide a technique that can be proved efficiently by using a proof expression expressed by a ring product.

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 according to the present invention indicates to the verification device that the proof device has variable information that holds all the proof expressions included in at least one proof expression set of two or more proof expression sets. Prove that. 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. N is an integer greater than or equal to 2, n and m are integers greater than or equal to 1 and less than or equal to N, W _n is a variable of an element of group G corresponding to the nth proof expression set, g is an element of group G and is a constant other than 1 , I is a number indicating the 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 certification target acquisition unit acquires certification target information that is information on all constants included in all certification formulas included in all certification formula sets. The evidence acquisition unit acquires evidence that is variable information that makes up all the proof expressions included in the m-th proof expression set that is one of the proof expression sets. For all n = 1,..., N, the conversion unit converts all constant-constant pairings into constant-variable pairings for all proof expressions included in the n-th proof expression set. The n-th conversion equation set is generated by generating the conversion equation. Switcher generator, n = 1, ..., and equation paired product of W _n holds only when one or g for _N, W 1, ..., one of W _N is a g other all 1 In this case, the pairing product equation that holds is generated as a switcher equation. For all n = 1,..., N, the conversion variable expression generation unit W _n = g for each variable Y _i converted from the constant B _i by the conversion unit in the n-th conversion expression set. Is generated only as Y _i = B _i , and when W _n = 1, a pairing product equation that is satisfied only when Y _i = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is converted to the n-th conversion. A variable expression set. The GS proof execution unit assigns W _m = g to the switcher expression, W _n = 1 to W _{n where} n ≠ m, and all the variables of the conversion expressions included in the m-th conversion expression set and the m-th conversion variable. All values of transformation variables included in the formula set are assigned values obtained from evidence and Y _i = B _i to variables of the transformation formulas, and all variables and m of all transformation formulas included in all the transformation formula sets other than the m-th. Assign a value that results in a pairing result of 1 to all variables in all conversion variable expressions other than the number of conversion variable expressions. For all switcher expressions, all conversion expressions, and all conversion variable expressions Perform GS certification for each. The proof output unit outputs information of all switcher expressions, all conversion expression sets, all conversion variable expression sets, and all results of 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 all proof expression sets. The proof input unit acquires information on all the switcher expressions, all the conversion expression sets, all the conversion variable expression sets, and all the results of the GS proof output from the proof device. The GS proof confirmation unit confirms the GS proof results for all switcher expressions, all conversion expressions, and all conversion variable expressions. The object confirmation unit confirms that all switcher expressions, all conversion expressions, and all conversion variable expressions correspond to the proof object information.

  The proof system of the present invention can be applied to two or more proof expression sets, and there is no restriction 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 according to the present invention indicates to the verification device that the proof device has variable information that holds all the proof expressions included in at least one proof expression set of two or more proof expression sets. Prove that. 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 G, the G _T of prime order q group, e is the pairing of mapping between elements of the group G to an element of the group G _T, N is an integer of 2 or more, n and m are less 1 or more N An integer, W _n is a variable of an element of the group G corresponding to the nth proof expression set, g is an element of the group G and a constant other than 1, and i is a number indicating a correspondence relationship. Note that when g ₁ and g ₂ are elements of group G and constants other than 1 and α and β are integers of 0 to q−1, pairing e is e (g ₁ , g ₂ ). ≠ 1, e (g ₁ ^α , g ₂ ^β ) = e (g ₁ , g ₂ ) ^αβ is a mapping having the property of ^αβ .

または、この式の項を移項すること（両辺に同じ項を乗算すること、または両辺を同じ項で除算すること）で表現できる式である。つまり、ペアリングの積で表現されたすべての式は、移項によって整理すれば式（１）の形に変形できる。そこで、以下での一般化した説明では、式（１）を用いて説明する。 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,

Alternatively, it is an expression that can be expressed by shifting the terms of this expression (multiplying both sides by the same term, or dividing both sides by the same term). 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-mentioned “proving to the verification device that the proof device possesses the values of the variables that hold all the proof equations included in at least one proof equation set among the two or more proof equation sets. When applied to the signature, it means “proving to the verification device that the proving device has at least one valid signature of the two or more 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 all 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 .

  The evidence acquisition unit 120 acquires evidence, which is information on variables that make up all the proof expressions included in the m-th proof expression set that is one of the proof expression sets, and records it 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 all n = 1,..., N, the conversion unit 130 converts all constant-constant pairings into constant-variable pairings for all proof expressions included in the n-th proof expression set. By generating the converted conversion formula, an nth conversion formula set 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 . Further, "generates a set", it is meant that the handle as chunks of one or more expressions in some way, and recording the expressions belonging to the same set in the same table, for associating This includes, but is not limited to, assigning numbers.

をスイッチャー式とすればよいし、
ｅ（ｇ／Ｗ_１，Ｗ_１）＝１，…，ｅ（ｇ／Ｗ_Ｎ，Ｗ_Ｎ）＝１ （５）
のＮ個の等式と

をスイッチャー式にしてもよい。 Switcher generator 140, the switcher type, n = 1, ..., and equation pairing product that consists only when _{W n} is 1 or g for _N, W 1, ..., in any one of g of _{W N} An equality of pairing product that holds when all others are 1 is recorded in the recording unit 190 (S140). For example,
e (W ₁ , W ₁ / g) = 1,..., e (W _N , W _N / g) = 1 (3)
N equations

Can be a switcher type,
e (g / W ₁ , W ₁ ) = 1,..., e (g / W _N , W _N ) = 1 (5)
N equations

May be a switcher type.

The conversion variable expression generation unit 150 performs the following processing for all of n = 1,. For the n-th conversion expression set, each transformed variables _{Y i} from the constant _{B i} in the conversion unit _130, when the _W n = g holds only in _Y i = _{B i,} when the _W n = 1 _Y i = 1 The pairing product equation that holds only at is generated as a conversion variable expression, and this set of conversion variable expressions is set as the nth conversion variable expression set (S150). For example,
e (B _i , W _n ) = e (Y _i , g) (7)
You just need to generate a conversion variable expression like
e (B _i , W _n ) e (Y _i , g ⁻¹ ) = 1 (8)
A conversion variable expression may be generated as follows.

The GS certification execution unit 160 performs the following processing. W _m = g is assigned to the switcher expression, W _n = 1 is assigned to W _{n where} n ≠ m, and all variables included in the m th conversion expression set and all included in the m th conversion variable expression set The value obtained from the evidence and Y _i = B _i are assigned to the variables of the conversion variable formula of 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, pairing results are obtained for all variables of all conversion expressions included in all conversion expression sets other than the mth and all conversion variable expression variables included in all conversion variable expression sets other than the mth. Assign a value of 1. Then, GS proof (Groth-Sahai non-dialogue proof) is performed for all switcher expressions, all conversion expressions, and all conversion variable expressions assigned values to variables (S160). 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, equations (3) and (4) are switcher equations, and equation (7) is a conversion variable equation is as follows. Switcher type e (W _m , W _m / g) = 1
e (g, g / g) = 1
And it holds. The switcher equation e (W _n , W _n / g) = 1 when n ≠ m is
e (1,1 / g) = 1
And it holds. Also, the equation (4) is
e (g, g / g) = 1
Since it becomes, it is formed. The transformation formula of the mth transformation 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 mth transformation variable expression set is
e (B _i , g) = e (Y _i , g)
Since it becomes, it is formed. Also, the conversion formulas of all conversion formula sets other than the mth are:

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 expressions of all transformation variable expression sets other than the mth are
e (B _i , 1) = e (1, g)
This is also true because both the right side and the left side are 1.

  That is, even if m is any value from 1 to N, all switcher expressions, all conversion expressions, and all conversion variable expressions to which variables are assigned hold. And since GS proof is performed with respect to these equations, it can prove that all the expressions are formed.

  The proof output unit 170 outputs information of all switcher expressions, all conversion expression sets, all conversion variable expression sets, and all results of 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 target acquisition unit 210 acquires certification target information that is information on all constants included in all certification formulas included in all certification formula sets, and records the certification target 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 the switcher expressions, all the conversion expression sets, all the conversion variable expression sets, and all the results of 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 confirms the results of GS proof for all switcher expressions, all conversion expressions, and all conversion variable expressions (S230). This confirmation confirms that all the expressions hold.

  The object confirmation unit 240 confirms that all switcher expressions, all conversion expressions, and all conversion variable expressions correspond to the certification target information (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 proof. You can prove that you have evidence for the set of expressions. If such a method is used, the security of the signature system can be enhanced, for example. Further, the present invention is not limited to two proof expression sets, but can be applied to any number of two or more proof sets, thereby expanding the application range of the present invention. For example, a person who receives a signature from one person in a group can prove that he has received the signature from at least someone in the group without revealing who received it. Furthermore, in the proof system of the present invention, there is no restriction 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.

[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 among N 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 in the equation that is concealed from the verification device is called a variable, and N is 2 The above integers, n and m are integers of 1 to N, W _n is a group element variable corresponding to the nth proof expression set, g is a group element and a constant other than 1, and i is a correspondence relationship And a number indicating
The proving device is
A certification target acquisition unit that acquires certification target information that is information of all constants included in all certification formulas included in all certification formula sets;
An evidence acquisition unit that acquires evidence that is information of variables that make up all the proof expressions included in the m-th proof expression set that is one of the proof expression sets;
For all n = 1,..., N, for all proof expressions included in the nth proof expression set, conversion formulas that convert all constant-constant pairings into constant-variable pairings are: Generating a conversion unit that generates the n-th conversion formula set;
n = 1, ..., and equation paired product of W _n holds only when one or g for _N, W 1, ..., W pairing holds true when it other are all 1 any one of g _N A switcher generator for generating a product equation as a switcher equation;
For all of n = 1,..., N, for each variable Y _i converted from the constant B _{i by the} conversion unit in the n-th conversion formula set, Y _i = B when W _n = g. _A pairing product equation that holds only at _i and holds only when Y _i = 1 when W _n = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is used as the n-th conversion variable expression set. A variable expression generator,
W _m = g is assigned to the switcher expression, and W _n = 1 is assigned to W _{n where} n ≠ m, and the variables of all the conversion expressions included in the m-th conversion expression set and the m-th conversion variable expression set are included. Assign the values obtained from the above evidence and Y _i = B _i to the variables of all conversion variable expressions, and all the variables of all conversion expressions and all but the mth included in all the conversion expression sets other than the mth. Assign a value that results in a pairing result of 1 to all variables in the transformation variable expression set of, and obtain GS certification for all switcher expressions, all conversion expressions, and all conversion variable expressions. A GS certification execution unit to perform;
A proof output unit that outputs information about all the switcher expressions, all the conversion expression sets, all the conversion variable expression sets, and all the results of the GS proof, and
The verification device includes:
A verification target acquisition unit that acquires certification target information, which is information on all constants included in all certification formulas included in all certification formula sets;
A proof input unit that obtains information on all the switcher expressions output by the proof device, all the conversion expression sets, all the conversion variable expression sets, and all results of the GS proof;
A GS proof confirmation unit for confirming a result of the GS proof for all the switcher expressions, all the conversion expressions, and all the conversion variable expressions;
A verification system comprising: a target confirmation unit that confirms that all the switcher formulas, all the conversion formulas, and all the conversion variable formulas correspond to the certification target information. 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,..., e (W _N , W _N / g) = 1

And
The conversion variable expression of the nth conversion variable expression set is:
e (B _i , W _n ) = e (Y _i , 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. And a proof system. 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 among N 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 in the equation that is concealed from the verification device is called a variable, and N is 2 The above integers, n and m are integers of 1 to N, W _n is a group element variable corresponding to the nth proof expression set, g is a group element and a constant other than 1, and i is a correspondence relationship And a number indicating
A certification target acquisition unit that acquires certification target information that is information of all constants included in all certification formulas included in all certification formula sets;
An evidence acquisition unit that acquires evidence that is information of variables that make up all the proof expressions included in the m-th proof expression set that is one of the proof expression sets;
For all n = 1,..., N, for all proof expressions included in the nth proof expression set, conversion formulas that convert all constant-constant pairings into constant-variable pairings are: Generating a conversion unit that generates the n-th conversion formula set;
n = 1, ..., and equation paired product of W _n holds only when one or g for _N, W 1, ..., W pairing holds true when it other are all 1 any one of g _N A switcher generator for generating a product equation as a switcher equation;
For all of n = 1,..., N, for each variable Y _i converted from the constant B _{i by the} conversion unit in the n-th conversion formula set, Y _i = B when W _n = g. _A pairing product equation that holds only at _i and holds only when Y _i = 1 when W _n = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is used as the n-th conversion variable expression set. A variable expression generator,
W _m = g is assigned to the switcher expression, and W _n = 1 is assigned to W _{n where} n ≠ m, and the variables of all the conversion expressions included in the m-th conversion expression set and the m-th conversion variable expression set are included. Assign the values obtained from the above evidence and Y _i = B _i to the variables of all conversion variable expressions, and all the variables of all conversion expressions and all but the mth included in all the conversion expression sets other than the mth. Assign a value that results in a pairing result of 1 to all variables in the transformation variable expression set of, and obtain GS certification for all switcher expressions, all conversion expressions, and all conversion variable expressions. A GS certification execution unit to perform;
A proof device comprising: all the switcher expressions, all the conversion expression sets, all the conversion variable expression sets, 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 expressions included in at least one proof expression set among N 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 in the equation that is concealed from the verification device is called a variable, and N is 2 N is an integer greater than or equal to 1 and less than or equal to N, W _n is a variable of a group element corresponding to the nth proof expression set, g is a group element and a constant other than 1, and i indicates a correspondence relationship Number and
For all proof expressions included in the nth proof expression set, a conversion expression is generated by converting all constant-constant pairings into constant-variable pairings. Let the set be the n-th transformation set,
n = 1, ..., and equation paired product of W _n holds only when one or g for _N, W 1, ..., W pairing holds true when it other are all 1 any one of g _N The product equation is the switcher type,
Among the n-th conversion expression set, which is generated for each variable _{Y i} converted from the constant _{B i,} when the _W n = g holds only in _Y i = _{B i,} when _W n = 1 is _Y i = The pairing product equation that holds only at 1 is the transformation variable expression, and the set of this transformation variable expression is the nth transformation variable expression set,
A verification target acquisition unit that acquires certification target information, which is information on all constants included in all certification formulas included in all certification formula sets;
GS for all the switcher expressions, all the conversion expression sets, information on all the conversion variable expression sets, and all the switcher expressions, all the conversion expressions, and all the conversion variable expressions output by the proving device. A proof input to obtain information on all results of the proof,
A GS certification confirmation unit for confirming all results of the GS certification;
An object confirmation unit for confirming that all the switcher expressions, all the conversion expressions, and all the conversion variable expressions correspond to the proof object information;
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 among N 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 in the equation that is concealed from the verification device is called a variable, and N is 2 The above integers, n and m are integers of 1 to N, W _n is a group element variable corresponding to the nth proof expression set, g is a group element and a constant other than 1, and i is a correspondence relationship And a number indicating
A proof object acquisition step in which the proof device acquires proof object information which is information of all constants included in all proof expressions included in all 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 the m-th proof expression set that is any one proof expression set;
For all of n = 1,..., N, the proof device converts all of the constant-constant pairing to constant-variable pairing for all proof expressions included in the n-th proof expression set. A conversion step of generating an n th conversion expression set by generating a converted conversion expression;
The certification device, n = 1, ..., and equation paired product of W _n holds only when one or g for _N, W 1, ..., one of W _N is a g other all 1 A switcher generation step for generating a pairing product equation as a switcher equation,
For all of n = 1,..., N, the proving device has W _n = g for each variable Y _i converted from a constant B _{i in} the n-th conversion equation set. An equation of a pairing product that sometimes holds only when Y _i = B _i and holds only when Y _i = 1 when W _n = 1 is generated as a conversion variable expression, and this set of conversion variable expressions is set as the n-th conversion variable. A conversion variable expression generation step as an expression set;
The certification device, W _{m =} g the switcher formula assigns W _{n =} 1 to W _n of n ≠ m, all conversion formula variables and m-th conversion variables included in the m-th conversion expression set Assign all the variables of all the conversion expressions included in all the conversion expression sets other than the m-th by assigning the values obtained from the evidence and Y _i = B _i to the variables of all the conversion variable expressions included in the expression set. Assign a value that results in a pairing result of 1 to all the variables of the conversion variable expressions included in all the conversion variable expression sets other than the mth, and to all switcher expressions, all conversion expressions, and all conversion variable expressions GS certification execution steps for performing GS certification respectively,
A proof output step in which the proof device outputs information about all the switcher expressions, all the conversion expression sets, all the conversion variable expression sets, and all the results of 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 all proof expression sets;
A proof input step in which the verification device acquires information of all the switcher expressions output from the proof device, all the conversion equation sets, all the conversion variable equation sets, and all the results of the GS proof;
A GS proof confirmation step in which the verification device confirms a result of the GS proof for all the switcher expressions, all the conversion expressions, and all the conversion variable expressions;
An object confirmation step in which the verification device confirms that all the switcher expressions, all the conversion expressions, and all the conversion variable expressions correspond to the proof object information;
Proving method with.

Images