JP5321696B2 - Proof device and verification device applied to non-repudiation zero knowledge dialogue proof - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To make it possible to perform a deniable zero-knowledge interactive proof requiring a small amount of both communication and calculation by utilizing a method for a special honest verifier zero-knowledge interactive proof when the method is given. <P>SOLUTION: A second relation proof generation device 417, to which common input and a third random tape are input, outputs a proof of non-interactive knowledge related to a second relation to a second relation proof verification device 423. The second relation proof verification device 423 determines whether or not a prescribed relational expression is established by using the proof of non-interactive knowledge related to the second relation. A proof generation device 425; to which the common input, evidence, a first random tape, and a second random tape are input; generates a proof of non-interactive knowledge of either evidence of evidence meeting a first relation and evidence meeting the second relation. A proof verification device 434 outputs a signal showing acceptance or nonacceptance of the proof as a verification result. <P>COPYRIGHT: (C)2012,JPO&amp;INPIT

Description

  The present invention relates to a proof device and a verification device applied to non-repudible zero knowledge dialogue proof.

  For example, Non-Patent Document 1 describes a technique of non-repudiation zero knowledge dialogue proof in a conventional random oracle model. Hereinafter, the technique described in Non-Patent Document 1 (hereinafter referred to as Conventional Technique 1) will be described.

  FIG. 4 is an explanatory diagram illustrating a configuration described in Non-Patent Document 1. In the drawings in this application, the joining arrows mean that all the original information of the arrows are gathered and sent to the tip of the arrows, and the branching arrows are all or part of the original information of the arrows. Means sent to the end of the arrow.

  Further, the language proved by the prior art 1 is a trichromatic problem of a graph that is NP-complete. Here, the language means a set of data, and “language is a trichromatic problem” means that the data set is a trichromatic problem set. Further, proving that a certain d belongs to a certain language (for example, the three-color problem) is to prove that d belongs to a set of three-color problems. The fact that the prior art 1 can prove this language with repudable zero knowledge means that the prior art 1 can prove all languages belonging to NP with repudable zero knowledge.

A directed graph G _n = (V _G , E _G ) is input as a common input 101 to the proving device 103 and the verification device 104 shown in FIG. Here, V _G is the set of vertices of a graph, E _G is the set of edges, the graph G is represented by both. The number of vertices (denoted as | V _G |) is | V _G | = n.

Further, the color C = (c ₁ , c ₂ ,..., C _n ) of each vertex is input to the proving device 103 as evidence 102. Each i ∈ {1, ..., n} is c _i ∈ {1,2,3}, which represents three colors and expresses the colors of the vertices. C should be painted on all sides so that the two vertices connected at this side have different colors.

  The proving device 103 certifies that the above evidence C regarding G exists in the verification device 104 and proves that it is a zero knowledge dialogue. “Certification of dialogue” means that if C having the above property does not exist for G 1, this fake proof device and verification device (in this example, verification device 104) can be used. After performing communication with each other and calculation in each device, the verification device (verification device 104 in this example) does not output a signal indicating that the proof is finally accepted, and the verification device (in this example, the verification device 103). ) And the verification device (verification device 104 in this example) means that the verification device (verification device 104 in this example) outputs a signal indicating acceptance of the proof.

  The non-repudiation zero knowledge means the following. Whatever data is input and any fake verifier that operates only in polynomial time communicates with the proving device (the proving device 103 in this example), the output of the fake verifier has the following properties (property A and Satisfy.) However, it is assumed that a fake verification device can simultaneously communicate with a plurality of proving devices having the same G and C. Here, the property A is that if there is a simulation device that can communicate with a fake verification device and operates only in polynomial time, and an input to the fake verification device is given to this device, Even if this simulation device cannot communicate with the proving device (the proving device 103 in this example), the output of the fake verification device and data whose distribution cannot be identified can be output. A specific example of property A will be shown. For example, it is assumed that an arbitrary fake verification device outputs some data after communicating with the certification device (the certification device 103 in this example). This data is called a. On the other hand, the simulation device communicates with a fake verification device (behaves as a proof device at this time), and then outputs some data. This data is called b. The simulation device can output data b having a distribution indistinguishable from the distribution of the output data a (property A) no matter what fake verification device is brought.

  Note that “the distribution of data a and the distribution of data b cannot be distinguished” has the following meaning. It is assumed that a certain data distribution A and data distribution B are given. In addition, it is assumed that the data a is data randomly selected from the distribution A, and the data b is data randomly selected from the distribution B. What kind of identification device D (assuming to be a device that outputs 0 or 1), the probability that the identification device D outputs 1 when a is input to the identification device D, and the identification device If the probability that the discriminating device D outputs 1 when b is input to D is equal, it is said that the distribution of data a and the distribution of data b cannot be discriminated. The probability is obtained by repeatedly selecting a and b from the distributions A and B.

Hereinafter, operations of the proving device 103 and the verification device 104 illustrated in FIG. 4 will be described. In the following explanation, an example using the discrete logarithm problem is shown, but a general (stochastic) one-way function is also possible. Let G _{q be a} multiplicative group for which the discrete logarithm problem of order q is difficult, and g be its generator. Let t be a safety variable. It is sufficient that the value of t is 160 or more. Hash (•) is a hash function and its output size is t bits.

Step 1: The verification device 104 randomly selects x ∈ Z / qZ and calculates y = g ^x .

Step 2: The verification apparatus 104 selects x ′ [i] ∈Z / qZ for i = 1,..., T, and sets y ′ [i] = g ^{x ′ [i]} .

Step 3: The verification apparatus 104 calculates a random number r [1, i] ∈ {0,1} ⁿ and a random number r [2, i] ∈ {0, 1} ⁿ for i = 1,. Choose. The verification device 104 performs the hash value c [1, i] = Hash (x ′ [i], r [1, i]) and the hash value c [2, i] for i = 1,. = Hash (x ′ [i] + x, r [2, i]) is generated by communicating with the device 105 that generates the hash function many times.

  Step 4: The verification device 104 calculates a t-bit hash value c as follows.

h = Hash ({g, y, y '[i], c [1, i], c [2, i]} _{i = 1, ..., t} )

  If i = 1, ..., t and the i-th bit of h is 0, the verification device 104 determines that t [1, i] = x ′ [i], t [2, i] = r [1 , i]. If the i-th bit of h is 1, t [1, i] = x ′ [i] + x, t [2, i] = r [2, i]).

Step 5: The verification device 104 sends {g, y, y ′ [i], c [1, i], c [2, i], t [1, i], t [2, i] to the proving device 103. } Send _{i = 1, ..., t} ).

Step 6: The proving apparatus 103 calculates h ′ = Hash ({g, y, y ′ [i], c [1, i], c [2, i]} _{i = 1, ..., t} ). To do. The proving device 103 communicates with a device 107 that calculates a hash function, so that for i = 1,..., T, if the i-th bit of h ′ is 0, c [1, i] = Hash ( t [1, i], t [2, i]) and g ^{t [1, i]} = y '[i], and if the i'th bit of h' is 1, , C [2, i] = Hash (t [1, i], t [2, i]) and g ^{t [2, i]} = y · y '[i] .

Step 7: The proving device 103 generates a non-interactive zero-knowledge proof using the hash function 107 that knows ^{x where} y = g ^x or knows C with respect to G 1. However, prove that you do not know which one you know. The non-interactive zero knowledge proof in step 7 is generated by the method described in Non-Patent Document 3, for example.

  Step 8: The proof device 103 sends the non-interactive zero knowledge proof generated in Step 7 to the verification device 104.

  Step 9: The verification device 104 verifies the non-interactive zero-knowledge proof sent from the verification device 103, and outputs a signal representing acceptance if it is valid and a signal indicating unacceptance if it is invalid, as a verification result 109.

  Assuming that the hash function is a function that returns random data, step 1-5 is a non-interactive zero-knowledge proof of the verifier 104 that the verifier 104 knows x. This can be understood as follows.

The data sent from the proving device 103 is h '= Hash ({g, y, y' [i], c [1, i], c [2, i]} _{i = 1, ..., t} ) On the other hand, it should be as follows.

That is, for i = 1, ..., t, if the i-th bit of h 'is 0, then c [1, i] = Hash (t [1, i], t [2, i]) , G ^{t [1, i]} = y '[i] and the i-th bit of h' is 1, c [2, i] = Hash (t [1, i], t [2, i ]) And g ^{t [2, i]} = y · y '[i].

  Such data can be easily generated if the value of h ′ is determined in advance. Assuming that the hash function is a function that returns a random value, such an assumption can be made. Therefore, the above data can be generated without knowing x. For this reason, the proof device 103 does not obtain any knowledge from this data.

It can be seen from the following that the above proof is a dialogue proof between the proof device 103 and the verification device 104. In step 7, the proving device 103 tells the verification device 104 that either (1) C is known for G, that is, C exists for G or (2) x is known. Prove that there is. However, since the prover 103 cannot obtain any knowledge from the data received in step 5, it cannot obtain the discrete logarithm of G _q and cannot know z. Therefore, it is necessary to prove the above (1).

  Further, in the above operation, it can be understood from the following that the dialogue between the proving device 103 and the verification device 104 is non-repudible zero knowledge. In the random oracle model, the verification device 104 uses the hash value c [1, i] = Hash (x ′ [i], r [1, i]) and the hash value c [2, i] = Hash (x ′ [i ] + x, r [2, i]) and (x '[i], r [1, i]) and (x' [i] + x, r [2, i]) and Must be sent to a random oracle. If the simulator intercepts such a value, x can be easily obtained as (x ′ [i] + x) −x ′ [i] = x. In step 7, the simulation device that knows x can prove “knowing x” in (2) above. Since this cannot be identified from the proof of “knowing C” in (1) above, it is possible to generate data that cannot be identified from the data generated by the proving device 103.

  With the above operation, the non-repudiation zero knowledge dialogue proof in the proof device 103 and the verification device 104 is two rounds. That is, only one communication is required from the verification device 104 to the verification device 103, and one communication from the verification device 103 to the verification device 104 is required.

Further, the conventional special honest verifier zero knowledge dialogue proof technique is described in Non-Patent Document 2, for example. The “special honest verifier” means that the data sent from the verifier (verification device) to the prover (certification device) is a random number. In the special honest verifier zero-knowledge dialogue proof, the message a _R first sent from the verification device to the verification device, the message e _R sent from the verification device to the verification device, and finally the verification device to the verification device. Use message z _R to be sent. “Proof commitment” is the message a _R sent to the verification device first. The “challenge value” is a message e _R that is next sent from the verification device to the certification device. The “response” is a message z _R that is finally sent from the verification device to the verification device.

  Hereinafter, the technique described in Non-Patent Document 2 (referred to as Prior Art 2) will be described. 5 and 6 are explanatory diagrams showing the configuration described in Non-Patent Document 2. FIG. In the following description, the relationship is represented by R 1, the common input (common input 207 in FIGS. 5 and 6) is represented by X, and the evidence (evidence 208 in FIG. 6) is represented by the symbol W. Let (X, W) ∈ R that the common input X and the evidence W satisfy the relation R.

Proof commitment generation apparatus 201 shown in FIG. 5 is an apparatus for generating a proof commitment by the function A _R. The response generation device 202 is a function that generates a response using the function Z _R. The verification device 203 is a device for outputting a verification result by the function V _R. The simulation device 204 shown in FIG. 6 is a device that performs the calculation of the function S _R. Evidence extractor 205 is an apparatus for extracting evidence by a function E _R. The function A _R , the function Z _R , the function V _R , the function S _R , and the function E _R will be described later.

The 3-round special honest verifier zero knowledge dialogue proof for relation R is denoted as SHVZKIP (R). This uses the function A _R for generating proof commitment, the function Z _R for generating response, the function V _{R for} verification, the function S _{R for} simulation, and the function E _R for evidence extraction, and has the following properties: Is satisfied. In the following description, R _P and R _S are random tapes.

[Property 1]
The challenge value e _R (challenge value 212 in the figure) is a random number 206. Further, it is assumed that the proof commitment a _R (the proof commitment 209 in the figure) and the response z _R (the response 210 in the figure) are expressed by the following equations.

a _R = A _R (X, W, R _P )
z _R = Z _R (X, W, R _P , e _R )

At this time, V _R = V _R (X, a _P , e _R , z _R ) = 1 holds. Here, the output of V _R is called a verification result 211.

[Property 2]
The proof commitment a _R (the proof commitment 213 in the figure), the first challenge value e _R and the second challenge value e ′ _R (shown as a set 214 of the first challenge value and the second challenge value in the figure), the first. It is assumed that the one response z _R and the second response z ′ _R (shown as a set 215 of the first response and the second response in the drawing) satisfy the following expression.

V _R (X, a _R , e _R , z _R ) = 1
V _R (X, a _R , e ' _R , z' _R ) = 1
e _R ≠ e ' _R

At this time, the evidence W ′ (evidence 216 in the figure) as W ′ = E _R (a _R , e _R , z _R , e ′ _R , z ′ _R ) becomes (X, W ′) ∈R.

[Property 3]
The challenge value e _R (challenge value 212 in the figure) is a random number. Further, it is assumed that the proof commitment a _R (the proof commitment 209 in the figure) and the response z _R (the response 210 in the figure) are expressed by the following equations. Here, R _P is the random tape 206.

a _R = A _R (X, W, R _P )
z _R = Z _R (X, W, R _P , e _R )

On the other hand, the challenge value e ′ _R (challenge value 216 in the figure) is a random number. Further, it is assumed that the proof commitment a ′ _R (the proof commitment 217 in the figure) and the response z ′ _R (the response 218 in the figure) are derived as follows. However, R _S is a random tape 219.

(a ' _R , z' _R ) = S _R (X, e ' _R , R _S )

At this time, the distribution of (a _R , e _R , z _R ) when the random tape R _P (random tape 206 in the figure) is randomly shaken and the random tape R _S (random tape 219 in the figure) are randomly shaken. It is difficult to distinguish the distribution of (a ' _R , e' _R , z ' _R ).

If you make the dialogue demonstrated using SHVZKIP (R), for e _R choice for verification devices, but there is a restriction that must be random, generally to the verification device there is no guarantee that choose such e _R, this dialogue Proof is not zero knowledge.

  However, since efficient SHVZKIP (R) for many Rs is known, using this SHVZKIP (R) to construct a zero-knowledge dialogue proof while suppressing deterioration in efficiency has application significance. is there.

An example of SHVZKIP (R) is given below. X is two elements (y, g) of G _q , W is an element x of Z / qZ, and (X, W) ∈ R when y = g ^x is satisfied.

The function A _R is, for example, the following function. Input is X, W, and a random tape R _P. Then, a random x ′ ∈ Z / qZ is generated from R _P , and a _R is output with a _R = y ′ = g ^{x ′} .

The function Z _R is, for example, the following function. Inputs are X, W, random tape R _P , and e _R = c. Then, z _R = r = xc + x ′ mod q is calculated and z _R is output.

The function V _R is, for example, the following function. Inputs are X, a _R , e _R , and z _R. If g ^r = y ^c y 'is satisfied, 1 is output, and if not, 0 is output.

The function E _R is, for example, the following function. The inputs are a _R , e _R = c, z _R = r, e ′ _R = c ′, z ′ _R = r ′. Then, W = x = (r−r ′) / (c′−c) mod q is calculated and W is output.

The function S _R is, for example, the following function. Inputs are X, e _R = c, and random tape R _S. Then, a random z _R = r ∈ Z / qZ is generated from R _S , and a _R = y ′ = g ^r y ^-c is generated. Then, (a _R , z _R ) is output.

[Proof of non-interactive knowledge]
Next, proof of non-interactive knowledge will be described. In the above-described prior art 2, the prover proves to the verifier that the case belongs to a certain language by the dialog (communication with each other) between the prover and the verifier. On the other hand, there is a method for proving that a case belongs to a certain language by sending data once to the verifier. This is called non-interactive proof. In particular, when it is proved that a case can be verified in polynomial time that it belongs to a language, it is called proof of non-interactive knowledge.

According to the method described in Non-Patent Document 3, proof of non-interactive knowledge that there is knowledge of R with (X, W) ∈ R for X using special honest verifier zero-knowledge dialogue proof An example (P _R ) can be configured as follows.

P _R = (aR, zR)

However, _RP is a random tape. Further, it is assumed that the following relationship holds.
a _R = A _R (X, W, R _P ),
e _R = Hash (X, a _R ),
a _R = A _R (X, W, R _P , e _R ).

“Rafael Pass”, “On Deniability in the Common Reference String and Random Oracle Model”, “CRYPTO 2003”, 2003, p.316-337, p316-337 “Oded Goldreich”, “Foundations of Cryptography --- Basic Tools”, “Cambridge University Press”, 2001, p.206-207 “Amos Fiat Adi Shamir”, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems”, “CRYPTO 1986”, 1986, p.186-194

  However, the above prior art 1 has the following problems.

In the prior art 1, in step 3, it is necessary to generate _t commitments {c [1, i] and c [2.i]} _{i = 1} ,. The reason is as follows. The simulator has two commitments c [1, i] = Hash (x '[i], r [1, i]) and c [2, i] = Hash (x' [i] + x, r [2 , i]) requires committed values x '[i] and x' [i] + x. That is, the simulator will not work unless both commitments are made correctly. However, in the actual operation of the verification apparatus, only one of the values committed for each i is disclosed. Therefore, even if the value that is not disclosed is illegally generated, the proving device may not be detected. Because of this possibility, by generating (t) commitments for a sufficiently large number of i, the probability that the verification device can lose the proving device for all i is reduced sufficiently (1/2 ^t ). Yes.

  For the above reasons, the conventional technique requires a verification apparatus to generate a large number of commitments, and in step 6 requires a verification apparatus to perform a large number of calculations. This has the disadvantage that both the calculation time and the amount of communication between both are large.

  Step 1-5 described in the prior art 1 is a non-interactive zero knowledge proof of knowledge of discrete logarithm, but by comparing with the non-interactive zero knowledge proof of knowledge of discrete logarithm, the difference between the calculation amount and the communication amount is as follows. I understand well.

Let y = g ^x . G, y, x is input to the proving device, and g, y is input to the verifier (verification device).

Step 1: The proving device selects x ′ ∈ Z / qZ and generates y ′ = g ^{x ′} .

  Step 2: The proving device calculates c = Hash (g, y, y ′).

  Step 3: The proving device calculates t = c x + x ′ mod q.

  Step 4: The proving device sends (t, c) to the verification device.

Step 5: The verification device confirms that c = Hash (g, y, g ^t y ^−c ) holds.

  The amount of communication and the amount of computation in the non-interactive zero-knowledge proof shown here are both 1 / t times, although they are used in the conventional technology, and are very efficient.

  However, the method shown here cannot be simply applied to the conventional method already described. This is because even if the pseudo-device can extract the input (g, y, y ′) to the hash, it cannot determine x.

  On the other hand, as described at the end of the description of the prior art 2, the prior art 2 has many efficient methods for many R 1, but does not have zero knowledge. In particular, it has no undeniable zero knowledge.

  The present invention has been made in view of the above-mentioned problems, and when a special honest verifier zero knowledge dialogue proof method is provided, it can be used to reduce the amount of communication and the amount of computation. The purpose is to enable knowledge dialogue proof.

A proving device according to the present invention is a proving device that is communicably connected to a verification device,
Communicating with a first proof commitment generator for generating a proof commitment of a special honest verifier zero knowledge dialog proof of the first relationship based on common input and evidence satisfying a predetermined first relationship and a random tape Communicating with a first response generating device that generates a response of a special honest verifier zero-knowledge dialogue proof about the first relationship based on the common input and evidence on the first relationship, the random tape, and the challenge value A signal representing acceptance or non-acceptance of a special honest verifier zero-knowledge dialogue proof of the second relationship based on the common input, proof commitment, challenge value and response of the second relationship The second dialogue proof verification device is connected to be communicable, and the second relationship is based on the common input, challenge value, and random tape regarding the second relationship. A common input and evidence satisfying a predetermined first relationship, connected to a simulation device that generates a proof commitment and a response, and communicatively connected to a hash function calculation device that calculates a hash function. Common input such as common input, random tape input means for inputting the first random tape and the second random tape, and evidence corresponding to the common input from the verification device and the common input. Whether to accept the non-dialogue proof based on the result of communicating with the non-dialogue proof receiving means for receiving the non-dialogue proof of knowledge and the hash function calculator and the second dialog proof verifier using the non-dialogue proof Non-dialogue proof acceptance non-acceptance judgment means for judging the first random tape, second random tape, common input satisfying the first relationship Common input related to the first relationship by communicating with the simulation device, the first proof commitment generation device, the hash function calculation device, and the first response generation device using the common input included in the certificate and the non-dialogue proof Evidence knowledge non-dialogue proof generating means and evidence knowledge non-dialogue proof generating means for generating knowledge non-dialogue proof of knowledge that either knowledge of evidence for knowledge or knowledge of evidence for common input related to second relation exists And non-dialogue proof transmitting means for transmitting the non-dialogue proof of knowledge generated to the verification device.

  The non-dialog proof receiving means receives a non-dialog proof including a common input, proof commitment, and response regarding the second relationship from the verification device, and the non-dialog proof acceptance non-acceptance determination means is included in the non-dialog proof. Send the common input and proof commitment for the second relationship to the hash function calculator, and calculate the hash value that will be the challenge value according to the common input and proof commitment for the second relationship. Whether or not to accept the non-dialogue proof by a signal output from the second dialog proof verifier by transmitting common input, proof commitment, and response regarding the included second relationship to the second dialog proof verifier The evidence knowledge non-dialogue proof generation means generates a challenge value related to the second relationship using the second random tape, and a common input related to the second relationship, Send the challenge value for the second relationship, and the second random tape to the simulator to generate a proof commitment and response for the second relationship, common input and evidence satisfying the first relationship, and the first random tape Is sent to the first proof commitment generation device, and the proof commitment for the first relationship is generated, and the common input and proof commitment for the first relationship and the common input for the second relationship are generated by the simulation device. The proof commitment for the second relationship is transmitted to the hash function calculation device, and the hash value corresponding to the common input and proof commitment for the first relationship and the common input and proof commitment for the second relationship is calculated. The challenge for the first relationship based on the hash value and the challenge value for the second relationship And send the common input and evidence satisfying the first relationship, the first random tape, and the challenge value for the first relationship to the first response generator to generate a response for the first relationship. Proof commitment, challenge value, and response for the first relationship, challenge value for the second relationship, and proof commitment and response for the second relationship generated by the simulator as non-dialogue proof of knowledge It may be.

The verification device according to the present invention is a verification device that is communicably connected to the proof device described above, and is based on the common input, the proof commitment, the challenge value, and the response related to the first relationship. Honest verifier is connected to the first dialog proof verification device that outputs a signal indicating acceptance or non-acceptance of zero knowledge dialog proof, and is communicably connected to the second relation, common input, proof commitment, challenge value, and response Is connected to a second dialogue proof verification device that outputs a signal representing acceptance or non-acceptance of a special honest verifier zero knowledge dialogue proof relating to the second relationship, and is common to the second relationship. A second proof commitment student that generates a proof commitment of a special honest verifier zero knowledge dialog proof of the second relationship based on input and evidence and random tape Second response generation communicatively connected to the device to generate a special honest verifier zero knowledge dialogue proof response for the second relationship based on common input and evidence for the second relationship, random tape and challenge value A common input input means connected to the apparatus and communicably connected to a hash function calculation apparatus for calculating a hash function and receiving a common input related to the first relationship; and a random as a third random tape Random tape input means to which tape R _V and random tape R ′ _V are input, common input that generates the common input and evidence satisfying the second relationship from the random tape R ′ _{V of} the third random tape, etc. Generating means, common input and proof satisfying the second relationship generated by the generating means such as common input, and a random tape R _{V of} the third random tape. Using non-dialogue proof of knowledge of evidence to satisfy the second relationship with the common input by communicating with the second proof commitment generator, the second response generator, and the hash function calculator Common knowledge about the first relationship from the proof device and the non-dialogue proof transmitting means for transmitting the non-dialogue proof of the knowledge generated by the evidence knowledge non-dialogue proof generating means to the proof device Non-dialogue proof receiving means for receiving a non-dialogue proof of knowledge that there is knowledge of evidence for input or knowledge of evidence for common input regarding the second relationship, and common input regarding the second relationship; The first dialog proof verification device, the second pair, using the common input related to the first relationship input to the common input input means and the non-dialog proof received by the non-dialog proof receiving means. A communication means for determining whether or not to accept the non-interactive proof received by the non-interactive proof receiving means by communicating with the proof verification device and the hash function calculating device, and a determination means for outputting the determination result; It is characterized by that.

Evidence knowledge non-interactive proof generation means, a common input and evidence satisfy a second relationship, and a random tape R _V of the third random tape sent to the second proof commitment generation apparatus, and a second relationship Generate a proof commitment, send the common input for the second relationship and the proof commitment for the second relationship to the hash function calculator, calculate the hash value that will be the challenge value according to the common input and the proof commitment, The common input and evidence satisfying the two relations, the random tape R _V and the challenge value are transmitted to the second response generation device to generate a response relating to the second relation, and the common input and proof relating to the second relation. The commitment and the response are assumed to be non-dialogue proofs of knowledge, and the non-dialogue proof receiving means receives a proof commitment concerning the first relationship from the proof device. A non-dialogue proof including a challenge value and a response and a proof commitment, a challenge value, and a response regarding the second relationship is received, and the determination means is a common input regarding the first relationship input to the common input input means; , Transmitting a proof commitment, a challenge value, and a response regarding the first relationship included in the non-dialogue proof to the first dialog proof verifier, receiving a signal output by the first dialog proof verifier, Sends the common input for the relationship and the proof commitment, challenge value, and response for the second relationship included in the non-dialogue proof to the second dialog proof verifier and receives the signal output by the second dialog proof verifier Send the common input and proof commitment for the first relationship and the common input and proof commitment for the second relationship to the hash function computing device, A hash value corresponding to the common input and proof commitment related to the clerk and the common input and proof commitment related to the second relationship is calculated, and the challenge value and the second relationship related to the first relationship included in the hash value and the non-dialogue proof are calculated. It is determined whether or not a predetermined relationship is established between the challenge value and the determination value, and based on the result of the determination and the signals received from the first dialog proof verification device and the second dialog proof verification device, It may be configured to determine whether or not to accept the dialogue proof.

  According to the present invention, it is possible to realize non-repudiation zero knowledge dialogue proof that both the communication amount and the calculation amount are small.

It is explanatory drawing which shows the certification | authentication apparatus and verification apparatus of the 1st Embodiment of this invention. It is explanatory drawing which shows the certification | authentication apparatus and verification apparatus of the 2nd Embodiment of this invention. It is explanatory drawing which shows the Example of this invention. It is explanatory drawing which shows the structure described in the nonpatent literature 1. It is explanatory drawing which shows the structure described in the nonpatent literature 2. It is explanatory drawing which shows the structure described in the nonpatent literature 2.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  In the following explanation, reference is made to the commitment of the challenge value, but this “commitment” is different from the “proof commitment” already explained. First, “commitment” will be described. “Commitment of U (for example, challenge value)” is data having the following properties. In other words, the property that "even if only U's commitment is given, no information about U is obtained, and the one that generates U's commitment can later prove that this is U's commitment." And has the property that “it is not possible to prove that U ′ is a commitment for any U ′ ≠ U”. The “challenge of commitment value” mentioned in the following explanation also has this property.

Embodiment 1 FIG.
FIG. 1 is an explanatory diagram illustrating a proving device and a verification device according to the first embodiment of this invention. The proving device 301 and the verification device 302 are connected so that they can communicate with each other. To the proving device 301, a common input X (X, W) ∈ R, an evidence W, and a first random tape _RP are input. This relationship R is a predetermined relationship. In the present embodiment, for convenience, the relationship R will be referred to as the first relationship.

  The common input is data input in common to the proving device and the verification device. However, in the second embodiment to be described later, a case where the verification device generates data (X ′ in the second embodiment) as a common input and transmits it to the certification device is also shown. In this way, data generated by the verification device and transmitted to the certification device is also a common input.

  The proof device 301 includes a challenge value commitment verification device 324 (hereinafter referred to as a challenge value commitment verification device 324) related to the first relationship, and an interactive knowledge proof generation device 330 (hereinafter referred to as a challenge relationship commitment verification device 324). And a proof generation device 330).

  The verification device 312 includes a challenge value commitment generation device 312 (hereinafter referred to as a challenge value commitment generation device 312) related to the first relationship, and an interactive knowledge proof verification device 340 (hereinafter referred to as the challenge relationship commitment generation device 312). And proof verification device 340).

  The challenge value commitment verification device 324 is communicably connected to the hash function calculation device 310. Further, the proof generation device 330 is communicably connected to a proof commitment generation device 303 (hereinafter referred to as a proof commitment generation device 303) of the special honest verifier zero knowledge dialogue proof relating to the first relationship R. Further, the proof generation device 330 is communicably connected to a response generation 304 (hereinafter referred to as a response generation device 304) of the special honest verifier zero knowledge dialogue proof regarding the first relationship R.

  The challenge value commitment generation device 312 is communicably connected to a hash function calculation device 311. The proof verification device 340 is communicably connected to a special honest verifier zero knowledge dialogue proof verification device 305 (hereinafter referred to as a dialogue proof verification device 305) related to the first relationship R.

The proof commitment generation device 303 generates a proof commitment according to the input from the proof generation device 330 according to a function (function A _R ) and outputs the proof commitment to the proof generation device 330. A specific calculation example of the function A _R in the present embodiment is the same as the function A _R shown in the conventional technique 2, for example.

The response generation device 304 generates a response according to the input from the proof generation device 330 according to the function (function Z _R ), and outputs the response to the proof generation device 330. A specific calculation example of the function Z _R in the present embodiment is the same as the function Z _R shown in the conventional technique 2, for example.

The dialogue proof verification apparatus 305 generates a verification result corresponding to the input from the proof verification apparatus 340 according to the function (function V _R ), and outputs the verification result to the proof verification apparatus 340. A specific calculation example of the function V _R in the present embodiment is the same as the function V _R shown in the conventional technique 2, for example. If the verification result is 1, it means that the proof is accepted, and if the verification result is 0, it means that the proof is not accepted.

  A challenge value commitment verification device 324 receives a challenge value commitment (c) from the challenge value commitment generation device 312. The challenge value commitment verification device 324 determines whether the calculation result of the hash function using the challenge value and the random number output from the proof verification device 340 to the proof generation device 330 matches the challenge value commitment c. To do.

The above-mentioned common input X 1, evidence W 2, and first random tape _RP are input to the proof generation device 330. The proof generation device 330 outputs the proof commitment generated by the proof commitment generation device 303 to the proof verification device 340. Thereafter, a challenge value and a random number are input from the proof verification device 340 to the proof generation device 330. When the calculation result of the hash function using the challenge value and the random number matches the challenge value commitment c, the proof generation device 330 outputs the response generated by the response generation device 304 to the proof verification device 340. To do.

Commitment generating device 312 of the challenge value is the common input X, and the second random tape R _V is input. The challenge value commitment generation device 312 generates a challenge value and a random number, and causes the hash function calculation device 311 to generate a commitment value commitment c. The challenge value commitment generation device 312 outputs the challenge value commitment c to the challenge value commitment verification device 324.

  The proof commitment is input from the proof generation device 330 to the proof verification device 340. Thereafter, the proof verification device 340 outputs the challenge value and the random number to the proof generation device 330. Then, a response is input from the proof generation device 330. Upon receiving the response, the proof verification device 340 causes the dialog proof verification device 305 to generate a verification result and outputs the verification result 322.

In FIG. 1, the common input X is indicated by reference numeral 306. Also, the evidence W is indicated by using a reference numeral 307. Further, the first random tape _RP is indicated by using a reference numeral 308. In addition, a second random tape _RV is indicated by reference numeral 309.

  Next, the operation of the repudiation zero knowledge dialogue proof of the relation R 1 by the proof device 301 and the verification device 302 will be described.

First, the common input X with (X, W) ∈ R, the evidence W, and the first random tape _RP are input to the proof generation device 330 of the proof device 301.

Subsequently, the common input X and the second random tape R _V are input to the commitment value commitment generation device 312 included in the verification device 302.

Next, the challenge value commitment generation device 312 causes the hash function calculation device 311 to generate a commitment value commitment related to the first relationship R as follows. The challenge value commitment generator 312 selects the challenge value e _R using the second random tape R _V. Further, the commitment value commitment generator 312 selects the random number r using the second random tape R _V. This random number r is evidence of a challenge value commitment. The challenge value commitment generation device 312 transmits the challenge value e _R and the random number r to the hash function calculation device 311. The hash function calculation device 311 calculates a challenge value commitment c as c = Hash (e _R , r), and transmits the challenge value commitment c to the challenge value commitment generation device 312. The communication at this time is shown as communication 313 in FIG.

  The challenge value commitment generation device 312 transmits the challenge value commitment c received from the hash function calculation device 311 to the challenge value commitment verification device 324 (communication 314 shown in FIG. 1). The challenge value commitment verification device 324 waits for a challenge value commitment c to be transmitted from the challenge value commitment generation device 312, and receives the challenge value commitment c from the challenge value commitment generation device 312.

When the challenge value commitment verification device 324 receives the challenge value commitment c, the proof generation device 330 transmits the common input X, evidence W, and the first random tape _RP to the proof commitment generation device 303. Proof commitment generation apparatus 303, by the function _{A R, a R = A R} (x, w, R P) as to generate a proof commitment a _R. Then, the proof commitment generation device 303 transmits the proof commitment a _R to the proof generation device 330. The communication at this time is shown as communication 315 in FIG.

The proof generation device 330 transmits the proof commitment a _R received from the proof commitment generation device 303 to the proof verification device 340 (communication 316 shown in FIG. 1). After transmitting the proof commitment a _R , the proof generation device 330 waits for the challenge value committed by the challenge value commitment c and the proof of the commitment (random number r) to be transmitted from the proof verification device 340.

After receiving the certification commitment a _R , the certification verification device 340 transmits the challenge value e _R and the random number r to the certification generation device 330 (communication 317 shown in FIG. 1). After transmitting the challenge value e _R and the random number r ₁ , the proof verification device 340 waits for a response from the proof generation device 330.

When the proof generation device 330 receives the challenge value e _R and the random number r 1, the challenge value commitment verification device 324 communicates with the hash function calculation device 310 (communication 319 shown in FIG. 1), and the challenge value e _R and the random number. It is determined whether the calculation result of the hash function using r matches the commitment value commitment c. That is, the hash function calculation device 310 calculates Hash (e _R , r), and determines whether or not the calculation result matches the commitment value commitment c already received. In other words, it is verified by using the random number r whether or not the commitment value c already received is a commitment value e _R commitment.

If c = Hash (e _R , r) does not hold, the challenge value commitment verification device 324 outputs a stop command of the proving device 301 to the proof generating device 330 (output 325 shown in FIG. 1). When the stop command is output, the certification device 301 stops the operation. If c = Hash (e _R , r) is established, no stop command is output.

If the stop command is not output, the proof generation device 330 transmits the common input X, the evidence W, the challenge value e _R , and the first random tape _RP to the response generation device 304. Response generation apparatus 304, by the function _{Z R, z R = Z R} (x, w, e R, R P) as to generate a response z _R. Then, the response generation device 304 transmits the response z _R to the proof generation device 330. The communication at this time is shown as communication 320 in FIG.

The proof generation device 330 transmits the response z _R received from the response generation device 304 to the proof verification device 340 (communication 318 shown in FIG. 1).

Upon receiving the response z _R , the proof verification device 340 transmits the common input X 1, the proof commitment a _R , the challenge value e _R , and the response z _R to the dialog proof verification device 305. The proof verification device 340 may receive the challenge value e _R from the commitment value commitment generation device 312 (communication 326 shown in FIG. 1). The dialogue proof verification apparatus 305 derives the calculation result of V _R (X, a _R , e _R , z _R ) by the function V _R. This calculation result is, for example, either 1 or 0 and represents acceptance or non-acceptance of the proof. The dialogue proof verification device 305 transmits a signal indicating acceptance or non-acceptance of the proof to the proof verification device 340. The communication at this time is shown as communication 321 in FIG.

  The proof verification apparatus 340 outputs the received signal (a signal indicating acceptance or non-acceptance of the proof) as a verification result 322.

  According to the first embodiment, transmission from the verification device 302 to the verification device 301 includes transmission of a challenge value commitment c (communication 314 shown in FIG. 1), and the commitment is a commitment value commitment. Is transmitted only (communication 317 shown in FIG. 1). Therefore, the amount of communication can be reduced, the system can be simplified, and communication can be made efficient.

  In the first embodiment, the common input unit, the random tape input unit, the proof commitment generation control unit, the challenge value reception unit, and the response generation control unit included in the proof device are the proof generation device 330 of the proof device 301. It is realized by. Further, the challenge value commitment receiving means and the challenge value commitment verification means included in the proof device are realized by the challenge value commitment verification device 324 of the proof device 301.

  The common input input means, random tape input means, challenge value generation means, random number generation means, and challenge value commitment generation control means included in the verification apparatus are realized by the challenge value commitment generation apparatus 312 of the verification apparatus 302. Further, the proof commitment receiving means, the response receiving means, and the verification result output means included in the verification device are realized by the proof verification device 340 of the verification device 303.

Embodiment 2. FIG.
In the following description, the bitwise exclusive OR is represented by a sign ∨.

FIG. 2 is an explanatory diagram illustrating a proving device and a verification device according to the second embodiment of this invention. The proving device 401 and the verification device 402 are connected so that they can communicate with each other. To the proving device 401, the common input X (X, W) ∈ R, the evidence W, the first random tape R _P , and the second random tape R ′ _P are input. This relationship R is a predetermined relationship, and is hereinafter referred to as a first relationship. Note that a second relationship different from the first relationship R is R ′.

  The proof device 401 is a non-interactive knowledge proof verification device 423 (hereinafter referred to as a second relationship proof verification device 423) related to the second relationship, a non-interactive proof that satisfies the first relationship, A proof generation device 425 (hereinafter referred to as a proof generation device 425) for knowledge of any of the evidences satisfying the two relations.

  The verification device 402 is a non-interactive knowledge proof generation device 417 (hereinafter referred to as a second relationship proof generation device 417) related to the second relationship and a non-interactive knowledge satisfying the first relationship, or A knowledge proof verification device 434 (hereinafter, referred to as a proof verification device 434) of any of the knowledge satisfying the two relations.

  The second relationship proof verification device 423 is communicably connected to the hash function calculation device 410. The second relationship proof verification device 423 is also communicably connected to a special honest verifier zero knowledge dialog proof verification device 408 (hereinafter referred to as a second dialog proof verification device 408) related to the second relationship R ′. ing.

  The proof generation device 425 is communicably connected to the hash function calculation device 410. Further, the proof generation device 425 is communicably connected to a proof commitment generation device 403 (hereinafter referred to as a first proof commitment generation device 403) of the special honest verifier zero knowledge dialogue proof relating to the first relationship R. Further, the proof generation device 425 is communicably connected to a response generation device 404 (hereinafter referred to as the first response generation device 404) of the special honest verifier zero knowledge dialogue proof relating to the first relationship R. Further, the proof generation device 425 is communicably connected to a special honest verifier zero knowledge dialogue proof simulation device 409 (hereinafter referred to as a second relationship simulation device 409) regarding the second relationship R ′.

  The second relationship proof generation device 417 is communicably connected to the hash function calculation device 411. The second relationship proof generation device 417 is communicably connected to a proof commitment generation device 406 (hereinafter, second proof commitment generation device 406) of the special honest verifier zero knowledge dialogue proof regarding the second relationship R ′. . Furthermore, the second relationship proof generation device 417 is communicably connected to a response generation device 407 (hereinafter, second response generation device 407) of the special honest verifier zero knowledge dialogue proof regarding the second relationship R ′.

  The proof verification device 434 is communicably connected to the hash function calculation device 411. Further, the proof verification device 434 is communicably connected to a special honest verifier zero knowledge dialogue proof verification device 405 (hereinafter referred to as a first dialogue proof verification device 405) related to the first relationship R. Further, the proof verification device 434 is connected to the second dialog proof verification device 408 so as to be communicable.

The first proof commitment generation device 403 generates a proof commitment corresponding to the input from the proof generation device 425 according to a function (function A _R ) and outputs the proof commitment to the proof generation device 425. A specific calculation example of the function A _R in the present embodiment is the same as the function A _R shown in the conventional technique 2, for example.

The first response generation device 404 generates a response corresponding to the input from the proof generation device 425 according to the function (function Z _R ), and outputs the response to the proof generation device 425. A specific calculation example of the function Z _R in the present embodiment is the same as the function Z _R shown in the conventional technique 2, for example.

The first dialog proof verification device 405 generates a verification result (a signal indicating acceptance or non-acceptance of the proof) according to the input from the proof verification device 434 according to the function (function V _R ). Output to 434. A specific calculation example of the function V _R in the present embodiment is the same as the function V _R shown in the conventional technique 2, for example. If the verification result is 1, it means that the proof is accepted, and if the verification result is 0, it means that the proof is not accepted.

The second proof commitment generation device 406 generates a proof commitment (referred to as a _{R ′} ) corresponding to the input from the second relationship proof generation device 417 according to the function (referred to as function A _{R ′} ), and the second The data is output to the relationship proof generation device 417. The function A _{R ′} is a function that takes a common input, evidence, and random tape as inputs and outputs a proof commitment. Here, description will be made assuming that the function A _{R ′} is a function that performs a calculation different from the function A _R , but if the first relationship R and the second relationship R ′ are the same relationship, the function A _{R 'it} may be a function that calculates the same function a _R.

The second response generation device 407 generates a response according to the input from the second relationship proof generation device 417 according to the function (function Z _{R ′} ), and outputs the response to the second relationship proof generation device 417. The function Z _{R ′} is a function that inputs a common input, evidence, challenge value, and random tape and outputs a response (denoted z _{R ′} ). Here, description will be made assuming that the function Z _{R ′} is a function that performs a calculation different from the function Z _R , but if the first relationship R and the second relationship R ′ are the same relationship, the function Z _{R ′ 'May} be a function that performs the same calculation as the function Z _R.

The second dialog proof verification device 408 indicates a verification result (representing acceptance or non-acceptance of the proof) according to an input from the second relationship proof verification device 423 or the proof verification device 434 according to a function (function V _{R ′} ). Signal) and the verification result is output to the second relationship proof verification device 423 and the proof verification device 434. The function V _{R ′} is a function that receives a proof commitment, a response, a common input, and a challenge value and outputs a verification result. Here, description will be made assuming that the function V _{R ′} is a function that performs a calculation different from the function V _R , but if the first relationship R and the second relationship R ′ are the same relationship, the function V _{R 'it} may be a function that calculates the same function V _R. If the verification result is 1, it means that the proof is accepted, and if the verification result is 0, it means that the proof is not accepted.

The second relation simulation device 409 outputs a proof commitment and a response according to the input from the proof generation device 425 according to a function (function S _{R ′} ). The function S _{R ′} is a function that receives a common input, a challenge value, and a random tape, and outputs a proof commitment and a response. Specific example of calculation of the function S _{R 'in} the present embodiment, for example, is similar to the function S _R shown in the prior art 2.

A common input X and a third random tape are input to the second relationship proof generation device 417. Note that R _V and R ′ _V are input as the third random tape. Further, the second relationship proof generation device 417 outputs a non-interactive knowledge proof (referred to as P _{R ′} ) regarding the second relationship R ′ to the second relationship proof verification device 423.

Second relationship proof verification apparatus 423, by using a 'certificate P _R of the non-interactive _knowledge' second relation R, determines whether a predetermined relationship is satisfied.

The above-mentioned common input X, evidence W, first random tape R _P , and second random tape R ′ _P are input to the proof generation device 425. Then, generate a proof of knowledge (referred to as _{PR∨R '} ) for either non-interactive evidence that satisfies the first relationship or evidence that satisfies the second relationship, and prove the proof. The data is output to the verification device 434.

The proof verification apparatus 434 outputs a signal indicating acceptance or non-acceptance of the proof _{PR R′R ′} as the verification result 435 based on the communication result between the first dialog proof verification apparatus 405 and the second dialog proof verification apparatus 408. .

In FIG. 2, the common input X is indicated by reference numeral 412. In addition, the proof W is indicated by using a reference numeral 413. Further, the first random tape _RP is indicated by using a reference numeral 414. Further, the second random tape R ′ _P is indicated by reference numeral 415. In addition, the third random tapes R _V and R ′ _V are indicated by reference numeral 416.

  Next, the operation of the repudiation zero knowledge dialogue proof of the relation R 1 by the proof device 401 and the verification device 402 will be described.

First, the common input X 1, the evidence W 1, the first random tape R _P , and the second random tape R ′ _P with (X, W) ∈ R are input to the proof generation device 425 of the proof device 401.

Subsequently, the common input X and the third random tapes R _V and R ′ _V are input to the second relationship proof generation device 417 of the verification device 402.

Next, the second relationship proof generation device 417 generates a non-interactive knowledge proof PR ′ for the second relationship _{R ′} as follows.

The second relationship proof generation device 417 uniformly and randomly selects X ′, W ′ (common input and evidence regarding the second relationship R ′) such that (X ′, W ′) ∈ R ′ as a third random number. generated using R _'V of the tape.

Next, the second relationship proof generation apparatus 417, the common input X ', evidence W', and transmits the R _V of the third random tape to the second proof commitment generation apparatus 406. Second proof commitment generation apparatus 406 _'by, a _R' function _{A R = A R '(X} ', W ', R V) as proof commitment a _R' to generate. Then, the second proof commitment generation device 406 transmits the proof commitment a _{R ′} to the second relationship proof generation device 417. The communication at this time is shown as communication 418 in FIG.

Next, the second relationship proof generation device 417 transmits the common input X ′ and the proof commitment a _{R ′} to the hash function calculation device 411. The hash function calculation device 411 calculates a hash value as e _{R ′} = Hash (X ′, a _{R ′} ). The hash function calculation device 411 transmits the hash value e _{R ′} to the second relationship proof generation device 417. The communication at this time is shown as communication 419 in FIG.

Next, the second relationship proof generation device 417 transmits the common input X ′, the evidence W ′, the hash value e _{R ′} , and R _V of the third random tape to the second response generation device 407. Here, the hash value e _{R ′} is transmitted as a challenge value. Second response generation apparatus 407 _'by, z _R' function _{Z R = Z R '(X} ', W ', e R', R V) as to generate a response z _{R '.} The second response generation device 407 transmits the response z _{R ′} to the second relationship proof generation device 417. The communication at this time is shown as communication 420 in FIG.

The second relationship proof generation device 417 sets the non-interactive knowledge proof PR ′ for the second relationship _{R ′} as (X ′, a _{R ′} , z _{R ′} ). The second relationship proof generation device 417 transmits the proof PR _′ = (X ′, a _{R ′} , z _{R ′} ) generated as described above to the second relationship proof verification device 423 (shown in FIG. 2). Communication 421).

The second relationship proof verification device 423 receives the proof P _{R ′} (the non-dialogue proof of the knowledge of the common input X ′ relating to the second relationship R ′ and the evidence W ′ corresponding to the common input X ′). Waiting to come, the above-described communication 421 receives the proof P _{R ′} = (X ′, a _{R ′} , z _{R ′} ) from the second relationship proof generation device 417.

The second relationship proof verification device 423 of the proof device 401 verifies the non-interactive knowledge proof PR ′ for the second relationship _{R ′} as follows.

The second relationship proof verification device 423 transmits the common input X ′ and the proof commitment a _{R ′} to the hash function calculation device 410. The hash function calculation unit 410 calculates a hash value as e _{R ′} = Hash (X ′, a _{R ′} ). The hash function calculation device 410 transmits the hash value e _{R ′} to the second relationship proof verification device 423. The communication at this time is shown as communication 422 in FIG.

The second relationship proof verification device 423 transmits the common input X ′, proof commitment a _{R ′} , hash value e _{R ′} , and response z _{R ′} to the second dialog proof verification device 408. Here, the hash value e _{R ′} is transmitted as a challenge value. The second dialogue proof verification device 408 derives the calculation result of V _{R ′} (X ′, a _{R ′} , e _{R ′} , z _{R ′} ) by the function V _{R ′ and} uses the calculation result as the second relation proof verification. Transmit to device 423. The communication at this time is shown as communication 424 in FIG.

The second relationship proof verification device 423 determines whether V _{R ′} (X ′, a _{R ′} , e _{R ′} , z _{R ′} ) = 1 holds. If not, the proving device 401 is stopped. Further, if it is established, the proving device 401 performs the following operation. That is, if V _{R ′} (X ′, a _{R ′} , e _{R ′} , z _{R ′} ) = 1 holds, the proof PR _{R ′} is accepted, and if not, the proof PR _{R ′} is not accepted. And

The proof generation device 425 of the proof device 401 performs non-interactive knowledge of knowledge about one of the evidences satisfying the first relation R or the evidence satisfying the second relation R ′ as follows. Proof P _{R∨R '} is generated.

The proof generation device 425 generates a random number e ′ _{R ′} using the second random tape R ′ _P, and sets this as a challenge value for the second relationship R ′.

Next, the proof generation device 425 transmits the common input X ′, the challenge value e ′ _{R ′} , and the second random tape R ′ _P to the second relationship simulation device 409, and sends it to the second relationship simulation device 409. Generate a proof commitment a '_R' and a response z '_R' for the second relation R '. The second relation simulator 409 derives (a ′ _{R ′} , z ′ _{R ′} ) = S _{R ′} (X ′, e ′ _{R ′} , R ′ _P ) by the function S _{R ′} , and proves the proof commitment a ′. _{R ′} and response z ′ _{R ′} are transmitted to the proof generation device 425. The communication at this time is shown as communication 426 in FIG.

Next, the proof generation device 425 transmits the common input X 1, the evidence W 2, and the first random tape _RP to the first proof commitment generation device 403. The first proof commitment generation apparatus 403, by the function _{A R, a R = A R} (X, W, R P) as to generate a proof commitment a _R, and transmits the certificate generation unit 425. The communication at this time is shown as communication 427 in FIG.

Next, the proof generation device 425 uses the common input X relating to the first relationship R, the proof commitment a _R , the common input X ′ relating to the second relationship R ′, and the proof commitment a ′ _{R ′} to the hash function calculation device 410. Send to. The hash function calculation unit 410 calculates a hash value e as e = Hash (X, a _R , X ′, a ′ _{R ′} ), and transmits the hash value to the proof generation unit 425. The communication at this time is shown as communication 428 in FIG.

Next, the proof generation device 425 calculates a challenge value e _R as e _R = e ∨ e ′ _{R ′} . The proof generation device 425 transmits the common input X, the evidence W, the challenge value e _R , and the first random tape _RP to the first response generation device 404 to generate a response z _R. The first response generation apparatus 404, by the function _{Z R, z R = Z R} (X, W, e R, R P) as to generate a response z _R, and transmits a response z _R to proof generation apparatus 425. The communication at this time is shown as communication 429 in FIG.

The proof generation device 425 _obtains a non-interactive knowledge proof P _{R∨R ′ of} knowledge about either evidence of the evidence satisfying the first relation R 1 or the evidence satisfying the second relation R ′ (a _R , e _R , z _R , a ′ _{R ′} , e ′ _{R ′} , z ′ _{R ′} ). The proof generation device 425 generates the proof _{PR ∨R ′} = (a _R , e _R , z _R , a ′ _{R ′} , e ′ _{R ′} , z ′ _{R ′} ) generated as described above, and the verification device 402. To the proof verification device 434 (communication 429 shown in FIG. 2).

The proof verification device 434 transmits the common input X (the common input X input to the verification device 402), the proof commitment a _R , the common input X ′, and the proof commitment a ′ _{R ′} to the hash function calculation device 411. Let the hash value be calculated. The hash function calculation device 411 derives the calculation result of Hash (X, a _R , X ′, a ′ _{R ′} ), and transmits the calculation result (hash value) to the proof verification device 434. The communication at this time is shown as communication 430 in FIG. Then, the proof verification device 434 determines whether the calculation result of Hash (X, a _R , X ′, a ′ _{R ′} ) is equal to e _R ∨ e ′ _{R ′} .

Next, the proof verification device 434 transmits the common input X, the proof commitment a _R , the challenge value e _R , and the response z _R to the first dialog proof verification device 405. The first dialog proof verification device 405 derives the calculation result of V _R (X, a _R , e _R , z _R ) by the function V _R and transmits the calculation result to the proof verification device 434. The communication at this time is shown as communication 432 in FIG. The certification verification device 434 determines whether or not V _R (X, a _R , e _R , z _R ) = 1 holds.

Next, the proof verification device 434 transmits the common input X ′, the proof commitment a ′ _{R ′} , the challenge value e ′ _{R ′} , and the response z ′ _{R ′} to the second dialog proof verification device 408. The second dialog proof verification device 408 derives the calculation result of V _{R ′} (X ′, a ′ _{R ′} , e ′ _{R ′} , z ′ _{R ′} ) by the function V _{R ′} and proves the calculation result. To the device 434. The communication at this time is shown as communication 431 in FIG. The proof verification apparatus 434 determines whether V _{R ′} (X ′, a ′ _{R ′} , e ′ _{R ′} , z ′ _{R ′} ) = 1 holds.

The proof verification device 434 determines that when all the above determinations are satisfied, that is, Hash (X, a _R , X ′, a ′ _{R ′} ) = e _R ∨ e ′ _{R ′} , V _R (X, a _{When R 1} , e _R , z _R ) = 1 and V _{R ′} (X ′, a ′ _{R ′} , e ′ _{R ′} , z ′ _{R ′} ) = 1 are all satisfied, the verification result is “1”. It outputs as 435. In other cases, the proof verification apparatus 434 outputs “0” as the verification result 435. The above “1” represents acceptance of the proof P _{R∨R ′} . Also, the above “0” indicates that the proof _{PR PR '} is not accepted.

According to the second embodiment, the amount of communication transmitted from the verification device 402 to the certification device 401 can be reduced, and the amount of communication and the amount of calculation can be suppressed. For example, in the related art 1 shown in FIG. 4, 2t c [1, i] and c [2, i] are transmitted from the verification device to the certification device. On the other hand, in the second embodiment, the verification device 402 only transmits the certification PR _′ to the certification device 401. Thus, according to the present invention, it is possible to reduce the amount of communication and the amount of calculation.

  In the second embodiment, the non-dialogue proof receiving means and the non-dialogue proof acceptance non-acceptance judging means included in the proof device are realized by the second relationship proof verification device 423 of the proof device 402. Further, the common input receiving means, random tape input means, evidence knowledge non-dialogue proof generation means, and non-dialogue proof transmission means included in the proof device are realized by a proof generation device 425 of the proof device 402.

  The common input input means, random tape input means, common input generation means, evidence knowledge non-dialogue proof generation means, and non-dialogue proof transmission means included in the verification device are realized by the second relation proof generation device 417 of the verification device 402. Is done. Further, the non-interactive certificate receiving means and the determining means provided in the verification device are realized by the proof verification device 434 of the verification device 402.

  According to the present invention, if there is a special honest verifier zero knowledge dialogue proof, it is possible to perform a repudiation zero knowledge dialogue proof. Can be increased.

  In addition, according to the present invention, since any verification device cannot prove the fact that the verification device communicated with the verification device, efficient non-repudiation signature, non-repudiation verification, and receipt-free electronic voting are realized. can do.

  In each of the above embodiments, the proving device and the verification device may be realized by a computer that operates according to a program.

  In each of the above embodiments, the case where the proof is accepted is represented by “1”, and the case where the proof is not accepted is represented by “0”.

  Examples of the second embodiment will be described below. FIG. 3 is an explanatory diagram showing an example of the second mode of the present invention. In the present embodiment, the case where the same discrete logarithmic relationship is used as both the first relationship R and the second relationship R ′ will be described as an example. The realization of the present embodiment is a non-repudiation authentication. Here, the certification device is authenticated by the verification device.

  A verification apparatus 501 shown in FIG. 3 corresponds to the verification apparatus 401 in the second embodiment, and a verification apparatus 502 in FIG. 3 corresponds to the verification apparatus 402 in the second embodiment.

  The proof device 501 is a non-interactive knowledge proof verification device 523 (hereinafter referred to as a second relationship proof verification device 523) related to the second relationship, non-interactive evidence that satisfies the first relationship, A proof generation device 525 (hereinafter referred to as a proof generation device 525) for knowledge of any of the evidences satisfying the second relationship. These correspond to the proof verification device 423 and the proof generation device 425 in the second embodiment, respectively.

  The verification device 502 includes a non-interactive knowledge proof generation device 517 (hereinafter referred to as a second relationship proof generation device 517) related to the second relationship, and non-interactive knowledge satisfying the first relationship, A knowledge proof verification device 534 (hereinafter, referred to as a proof verification device 534) of knowledge satisfying the second relationship. These correspond to the second relationship proof generation device 417 and the proof verification device 434 in the second embodiment, respectively.

  Also, hash function calculation devices 510 and 511 shown in FIG. 3 correspond to the hash function calculation devices 410 and 411 in the second embodiment, respectively.

In FIG. 3, the common input X is indicated by reference numeral 512. Also, the evidence W is indicated by using a reference numeral 513. Further, the first random tape _RP is indicated by using a reference numeral 514. Further, the second random tape R ′ _P is indicated by reference numeral 515. Further, the third random tape R _V and R ′ _V are indicated by using reference numeral 516.

In this embodiment, the same discrete logarithmic relationship is used for both the first relationship R and the second relationship R ′. Therefore, the first proof commitment generation device 403 and the second proof commitment generation device 406 in the second embodiment are realized by the same device. This device is a proof commitment generation device 503 (hereinafter referred to as a proof commitment generation device 503) of the special honest verifier zero knowledge dialogue proof relating to the discrete logarithmic relationship shown in FIG. The proof commitment generation device 503 generates a proof commitment by the function A _R.

Similarly, in the present example, the first response generation device 404 and the second response generation device 407 in the second embodiment are realized by the same device. This apparatus is a special honest verifier zero knowledge dialogue proof response generation apparatus 504 (hereinafter referred to as a response generation apparatus 504) related to the relationship of discrete logarithms shown in FIG. The response generation device 504 generates a response with the function Z _R.

Similarly, in the present embodiment, the first dialog proof verification device 405 and the second dialog proof verification device 408 in the second embodiment are realized by the same device. This device is a special honest verifier zero knowledge dialogue proof verification device 505 (hereinafter referred to as a dialogue proof verification device 505) related to the relationship of discrete logarithms shown in FIG. Interactive proof verification apparatus 505, by the function V _R, to derive the verification result.

Moreover, the special honest verifier zero knowledge dialogue proof simulation device 509 (hereinafter referred to as a simulation device 509) related to the discrete logarithmic relationship shown in FIG. 3 corresponds to the second relationship simulation device 409 in the second embodiment. To do. The simulator 509 uses the function S _{R ′} to generate a proof commitment and a response.

Hereinafter, the function A _R , the function Z _R , the function V _R , and the function S _{R ′} in this embodiment will be described. Although not used in this embodiment, as a supplement, it is also explained the function E _R in the prior art 2.

[Function A _R ]
Input is X, W, and a random tape R _P. Then, a random x ′ ∈ Z / qZ is generated from R _P , and a _R is output with a _R = y ′ = g ^{x ′} .

[Function Z _R ]
Inputs are X, W, random tape R _P , and e _R = c. Then, z _R = r = xc + x ′ mod q is calculated and z _R is output.

[Function V _R ]
Inputs are X, a _R , e _R , and z _R. If g ^r = y ^c y 'is satisfied, 1 is output, and if not, 0 is output.

[Function S _{R '} ]
Inputs are X, e _R = c, and random tape R _S. Then, a random z _R = r ∈ Z / qZ is generated from R _S , and a _R = y ′ = g ^r y ^-c is generated. Then, (a _R , z _R ) is output.

[Function E _R ]
The inputs are a _R , e _R = c, z _R = r, e ′ _R = c ′, z ′ _R = r ′. Then, W = x = (r−r ′) / (c′−c) mod q is calculated and W is output.

In the above description of the function, the input random tape is represented as R _S or the like, but this is merely a convenient representation of the input random tape.

  Next, an operation of non-repudiation authentication by the proving device and the verification device in the present embodiment will be described.

First, the common input X with (X, W) ∈ R, the evidence W, the first random tape R _P , and the second random tape R ′ _P are input to the proof generation device 525 of the proof device 501.

Subsequently, the common input X and the third random tapes R _V and R ′ _V are input to the second relationship proof generation device 517 of the verification device 502.

Next, the second relationship proof generation apparatus 517, as described below, to generate a proof P _R of the non-interactive knowledge about the relationship of the discrete logarithm.

The second relationship proof generation device 517 generates X ′, W ′ such that (X ′, W ′) ∈ R ′ uniformly and randomly using R ′ _V of the third random tape.

Next, the second relationship proof generation device 517 transmits the common input X ′, the evidence W ′, and R _V among the third random tapes to the proof commitment generation device 503. Proof commitment generation apparatus 503, by the function _{A R, α R = A R} (X ', W', R V) as to generate a proof commitment alpha _R. Then, the proof commitment generation device 503 transmits the proof commitment α _R to the second relationship proof generation device 517. The communication at this time is shown as communication 518 in FIG.

Next, the second relationship proof generation device 517 transmits the common input X ′ and the proof commitment α _R to the hash function calculation device 511. The hash function calculation device 511 calculates a hash value as ε _R = Hash (X ′, α _R ). The hash function calculation device 511 transmits the hash value ε _R to the second relationship proof generation device 517. The communication at this time is shown as communication 519 in FIG.

Next, the second relationship proof generation device 517 transmits the common input X ′, the evidence W ′, the hash value ε _R , and R _V of the third random tape to the response generation device 504. Here, the hash value ε _R is transmitted as a challenge value. Response generation apparatus 504, by the function _{Z R, ζ R = Z R} (X ', W', ε R, R V) as to generate a response zeta _R. The response generation device 504 transmits the response ζ _R to the second relationship proof generation device 517. The communication at this time is shown as communication 520 in FIG.

Second relationship proof generation apparatus 517, the certificate P _R of the non-interactive knowledge about the relationship of the discrete logarithm _{(X ', ε R, ζ} R) and. The second relationship proof generation device 517 transmits the proof P _R = (X ′, ε _R , ζ _R ) generated as described above to the second relationship proof verification device 523 (communication 521 shown in FIG. 3). .

Incidentally, the second relationship proof verification apparatus 523 waits for the certificate P _R is transmitted, by the communication 521, = second relationship proof generation apparatus 517 certificate from _{P R (X ', ε R} , ζ R ).

Second relationship proof verification apparatus 523 of the proving apparatus 501, as described below, to verify the certificate P _R of the non-interactive knowledge about the relationship of the discrete logarithm.

The second relationship proof verification device 523 transmits the common input X ′ and the proof commitment α _R to the hash function calculation device 510. The hash function calculation device 510 calculates a hash value as ε ′ _R = Hash (X ′, α _R ). The hash function calculation device 510 transmits the hash value ε ′ _R to the second relationship proof verification device 523. The communication at this time is shown as communication 522 in FIG.

The second relationship proof verification device 523 transmits the common input X ′, the proof commitment α _R , the hash value ε ′ _R , and the response ζ _R to the dialogue proof verification device 505. Here, the hash value ε ′ _R is transmitted as a challenge value. The dialogue proof verification device 505 derives the calculation result of V _R (X ′, α _R , ε ′ _R , ζ _R ) by the function V _R and transmits the calculation result to the second relationship proof verification device 523. The communication at this time is shown as communication 524 in FIG.

The second relationship proof verification device 523 determines whether V _R (X ′, α _R , ε ′ _R , ζ _R ) = 1 holds. If not, the proving device 501 is stopped. Further, if it is established, the proving apparatus 501 performs the following operation. _{That, V R (X ', α} R, ε' R, ζ R) = long as it 1 is established, the certificate P _R and acceptance, and not accept the certificate P _R if not satisfied.

The proof generation device 525 of the proof device 501 performs non-interactive knowledge of knowledge about either evidence of evidence satisfying a discrete logarithmic relationship with respect to X or evidence satisfying a discrete logarithmic relationship with respect to X ′ as follows: Proof of knowledge P _{R (X) ∨R (X ')} is generated.

The proof generation device 525 generates a random number e ′ _R using the second random tape R ′ _P, and sets this as a challenge value.

Next, the proof generation device 525 transmits the common input X ′, the challenge value e ′ _R , and the second random tape R ′ _P to the simulation device 509, and the proof commitment a ′ _R and the response z are transmitted to the simulation device 509. 'Generate _R. The simulation device 509 derives (a ′ _R , z ′ _R ) = S _{R ′} (X ′, e ′ _R , R ′ _P ) by the function S _{R ′} , and proves the commitment a ′ _R and the response z ′ _R. Is transmitted to the proof generation device 525. The communication at this time is shown as communication 526 in FIG.

Next, the proof generation device 525 transmits the common input X 1, the evidence W 2, and the first random tape _RP to the proof commitment generation device 503. Proof commitment generation apparatus 503, by the function _{A R, a R = A R} (X, W, R P) as to generate a proof commitment a _R, and transmits the certificate generation unit 525. The communication at this time is shown as communication 527 in FIG.

Next, the proof generation device 525 transmits the common input X, the proof commitment a _R , the common input X ′, and the proof commitment a ′ _R to the hash function calculation device 510. The hash function calculation device 510 calculates a hash value e as e = Hash (X, a _R , X ′, a ′ _R ), and transmits the hash value to the proof generation device 525. The communication at this time is shown as communication 528 in FIG.

Next, the proof generation device 525 calculates the challenge value e _R as e _R = e∨e ′ _R. The proof generation device 525 transmits the common input X, the evidence W, the challenge value e _R , and the first random tape _RP to the response generation device 504 to generate a response z _R. Response generation apparatus 504, by the function _{Z R, z R = Z R} (X, W, e R, R P) as to generate a response z _R, and transmits a response z _R to proof generation apparatus 525. The communication at this time is shown as communication 529 in FIG.

The proof generation device 525 proves the non-interactive knowledge of the knowledge about the evidence P _{R (X) ∨R} , either the evidence satisfying the discrete logarithmic relationship with respect to X or the evidence satisfying the discrete logarithmic relationship with respect to X ′. _{Let (X ′)} be (a _R , e _R , z _R , a ′ _R , e ′ _R , z ′ _R ). The proof generation device 525 generates the proof _{PR (X) ∨R (X ′)} = (a _R , e _R , z _R , a ′ _R , e ′ _R , z ′ _R ) generated as described above, It transmits to the proof verification apparatus 534 of the verification apparatus 502 (communication 529 shown in FIG. 3).

The proof verification device 534 transmits the common input X, the proof commitment a _R , the common input X ′, and the proof commitment a ′ _R to the hash function calculation device 511 to calculate a hash value. The hash function calculation device 511 derives the calculation result of Hash (X, a _R , X ′, a ′ _R ), and transmits the calculation result (hash value) to the proof verification device 534. The communication at this time is shown as communication 530 in FIG. Then, the proof verification apparatus 534 determines whether or not the calculation result of Hash (X, a _R , X ′, a ′ _R ) is equal to e _R ∨ e ′ _R.

Next, the proof verification device 534 transmits the common input X, the proof commitment a _R , the challenge value e _R , and the response z _R to the dialog proof verification device 505. The dialogue proof verification apparatus 505 derives the calculation result of V _R (X, a _R , e _R , z _R ) by the function V _R and transmits the calculation result to the proof verification apparatus 534. The communication at this time is shown as communication 532 in FIG. The certification verification device 534 determines whether V _R (X, a _R , e _R , z _R ) = 1 is satisfied.

Next, the proof verification device 534 transmits the common input X ′, the proof commitment a ′ _R , the challenge value e ′ _R , and the response z ′ _R to the dialog proof verification device 505. The dialogue proof verification apparatus 505 derives the calculation result of V _R (X ′, a ′ _R , e ′ _R , z ′ _R ) by the function V _R and transmits the calculation result to the proof verification apparatus 534. The communication at this time is shown as communication 531 in FIG. The proof verification apparatus 534 determines whether V _R (X ′, a ′ _R , e ′ _R , z ′ _R ) = 1 holds.

The proof verification device 534 determines that all of the above determinations are satisfied, that is, Hash (X, a _R , X ′, a ′ _R ) = e _R ∨ e ′ _R , V _R (X, a _R , When all of e _R , z _R ) = 1 and V _R (X ′, a ′ _R , e ′ _R , z ′ _R ) = 1 are satisfied, “1” is output as the verification result 535. In other cases, the certification verification apparatus 534 outputs “0” as the verification result 535. The above “1” indicates that the proof _{PR (X) ∨R (X ′)} is accepted. In addition, the above “0” indicates that the proof _{PR (X) ∨R (X ′)} is not accepted.

  The present invention is applicable to non-repudiation zero knowledge dialogue proofs used for non-repudiation signature non-repudiation protocol, non-repudiation signature confirmation protocol, non-repudiation authentication, and the like.

  The present invention can also be applied to non-repudiation authentication using hardware with a small computational power such as a smart card. When performing authentication with high privacy protection such as non-repudiation proof by a conventional method using a smart card or the like, it takes a lot of time due to the low computational power of the smart card or the like. By applying the present invention, authentication with high privacy protection can be realized with a calculation amount about twice as high as that of authentication with low privacy protection generally used.

  The present invention can also be used when a server or the like performs many privacy-protective authentications. In general, when a server or the like performs a large amount of authentication, even if the time and the amount of communication required for each authentication are not so large, if a large amount of authentication is performed, the amount thereof becomes enormous as a whole. If the present invention is used, even if authentication with high privacy protection is performed, the calculation amount and communication amount of the server can be kept small.

  The present invention can also be used when performing zero knowledge proof with high privacy protection. There are many applications that are convenient when high privacy protection is satisfied, such as authentication, electronic voting, non-repudiation signature, and verifier-designated signature. Many special honest verifier zero-knowledge dialogue proofs corresponding to these applications have been proposed. By applying the present invention to these special honest verifier zero knowledge dialogue proofs, it is possible to easily realize electronic voting, non-repudiation signature, verifier designated signature, etc. that satisfy high privacy protection.

DESCRIPTION OF SYMBOLS 301 Proving device 302 Verification device 303 Proof commitment generation device 304 Response generation device 305 Dialogue proof verification device 310, 311 Hash function calculation device 312 Challenge value commitment generation device 324 Challenge value commitment verification device 330 Proof generation device 340 Proof verification device

Claims (4)

A verification device communicably connected to the verification device,
Communicating with a first proof commitment generator for generating a proof commitment of a special honest verifier zero knowledge dialog proof of the first relationship based on common input and evidence satisfying a predetermined first relationship and a random tape Connected and possible
Communicatively connected to a first response generator for generating a special honest verifier zero knowledge dialogue proof response for the first relationship based on the common input and evidence for the first relationship, the random tape and the challenge value;
A second dialog that outputs a signal representing acceptance or non-acceptance of a special honest verifier zero-knowledge dialogue proof regarding the second relationship based on the common input, proof commitment, challenge value, and response regarding the second relationship Communicatively connected to the proof verification device,
Communicatively connected to a simulator that generates a proof commitment and response for the second relationship based on the common input, challenge value, and random tape for the second relationship;
It is connected to a hash function computing device that performs hash function computation,
A common input satisfying a predetermined first relation and a receiving means such as a common input to which evidence is input; and
A random tape input means for inputting the first random tape and the second random tape;
Non-dialogue proof receiving means for receiving a non-dialogue proof of common input related to the second relationship and knowledge of evidence corresponding to the common input from the verification device;
Non-dialog proof acceptance non-acceptance judging means for judging whether or not to accept the non-dialog proof based on a result of communication with the hash function calculation device and the second dialogue proof verification device using the non-dialog proof. ,
Using the first random tape, the second random tape, the common input and evidence satisfying the first relationship, and the common input included in the non-interactive proof, the simulation device, the first proof commitment generation device, Knowledge of evidence for common input regarding the first relationship or knowledge of evidence for common input regarding the second relationship by communicating with the hash function calculation device and the first response generation device Evidence knowledge non-dialogue proof generation means for generating a non-dialogue proof of knowledge,
A proof device comprising: non-dialogue proof transmission means for transmitting a non-dialogue proof of knowledge generated by the evidence knowledge non-dialogue proof generation means to the verification device. The non-interactive proof receiving means
Receiving a non-interactive proof including a common input, proof commitment and response for the second relationship from the verification device;
Non-dialogue proof acceptance non-acceptance judgment means,
The common input and proof commitment related to the second relationship included in the non-interactive proof are transmitted to the hash function calculation device, and the hash value that becomes the challenge value corresponding to the common input and proof commitment related to the second relationship is calculated. ,
The challenge value and the common input, the proof commitment, and the response related to the second relationship included in the non-dialogue proof are transmitted to the second dialogue proof verification device, and the second dialogue proof verification device outputs an output signal. , Determine whether to accept the non-dialogue proof,
Evidence knowledge non-dialogue proof generation means
Generate a challenge value for the second relationship with the second random tape,
Send a common input for the second relationship, a challenge value for the second relationship, and a second random tape to the simulator to generate a proof commitment and response for the second relationship;
Send the common input and evidence satisfying the first relationship and the first random tape to the first proof commitment generating device to generate a proof commitment for the first relationship,
A common input and proof commitment related to the first relationship, a common input related to the second relationship, and a proof commitment related to the second relationship generated by the simulation device are transmitted to the calculation device of the hash function, and the first relationship A hash value corresponding to the common input and proof commitment related to the second relationship and the common input and proof commitment related to
Determining a challenge value for the first relationship based on the hash value and the challenge value for the second relationship;
Sending the common input and evidence satisfying the first relationship, the first random tape, and the challenge value related to the first relationship to the first response generation device to generate a response related to the first relationship;
The proof commitment, challenge value, and response for the first relationship, the challenge value for the second relationship, and the proof commitment and response for the second relationship generated by the simulator are non-dialogue proofs of knowledge. 1. The proving device according to 1. A verification device that is communicably connected to the certification device according to claim 1 or 2,
A first dialog that outputs a signal indicating acceptance or non-acceptance of a special honest verifier zero-knowledge dialogue proof regarding the first relationship based on the common input, proof commitment, challenge value, and response regarding the first relationship Communicatively connected to the proof verification device,
A second dialog that outputs a signal representing acceptance or non-acceptance of a special honest verifier zero-knowledge dialogue proof regarding the second relationship based on the common input, proof commitment, challenge value, and response regarding the second relationship Communicatively connected to the proof verification device,
Communicatively connected to a second proof commitment generator for generating a proof commitment for a special honest verifier zero knowledge dialogue proof for the second relationship based on the common input and evidence for the second relationship and a random tape,
Communicatively connected to a second response generator for generating a special honest verifier zero knowledge dialogue proof response for the second relationship based on the common input and evidence for the second relationship, the random tape and the challenge value;
It is connected to a hash function computing device that performs hash function computation,
A common input input means for inputting a common input related to the first relationship;
Random tape input means in which random tape R _V and random tape R ′ _V are input as a third random tape;
Common input and the like generating means for generating the common input and evidence satisfying the second relationship from the random tape R ′ _{V of} the third random tape,
A common input and evidence satisfy a second relationship that is generated to the common input or the like generating means, a third by using a random tape R _V of the random tape, said second proof commitment generation apparatus, the second Evidence knowledge non-dialogue proof generation means for generating a non-dialogue proof of knowledge of evidence that satisfies the second relationship with the common input by communicating with a response generation device and the hash function calculation device; ,
Non-dialog proof transmitting means for transmitting the non-dialog proof of knowledge generated by the evidence knowledge non-dialog proof generating means to a proving device;
Non-dialogue proof receiving means for receiving from the proof device a non-dialogue proof of knowledge that there is either knowledge of evidence for the common input related to the first relationship or knowledge of evidence for the common input related to the second relationship When,
Using the common input related to the second relationship, the common input related to the first relationship input to the common input input means, and the non-dialogue proof received by the non-dialogue proof receiving means, By communicating with the second dialog proof verification device and the hash function calculation device, it is determined whether or not the non-dialog proof received by the non-dialog proof receiving means is received, and the determination result is output. And a verification device. Evidence knowledge non-dialogue proof generation means
A common input and evidence satisfy a second relationship, and a random tape R _V of the third random tape sent to the second proof commitment generation apparatus, to generate a proof commitment to the second relationship,
Sending a common input relating to a second relationship and a proof commitment relating to the second relationship to a calculation device of a hash function, causing a hash value to be a challenge value corresponding to the common input and the proof commitment to be calculated;
Send the common input and evidence satisfying the second relationship, the random tape R _V and the challenge value to the second response generation device to generate a response regarding the second relationship,
Let the common input, proof commitment, and response for the second relationship be a non-dialogue proof of knowledge,
The non-interactive proof receiving means
Receiving a non-interactive proof including a proof commitment, challenge value, and response for the first relationship and a proof commitment, challenge value, and response for the second relationship from the proof device;
The judging means is
The common input related to the first relationship input to the common input input means and the proof commitment, challenge value, and response regarding the first relationship included in the non-dialogue proof are transmitted to the first dialog proof verification device, Receiving a signal output from one dialogue proof verification device;
The common input related to the second relationship and the proof commitment, the challenge value, and the response related to the second relationship included in the non-dialogue proof are transmitted to the second dialog proof verification device and output by the second dialog proof verification device. Receive the signal,
The common input and proof commitment for the first relationship and the common input and proof commitment for the second relationship are sent to the hash function computing device, and the common input and proof commitment for the first relationship and the common for the second relationship A hash value corresponding to the input and proof commitment is calculated, and a predetermined relationship is established between the hash value and the challenge value related to the first relationship and the challenge value related to the second relationship included in the non-dialogue proof. Whether or not
The verification device according to claim 3, wherein it is determined whether or not a non-dialogue proof is accepted based on a result of the determination and a signal received from the first dialogue proof verification device and the second dialogue proof verification device.

Images