JP6563857B2 - Commitment system, common reference information generation device, commit generation device, commit reception device, commitment method, program - Google Patents

Description

  The present invention relates to information security technology, and more particularly to a commitment to maintain high security even in an environment in which a plurality of cryptographic protocols are incorporated and operate simultaneously.

  A cryptographic commitment is an electronic “sealing hand”. The commitment method is a protocol performed between a committing sender (committer) and a commitment receiving receiver. The sender deposits (commits) information to the receiver in the commit (sealing) phase. At this time, the receiver cannot know the contents of the deposited information (this property is called confidentiality). Next, the sender discloses the information concealed in the decommitment (opening) phase in a form that is convincing to the receiver, but cannot disclose the information different from the information deposited in the commit phase to satisfy the receiver (this The property is called restraint). Commitment must basically satisfy such confidentiality and binding.

  An immediate application of commitment is electronic janken or coin throwing. Of course, it can also be a seal used for shogi or samurai. I've given some examples that you can easily think of, but the range of practical applications is far wider.

  Since commitment is the most basic cryptographic protocol, it is frequently used in higher-level cryptographic protocols. In recent years, commitments have been increasingly used in more complex combinations to bring cryptographic protocols closer to the real environment. However, in a complex combination, the commitment made with the classic cryptographic security model will not be able to satisfy both confidentiality and constraint at the same time.

  A general-purpose combinable commitment is a commitment designed to satisfy confidentiality and restraint even when commitments are used in such a complex combination. See).

 In addition to the amount of calculation, traffic, and number of communication, the commitment method is CRS reuse type, adaptive security, information discard type / information discard unnecessary type, interactive / non-interactive type, discrete logarithm (DL) type It is also necessary to consider. Each will be described below.

<CRS reuse type>
It is known that in order to be able to construct a universal combinable commitment, it is necessary to have a common reference string (hereinafter referred to as CRS) that can be accessed by both the sender and receiver (made by a third party). (See Non-Patent Document 2). Due to technical problems, this CRS is divided into a case where it must be disposable for each commit (that is, a case where a new CRS is required for the number of commits) and a case where the same CRS can be reused without being disposable. Of course, the “CRS reuse type” commitment method that can use CRS all the time is more practical.

<Adaptive safety / static safety>
When considering general joint security, whether adaptive security is satisfied is an important measure. A protocol is adaptive security if it can satisfy security (general-purpose combination) even if the attacker is free to infiltrate the protocol participants' devices and steal data during the protocol. Satisfy. Adaptive safety is usually very difficult to achieve.

On the other hand, the security when the participant who is attacked is determined in advance is referred to as static security. Static safety is a lower level of safety than adaptive safety.
<Information disposal type / Information disposal unnecessary type>
In the universal combinable commitment, there are a method in which the sender and receiver cannot guarantee the security without discarding the data during or after the protocol, and a method in which the safety can be ensured without discarding. . Of course, the latter “information disposal-free type” is preferable because of its high safety.

<Interactive and non-interactive>
In particular, a scheme in which a commitment is completed simply by sending from a sender to a receiver is called “non-interactive”. “Non-interactive” is more practical.

<Discrete logarithm (DL) type>
It is desirable that the commitment can be implemented on a cyclic group (such that the discrete logarithm (DL) problem seems to hold) for reasons such as reducing security parameters or simplifying the structure. In fact, the commitments described in Non-Patent Document 3 and Non-Patent Document 4 that are considered to be the most efficient at present are all of the DL type.

  Non-Patent Document 3, Non-Patent Document 4, Non-Patent Document 5, Non-Patent Document 6, Non-Patent Document 7, Non-Patent Document 8, and the like are efficient CRS reusable, adaptive and safe universally joinable commitments. .

Ran Canetti, “Universally composable security: A new paradigm for cryptograpic protocols”, Technical report, Cryptology ePrint Archive, Report 2000/067, 2005. Preliminary version appeared in FOCS'01. R. Canetti and M. Fischlin, “Universally composable commitments”, In Joe Kilian, editor, Advances in Cryptology-CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pages 19-40, Springer, Heidelberg, 2001. Yehuda Lindell, “Highly-efficient universally-composable commitments based on the DDH assumption”, In Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pages 446-466, Springer, Heidelberg, 2011. full version is available at Cryptology ePrint Archive http://eprint.iacr.org/2011/180. Olivier Blazy, Celine Chevalier, David Pointcheval and Damien Vergnaud, “Analysis and improvement of lindell's uc-secure commitment schemes”, In Michael J. Jacobson, Jr., Michael E. Locasto, Payman Mohassel and Reihaneh Safavi-Naini, editors, ACNS 2013, volume 7954 of Lecture Notes in Computer Science, pages 534-551, Springer, Heidelberg, 2013. Ivan Damgard and Jesper Buus Nielsen, “Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor”, In Moti Yung, editor, CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 581-596, Springer, Heidelberg, 2002. The full version is available at http://www.brics.dk/RS/01/41/. Ivan Damgard and Jens Groth, “Non-interactive and reusable non-malleable commitment schemes”, In STOC 2003, pages 426-437, ACM, 2003. Marc Fischlin, Benoit Libert, and Mark Manulis, “Non-interactive and re-usable universally composable string commitments with adaptive security”, In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 468-485, Springer, Heidelberg, 2011. Eiichiro Fujisaki, “All-But-Many encryption-A new framework for fully-equipped UC commitments”, In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014 (2), volume 8874 of Lecture Notes in Computer Science, pages 426-447 , Springer, Heidelberg, 2014.

However, since Non-Patent Document 5, Non-Patent Document 6, and Non-Patent Document 8 have the prime factorization type problem as the basis of safety, the security parameter becomes large, and the non-patent document that sets the basis of safety as the DL type problem. 3. Compared with Non-Patent Document 4, the amount of communication and the amount of calculation are inferior. Non-Patent Document 7 bases safety on the DL type problem, but because it is configured on symmetric pairing (Reference Non-Patent Document 1), the security parameter length is the same as the prime factorization type, which is also inefficient. .
(Reference Non-Patent Document 1: David Freeman, Michael Scott and Edlyn Teske, “A taxonomy of pairing-friendly elliptic curves”, JOC, 23 (2), pages 224-280, 2010.)
In addition, Non-Patent Document 3, Non-Patent Document 4, and Non-Patent Document 7 are information discard types, and Non-Patent Document 5, Non-Patent Document 6, and Non-Patent Document 8 are information discard-free types. In addition, Non-Patent Document 4, Non-Patent Document 5, and Non-Patent Document 6 require a three-way communication with commitment, Non-Patent Document 3 requires a five-way communication, and Non-Patent Document 7 and Non-Patent Document 8 are non-interactive.

  As described above, each of the methods of Non-Patent Document 3, Non-Patent Document 4, Non-Patent Document 5, Non-Patent Document 6, Non-Patent Document 7, and Non-Patent Document 8 has advantages and disadvantages. However, when considering the mounting aspect, the method of Non-Patent Document 4 is the most efficient conventional method in terms of communication amount and calculation amount.

  Therefore, an object of the present invention is to provide a CRS reusable type, adaptively secure, and universally connectable commitment system that can reduce the common parameter length, communication amount, and calculation amount.

  Also, in some cases, the safety required for a universal combinable commitment system is not adaptive security, but static safety is sufficient.

  Therefore, an object of the present invention is to provide a CRS reusable and statically safe universally connectable commitment system that can reduce the common parameter length, communication amount, and calculation amount.

One aspect of the present invention is a commitment system including a common reference information generation device, a commit generation device, and a commit reception device, wherein κ is a security parameter, and λ _m (·) and λ _c (·) are κ Function, H: {0,1} ^* → {0,1} ^λ_m is a hash function that is difficult to collide, K is a key generation algorithm for public key cryptography PKE, E is an encryption algorithm for public key cryptography PKE, and Gen ^tc is dropped Key generation algorithm for Commitment Commit TCOM, encryption algorithm for Commitment TCOM with Com ^tc dropped, w ∈ COIN _{pk ^ enc} satisfying L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) Is a language defined from public key cryptography PKE (where COIN _{pk ^ enc} is a random number space), and P _Σ ^com is a language on the language L ^enc The first message generation algorithm bears protocol sigma, as validation algorithm Sigma protocol sigma on P _sigma second message generation algorithm sigma protocol sigma of the linguistic ^{L enc ans,} V _Σ ^vrfy language ^{L enc,} the common reference information The generation device uses the key generation algorithm K and Gen ^tc from 1 ^κ , and sets of two public keys and secret keys (pk ^enc , sk ^enc ) ← K (1 ^κ ), (pk ^tc , sk ^tc ) ← Gen ^tc (1 ^κ ) is generated, and the secret key sk ^enc and sk ^tc are discarded, and the public key pk ^enc and pk ^tc and the hash function H are combined into crs = (pk ^enc , pk ^tc, and a CRS generator for generating an H) as a common reference information, the commit generation device, the random number w ← COIN _{pk ^ e c} (however, COIN _{pk ^ enc} random number space) generate, by using the public key ^{pk enc} and the encryption algorithm E, confidential information m∈MSP _{pk ^ enc} (However, MSP _{pk ^ enc} is the plaintext space) The secret information encryption unit calculating the encrypted secret information CT = E _{pk ^ enc} (m, w) and the first message generation algorithm P _Σ ^com , and the secret information m and the encrypted secret information A first message calculation unit for calculating a first message (α, ξ) ← P _Σ ^com ((m, CT), w) from a set (m, CT) of information CT and the random number w; Quadruple (sid, ssid, C, R) (where sid is the session ID, ssid is the sub-session ID, C is the ID of the commit generating device, and R is the ID of the commit receiving device) ) Using the secret information m, the encrypted secret information CT, and the first element α of the first message, the hash value φ = H (sid, ssid, C, R, m, CT, α) A hash value calculation unit that calculates the random number r _tc ← COIN _{pk ^ tc} (where COIN _{pk ^ tc} is a random number space), and the hash is calculated using the encryption algorithm Com ^tc and the public key pk ^tc A hash value encryption unit for calculating an encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ; r _tc ) from the value φ, the four sets (sid, ssid, C, R), and the encrypted hash a first commit unit that transmits the value Ψ in the commit receiving apparatus, by using the second message generation algorithm P _sigma ^ans, the confidential information m and the encrypted pre confidential information CT pairs (m, CT), prior to Random number w, the second element xi] of the first message, the second message from the random epsilon received from committing the receiving device ^{_{γ = P Σ ans ((m}} , CT), w, ξ, ε) a second message to calculate the A calculation unit; an erasure unit that erases the random number w and the second element ξ of the first message; a second commit unit that transmits the encrypted confidential information CT to the commit receiver; and the confidential information m. A disclosure unit that transmits a set of four elements (m, α, γ, r _tc ) including the first element α, the second message γ, and the random number r _{tc of} the first message to the commit receiver as disclosure information. The commit reception device verifies the quadruplet (sid, ssid, C, R) received from the commit generation device, and if there is no problem, generates the random number ε ← {0, 1} ^λ_c , Random number ε A random number generation unit for transmitting device, the received from the commit generator quadruplet (sid, ssid, C, R ), the encrypted pre confidential information CT, the disclosure information _{(m, α, γ, r} tc ) And the hash function H, a hash value calculator that calculates a hash value φ ′ = H (sid, ssid, C, R, m, CT, α), the encryption algorithm Com ^tc, and the verification algorithm Using V _Σ ^vrfy, from the hash value φ ′, the disclosed information (m, α, γ, r _tc ), the encrypted confidential information CT, and the random number ε, Com ^tc _{pk ^ tc} (φ ′; r _tc ) And V _Σ ^vrfy ((m, CT), (α, ε, γ)), and the encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy (( m, CT), (α, ε, γ)) = 1 Including an opening portion.

One aspect of the present invention is a commitment system including a common reference information generation device, a commit generation device, and a commit reception device, wherein κ is a security parameter, and λ _m (·) and λ _c (·) are κ Function, H: {0,1} ^* → {0,1} ^λ_m is a hash function that is difficult to collide, K is a key generation algorithm for public key cryptography PKE, E is an encryption algorithm for public key cryptography PKE, and Gen ^tc is dropped Key generation algorithm for Commitment Commit TCOM, encryption algorithm for Commitment TCOM with Com ^tc dropped, w ∈ COIN _{pk ^ enc} satisfying L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) Is a language defined from public key cryptography PKE (where COIN _{pk ^ enc} is a random number space), and P _Σ ^com is a language on the language L ^enc The first message generation algorithm bears protocol sigma, as validation algorithm Sigma protocol sigma on P _sigma second message generation algorithm sigma protocol sigma of the linguistic ^{L enc ans,} V _Σ ^vrfy language ^{L enc,} the common reference information The generation device uses the key generation algorithm K and Gen ^tc from 1 ^κ , and sets of two public keys and secret keys (pk ^enc , sk ^enc ) ← K (1 ^κ ), (pk ^tc , sk ^tc ) ← Gen ^tc (1 ^κ ) is generated, and the secret key sk ^enc and sk ^tc are discarded, and the public key pk ^enc and pk ^tc and the hash function H are combined into crs = (pk ^enc , pk ^tc, and a CRS generator for generating an H) as a common reference information, the commit generation device, the random number w ← COIN _{pk ^ e c} (however, COIN _{pk ^ enc} random number space) generate, by using the public key ^{pk enc} and the encryption algorithm E, confidential information m∈MSP _{pk ^ enc} (However, MSP _{pk ^ enc} is the plaintext space) Secret information encryption unit for calculating encrypted secret information CT = E _{pk ^ enc} (m, w) and quadruple (sid, ssid, C, R) (where sid is the session ID and ssid is the sub A session ID, C is an ID of the commit generating device, R is a finite bit string indicating the ID of the commit receiving device), a second commit unit that transmits the encrypted confidential information CT to the commit receiving device, Using a message generation algorithm P _Σ ^com , the first message (α, ξ) from the set (m, CT) of the secret information m and the encrypted secret information CT and the random number w ^{_{) ← P Σ com ((m}} , CT), using a first message calculation unit for calculating a w), the said hash function H to (sid, ssid, C, R ), the confidential information m, the cryptographic Hidden secret information CT, a hash value calculator for calculating a hash value φ = H (sid, ssid, C, R, m, CT, α) from the first element α of the first message, and a random number r _tc ← COIN _{pk ^ tc} (where COIN _{pk ^ tc} is a random number space), and using the encryption algorithm Com ^tc and the public key pk ^tc , an encrypted hash value Ψ = Com ^tc _{pk ^} using the hash value encryption section for calculating a; _{(r tc} φ), a first disclosure unit that transmits the cryptographic haze hash value Ψ in the commit receiving device, the second message generation algorithm P _sigma ^ans _tc , A set (m, CT) of the secret information m and the encrypted secret information CT, the random number w, a second element ξ of the first message, a random number ε received from the commit receiver, and a second message γ = A second message calculation unit for calculating P _Σ ^ans ((m, CT), w, ξ, ε), the secret information m, the first element α of the first message, the second message γ, and the random number r. _a second disclosure unit that transmits a quadruple (m, α, γ, r _tc ) composed of _tc as second disclosure information to the commit reception device, wherein the commit reception device has received from the commit generation device A random number generation unit that verifies the quadruplet (sid, ssid, C, R), generates the random number ε ← {0, 1} ^λ_c if there is no problem, and transmits the random number ε to the commit generation device; Before received from the commit generator Quadruplet (sid, ssid, C, R ), the encrypted pre confidential information CT, the disclosure information _{(m, α, γ, r} tc) using said hash function H, the hash value φ '= H ( sid, ssid, C, R, m, CT, α), the hash value φ ′ and the disclosure information (using the encryption algorithm Com ^tc and the verification algorithm V _Σ ^vrfy ). m, α, γ, r _tc ), the encrypted confidential information CT, and the random number ε, Com ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)) is calculated, and the encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)) = 1 holds. Including an unsealed portion for confirming whether or not to perform.

  According to the present invention, it is possible to reduce the common parameter length, the communication amount, and the calculation amount in the CRS reuse type / adaptive safe general-purpose joinable commitment and the CRS reuse type / static secure general-purpose joinable commitment. It becomes.

1 is a block diagram showing a configuration of a commitment system 100. FIG. The block diagram which shows the structure of the common reference information generation apparatus 200. FIG. 5 is a flowchart showing the operation of the common reference information generating apparatus 200. FIG. 2 is a block diagram showing a configuration of a commit generation device 300. FIG. 3 is a block diagram showing a configuration of a commit receiving device 400. FIG. 3 is a sequence diagram of a commit phase (first embodiment). FIG. 3 is a sequence diagram of a decommit phase (first embodiment). Comparison table of commitment methods based on discrete logarithm problem (Embodiment 2). FIG. 3 is a block diagram showing a configuration of a commit generation device 500. 4 is a block diagram showing a configuration of a commit receiving device 600. FIG. FIG. 10 is a sequence diagram of a commit phase (third embodiment). FIG. 10 is a sequence diagram of a decommit phase (third embodiment). Comparison table of commitment schemes based on the discrete logarithm problem (Embodiment 4).

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

<Key points of the present invention>
Non-patent document 4, which is a CRS reusable and adaptively secure universally joinable commitment that is considered to be the most efficient at present, is a public key cipher Cramer-Shoup cipher that is strong against selective ciphertext attacks (reference non-patent document 2) And Pedersen Trapdoor Commitment (Reference Non-Patent Document 3) and Sigma Protocol (Reference Non-Patent Document 4).
(Reference Non-Patent Document 2: Ronald Cramer and Victor Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack”, In Hugo Krawczyk, editor, CRYPTO '98, volume 1462 of Lecture Notes in Computer Science, pages 13- 25, Springer, Heidelberg, 1998.)
(Reference Non-Patent Document 3: Torben P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing”, In Joan Feigenbaum, editor, CRYPTO '91, volume 576 of Lecture Notes in Computer Science, pages 129-140, (Springer, Heidelberg, 1991.)
(Reference Non-Patent Document 4: R. Cramer, I. Damgard and B. Schoenmakers, “Proofs of partial knowledge and simplified design of witness hiding protocols”, In Yvo G. Desmedt, editor, CRYPTO '94, volume 839 of Lecture Notes in Computer Science, pages 174-187, Springer, Heidelberg, 1994.)
In the present invention, by using public key cryptography weaker than the selected ciphertext attack and further comprising two Pedersen trapdoor commitments that have been used, the common parameter length is reduced without compromising the safety of the commitment. Reduce the amount of communication and calculation.

  In another invention of the present application, a commitment in which the safety of the commitment is made statically safe is realized by changing the transmission order of the commit information and the disclosed information in the invention of the present application. This commitment also has a reduced common parameter length, communication volume, and calculation volume compared to the conventional method.

<Preparation>
Prior to the description of the embodiments, notations, terms and the like used in this specification will be described.

[Notation etc.]
^ (Caret) represents a superscript. For example, x ^{y ^ z} represents that ^yz is a subscript to x, and x _{y ^ z} represents ^yz is a subscript to x. _ (Underscore) represents a subscript. For example, ^xy_z represents that _yz is a superscript to x, and _{xy_z} represents that _yz is a subscript to x.

  The algorithm M is probabilistic when the output y of M is determined by the input x and the internal random number (internal coin throw) r of M. That is, M can be written as M (x; r) = y as a two-input function. A deterministic algorithm can be defined as a special case of a stochastic algorithm without internal coins. Hereinafter, writing y ← M (x) means a trial in which the random variable y has been selected from the probability space M (x). On the other hand, when y = M (x; r) is written, M is regarded as a (deterministic) function. If x ← X is written for the set X, it means a trial in which the random variable x is selected from the set X uniformly and randomly.

Let κ be a security parameter, and λ _m (•) and λ _c (•) be a function of κ. Often λ _m (κ) = κ, λ _c (κ) = κ.
H: {0, 1} ^* → {0, 1} ^{Let λ_m} be a collision- ^resistant hash function.

[Public key encryption]
Public key encryption PKE = (K, E, D) is defined by the following three algorithms.

<K: Key generation algorithm>
Input: Security parameter 1 ^κ
Output: Public key and private key pair (pk ^enc , sk ^enc ) ← K (1 ^κ )

<E: Encryption algorithm>
Input: pk ^enc , plaintext m∈MSP _{pk ^ enc} (where MSP _{pk ^ enc} is a set for generating plaintext (hereinafter referred to as plaintext space))
Output: CT = E _{pk ^ enc} (m; w) (W is an internal random number)

<D: Decoding algorithm>
Input: sk ^enc , CT
Output: m = D _{sk ^ enc} (CT)

[Commitment with trapdoor (trapdoor commitment)]
Commitment with trapdoors TCOM = (Gen ^tc , Com ^tc , TCom ^tc , TCol ^tc ) is a commitment composed of the following four algorithms (Reference Non-Patent Document 5).
(Reference Non-Patent Document 5: Gilles Brassard, David Chaum and Claude Crepeau, “Minimum disclosure proofs of knowledge”, Journal of Computer and System Sciences (JCSS), 37 (2), pages 156-189, October 1988.)

<Gen ^tc : Stochastic algorithm>
Input: Security parameter 1 ^κ
Output: Public key and private key pair (pk ^tc , sk ^tc ) ← Gen ^tc (1 ^κ )
Hereinafter, Gen ^tc is also referred to as a key generation algorithm.

<Com ^tc : Stochastic algorithm>
Input: pk ^tc , plaintext φ∈ {0,1} ^λ_m
Output: c = Com ^tc _{pk ^ tc} (φ; r _tc ) (where r _tc is an internal random number)
Hereinafter, Com ^tc is also referred to as an encryption algorithm.

<TCom ^tc : Stochastic algorithm>
Input: sk ^tc , 1 ^κ
Output: (c, ξ) ← TCom ^tc _{sk ^ tc} (1 ^κ )

<TCol ^tc : deterministic algorithm>
Input: sk ^tc , (c, ξ), φ∈ {0, 1} ^λ_m
Output: r = TCol ^tc _{sk ^ tc} (c, ξ, φ)
If (pk ^tc , sk ^tc ) ∈ Gen ^tc , (c, ξ) ∈ TCom ^tc _{sk ^ tc} (1 ^κ ), then for any φ∈ {0, 1} ^* , r = TCol ^It is assumed that ^tc _{sk ^ tc} (c, ξ, φ) satisfies the condition c = Com ^tc _{pk ^ tc} (φ; r).

The trapdoor commitment TCOM further satisfies the following conditions:
1. When pk ^tc is given, Com ^tc _{pk ^ tc} (φ; r _tc ) = Com ^tc _{pk ^ tc} (φ ′; r _tc ′) (φ, r _tc ) ≠ (φ ′, r _tc ′) Is difficult to calculate.
2. For all (pk ^tc , φ), the distribution is the same even if (c, φ, r _tc ) is made in the following two ways. However, COIN _{pk ^ tc} is a set for random number generation (hereinafter referred to as random number space).

1) r _tc <-COIN _{pk ^ tc} ; c = Com ^tc _{pk ^ tc} (φ; r _tc )
2) (c, ξ) ← TCom ^tc _{sk ^ tc} (1 ^κ ); r _tc = TCol ^tc _{sk ^ tc} (c, ξ, φ)
Pedersen's commitment (Reference Non-Patent Document 3) is an example of a DL type trapdoor commitment.

[Sigma protocol]
The language L = {x | (x, w) εR} is an NP language (where the binary relation R is an NP relation). The sigma protocol Σ = (P _Σ ^com , P _Σ ^ans , V _Σ ^vrfy , sim P _Σ ^com ) on the language L is defined by the following four algorithms.

_<P Σ ^com: stochastic algorithm>
Input: (x, w) ∈ R
Output: (α, ξ) ← P Σ com (x, w)
Hereinafter, P _Σ ^com is also referred to as a first message generation algorithm.

<P _Σ ^ans : deterministic algorithm>
Input: (x, w) ∈ R, ξ, ∈ ∈ {0, 1} ^λ_c
Output: γ = P _Σ ^ans (x, w, ξ, ε)
Hereinafter, P _Σ ^ans is also referred to as a second message generation algorithm.

<V _Σ ^vrfy : deterministic algorithm>
Input: xεL, (α, ε, γ)
Output: 0/1 (where 1 represents acceptance, 0 represents non-acceptance)
Hereinafter, V _Σ ^vrfy is also referred to as a verification algorithm.

_<SimP Σ ^com: stochastic algorithm>
Input: xεL, ε
Output: (α, γ) ← simP Σ com (x, ε)
The sigma protocol Σ satisfies the following conditions (refer to Reference Non-Patent Document 4 for details).
1. For all (x, w) ∈R,

This equation is expressed as (α, ξ) ← P _Σ ^com (x, w), ε ← {0, 1} ^λ_c , γ = P _Σ ^ans (x, w, ξ, ε) It is shown that the probability that (α, ε, γ) is accepted by V _Σ ^vrfy becomes 1 when trials and the like are advanced in the order of).
2. epsilon ≠ epsilon 'becomes (α, ε, γ) and (α, ε', γ ' ) is accepted in the V _sigma ^vrfy together ^{_{(i.e., V Σ vrfy (x, (}} α, ε, γ)) = 1 And if V _Σ ^vrfy (x, (α, ε ′, γ ′)) = 1 holds), x∈L.
3. Even if (α, ε, γ) is made in the following two ways for all (x, w) εR, the distribution is the same.

1) (α, ξ) ← P _Σ ^com (x, w); ε ← {0, 1} ^λ_c ; γ = P _Σ ^ans (x, w, ξ, ε)
2) ε ← {0, 1} ^λ_c ; (α, γ) ← simP _Σ ^com (x, ε)

[Language defined from public key cryptography]
The language L ^enc defined from the public key encryption PKE = (K, E, D) is defined as follows.
L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) satisfies w∈COIN _{pk ^ enc} }

<Embodiment 1>
Hereinafter, the commitment system 100 will be described with reference to FIGS. FIG. 1 is a block diagram showing a configuration of the commitment system 100. FIG. 2 is a block diagram illustrating a configuration of the common reference information generation apparatus 200. FIG. 3 is a flowchart showing the operation of the common reference information generating apparatus 200. FIG. 4 is a block diagram illustrating a configuration of the commit generation device 300. FIG. 5 is a block diagram illustrating a configuration of the commit reception device 400. FIG. 6 is a sequence diagram of the commit phase. FIG. 7 is a sequence diagram of the decommit phase.

  As illustrated in FIG. 1, the commitment system 100 includes a common reference information generation device 200, a commit generation device 300, and a commit reception device 400. The common reference information generating device 200, the commit generating device 300, and the commit receiving device 400 are connected to a network 800 (eg, the Internet) and can communicate with each other. As shown in FIG. 2, the common reference information generation apparatus 200 includes a key generation unit 210, a CRS generation unit 220, and a hash function recording unit 290. As illustrated in FIG. 4, the commit generation device 300 includes a secret information encryption unit 305, a first message calculation unit 310, a hash value calculation unit 315, a hash value encryption unit 320, and a first commit unit 325. , A second message calculation unit 330, a deletion unit 335, a second commit unit 340, a disclosure unit 350, a communication unit 380, and a disclosure information recording unit 390. As illustrated in FIG. 5, the commit reception device 400 includes a random number generation unit 405, a hash value calculation unit 450, an unsealing unit 455, a communication unit 480, and a commit information recording unit 490.

[CRS generation]
The common reference information generation device 200 generates common reference information crs from the security parameter 1 ^κ . The key generation unit 210 uses the key generation algorithm K of the public key cryptography PKE and the key generation algorithm Gen ^tc of the trap door commitment TCOM from the security parameter 1 ^κ , and (pk ^enc , sk ^enc ) ← K (1 ^κ ) And (pk ^tc , sk ^tc ) ← Gen ^tc (1 ^κ ) are generated, and sk ^nc and sk ^tc are discarded (S210).

The CRS generation unit 220 reads the hash function H: {0, 1} ^* → {0, 1} ^λ_m recorded in the hash function recording unit 290, and commonly refers to crs = (pk ^enc , pk ^tc , H). It produces | generates and outputs as information (CRS) (S220). The common reference information crs is disclosed so that it can be acquired from the commit generation device 300 and the commit reception device 400. Alternatively, the common reference information generation apparatus 200 may transmit crs to the commit generation apparatus 300 and the commit reception apparatus 400. In any case, at the start of the commit phase, the commit generation device 300 and the commit reception device 400 hold crs.

[Commit (sealing) phase]
The commitment of the present embodiment is a protocol composed of three communications between the commit generation device 300 and the commit reception device 400.

The secret information encryption unit 305 of the commit generation device 300 takes the secret information mεMSP _{pk ^ enc} to be committed as input, generates a random number w ← COIN _{pk ^ enc,} and encrypts the encryption algorithms E and crs of the public key cryptography PKE. The encrypted secret information CT = E _{pk ^ enc} (m, w) is calculated using pk ^enc which is the first element of (S305). However, MSP _{pk ^ enc} is a plaintext space and COIN _{pk ^ enc} is a random number space.

In addition, the set (m, CT) of the secret information m and the CT calculated in S305 has w∈COIN _{pk ^ enc} that satisfies L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) ^Is the source of the language L ^enc defined by

The first message calculation unit 310 of the commit generation device 300 uses the first message generation algorithm P _Σ ^com of the sigma protocol Σ on the language L ^enc , and the first message calculation unit 310 of the sigma protocol Σ for the _element (m, CT) of the language L ^enc One message (α, ξ) ← P _Σ ^com ((m, CT), w) is calculated (S310). Here, w is an element of COIN _{pk ^ enc} that satisfies CT = E _{pk ^ enc} (m, w), and is the random number w generated in S305.

  The hash value calculation unit 315 of the commit generation device 300 calculates the hash value φ = H (sid, ssid, C, R, m, CT, α) using the hash function H that is the third element of crs ( S315). sid is a session ID, ssid is a sub-session ID, C is an ID of the commit generation device 300, and R is an ID of the commit reception device 400, each represented by a finite bit string.

The hash value encryption unit 320 of the commit generation device 300 generates a random number r _tc ← COIN _{pk ^ tc} , and uses pk ^tc which is the second element of the encryption algorithm Com ^tc and crs of the trapdoor commitment TCOM, The encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ; r _tc ) is calculated (S320). Where COIN _{pk ^ tc} is a random number space.

  The first commit unit 325 of the commit generation device 300 transmits the quadruple ID (sid, ssid, C, R) and the encrypted hash value Ψ to the commit reception device 400 (S325). (Sid, ssid, C, R) and Ψ are received using the communication unit 480 (S480-1).

The random number generation unit 405 of the commit reception device 400 verifies (sid, ssid, C, R), and if there is no problem, generates a random number ε ← {0, 1} ^λ_c and transmits it to the commit generation device 300 (S405). . The commit generation device 300 receives ε using the communication unit 380 (S380-1).

The second message calculation unit 330 of the commit generation device 300 uses the second message generation algorithm P _Σ ^ans of the sigma protocol Σ on the language L ^enc , and the second message calculation unit 330 of the sigma protocol Σ for the _element (m, CT) of the language L ^enc Two messages γ = P _Σ ^ans ((m, CT), w, ξ, ε) are calculated (S330). Here, ξ is the second element of the first message calculated in S310.

  The erasure unit 335 of the commit generation device 300 erases the random number w and the second element ξ of the first message (S335).

  The second commit unit 340 of the commit generation device 300 transmits the encrypted confidential information CT to the commit reception device 400 (S340), and the commit reception device 400 receives the encrypted confidential information CT using the communication unit 480. Then, the commit receiver 400 enters an accepting state for the decommit phase (S480-2).

The commit generation device 300 uses the quadruple (m, α, γ, r _tc ) including the secret information m, the first element α of the first message, the second message γ, and the random number r _tc as disclosure information as a disclosure information recording unit. It records in 390 (S390). Further, the commit receiving device 400 records a triplet (CT, Ψ, ε) including the encrypted confidential information CT, the encrypted hash value Ψ, and the random number ε as commit information in the commit information recording unit 490 (S490). ).

[Decommit (open) phase]
The decommitment of the present embodiment is a non-interactive protocol in which the commit generation device 300 sends disclosure information to the commit reception device 400, and the commit reception device 400 determines whether to accept or reject it.

The disclosure unit 350 of the commit generation device 300 transmits the disclosure information (m, α, γ, r _tc ) recorded in the disclosure information recording unit 390 to the commit reception device 400 (S350). Disclosure information (m, α, γ, r _tc ) is received using the communication unit 480 (S480-3).

  The hash value calculation unit 450 of the commit reception device 400 calculates a hash value φ ′ = H (sid, ssid, C, R, m, CT, α) using the hash function H that is the third element of crs. Restore (S450). Note that (sid, ssid, C, R) is received from the commit generation device 300 and held in the commit phase. CT is the first element of the commit information (CT, Ψ, ε) recorded in the commit information recording unit 490.

Open portion 455 of the commit receiving apparatus 400, by using the verification algorithm V _sigma ^vrfy Sigma protocol sigma on encryption algorithms trapdoor commitments TCOM ^{Com tc} and language _{^{L enc, Com tc pk ^ tc}} (φ '; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)), and Ψ = Com ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), It is confirmed whether (α, ε, γ)) = 1 holds (S455). If it is confirmed that the above two formulas are established, it is determined that the opening has been normally performed and approved. On the other hand, opening is refused otherwise. Note that m, α, γ, r _tc are the elements of the disclosure information (m, α, γ, r _tc ) received in S480-3, and CT, Ψ, ε are the commit information recorded in the commit information recording unit 490 ( CT, Ψ, ε).

  Note that (sid, ssid, C, R) is held in the commit generation device 300, and (sid, ssid, C, R) is transmitted again from the commit generation device 300 to the commit reception device 400 in S350. Also good.

<Embodiment 2>
The first embodiment is a general configuration method of a CRS reuse type and adaptive secure general-purpose combined commitment. Therefore, in the second embodiment, the first embodiment is embodied using the cyclic group G as follows.

[Symbols, etc.]
First, symbols are defined as follows.

Let g be a generator of a cyclic group G of order q. Further, κ = log ₂ (q). Group operations are described by multiplication. Since g is a generator of G, there exists x, yεZ / qZ such that a = g ^x , b = g ^y for any a, bεG, and a · b = g ^{x + y} ε G.

Further, it is assumed that λ _m and λ _c ≦ κ.

Further, H ′: {0,1} ^* → Z / qZ is a hash function that hashes a finite-length bit string x∈ {0,1} ^{* based} on Z / qZ.

[Public key encryption]
The public key cipher PKE = (K, E, D) is the following cipher.

<K>
Input: 1 ^κ (where κ = log ₂ (q))
Output: x _e ← Z / qZ is taken at random, and Y _e = g ^x_e is calculated. Z _e , Z _e '← G is taken at random. (Pk ^enc , sk ^enc ) = ((Y _e , Z _e , Z _e ′), x _e ), and (pk ^enc , sk ^enc ) is output.

<E>
Input: pk ^enc , plaintext m∈G
Output: Generate random number w ← COIN _{pk ^ enc} , calculate t = H ′ (sid, ssid, C, R, g ^w ), CT = (g ^w , (Z _e ^t Z _e ′) ^w , m Calculate Y _e ^w ) and output CT.

<D>
Input: sk ^enc , CT
Output: CT = (CT ₁ , CT ₂ , CT ₃ ) is decomposed into CT ₁ , CT ₂ , CT ₃ , m = CT ₃ / CT ₁ ^x_e is calculated and output.

[Language defined from public key cryptography]
Language L ^enc = {(m, CT) | CT = (CT ₁ , CT ₂ , CT ₃ ), CT ₁ = g ^w , CT ₂ = (Z _e ^t Z _e ′) ^w defined from the public key cryptography PKE , CT ₃ = m · Y _e ^w exists w∈COIN _{pk ^ enc} . } (Where t = H ′ (sid, ssid, C, R, CT ₁ )).

[Sigma protocol]
Sigma protocol sigma = linguistic _{^{L enc (P Σ com, P}} Σ ans, V Σ vrfy, simP Σ com) to assume the next.

_<P Σ ^com>
Input: (m, CT), w (where CT = (CT ₁ , CT ₂ , CT ₃ ), CT ₁ = g ^w , CT ₂ = (Z _e ^t Z _e ′) ^w , CT ₃ = m · Y satisfy _e ^w. Note that, t = H '(sid, ssid, C, R, CT 1))
That is, (pk ^enc , sid, ssid, C, R) is also implicitly included.
Output: ξ ← Z / qZ is selected at random, α ₁ = g ^ξ , t = H ′ (sid, ssid, C, R, α ₁ ), α ₂ = (Z _e ^t Z _e ′) ^ξ , α ₃ = Y _e ^ξ α = (α ₁ , α ₂ , α ₃ ) and (α, ξ) is output.

<P _Σ ^ans >
Input: (m, CT), w, ξ, εε {0, 1} ^λ_c (where CT = (CT ₁ , CT ₂ , CT ₃ ), CT ₁ = g ^w , CT ₂ = (Z _e ^t Z _e ′) satisfying ^w , CT ₃ = m · Y _e ^w , where t = H ′ (sid, ssid, C, R, CT ₁ ))
Output: γ = ξ−εw mod q is calculated and γ is output.

<V _Σ ^vrfy >
Input: (m, CT) εL ^enc , (α, ε, γ)
^{_{Output: α 1 = g γ CT 1}} ε, α 2 = (Z e t Z e ') γ CT 2 ε, α 3 = Y e γ 1 if _(CT 3 / m) satisfy all the ^epsilon, if not 0 is output.

_<SimP Σ ^com>
Input: (m, CT) εL ^enc , ε
Output: γ ← Z / qZ is selected at random, α ₁ = g ^γ CT ₁ ^ε , α ₂ = (Z _e ^t Z _e ′) ^γ CT ₂ ^ε , α ₃ = Y _e ^γ (CT ₃ / m) ^ε And α = (α ₁ , α ₂ , α ₃ ), and outputs (α, γ).

[Commitment with trapdoor]
The commitment TCOM with trapdoors is as follows.

<Gen ^tc >
Input: 1 ^κ (where κ = log ₂ (q))
Output: x _tc ← Z / qZ is taken at random, and h = g ^x_tc is calculated. pk ^tc = (G, g, q, h), sk ^tc = (pk ^tc , x _tc ), and (pk ^tc , sk ^tc ) is output.

<Com ^tc >
Input: pk ^tc , plaintext φ∈ {0,1} ^λ_m
Output: Internal random number r _tc ← Z / qZ is taken at random, c = g ^r_tc h ^φ is calculated, and c is output.

<TCom ^tc >
Input: sk ^tc , 1 ^κ
Output: ξ ← Z / qZ is taken at random, c = g ^ξ is calculated, and (c, ξ) is output.

<TCol ^tc >
Input: sk ^tc , (c, ξ), φ∈ {0, 1} ^λ_m
Output: Calculate r = ξ−φ · x _tc mod q and output r (note that c = g ^r h ^φ is satisfied).

<Theoretical Evaluation (Effect) of Invention of Embodiment 2>
The present invention is a general configuration method (embodiment 1) and a specific implementation example (embodiment 2) of a universal combined commitment that can be reused at a fixed length and in which common reference information CRS can be reused. In particular, by configuring the public key cryptosystem, the commitment with trapdoors, and the sigma protocol using a cyclic group, the second embodiment becomes a DL-type CRS reusable and adaptively secure general-purpose combinable commitment.

  FIG. 8 shows a comparison table between the present invention and Non-Patent Document 3 and Non-Patent Document 4. As can be seen from this table, the second and third embodiments are similar in terms of common parameter length, communication amount, and calculation amount in spite of assumptions equivalent to non-patent document 3 and non-patent document 4. I'm winning.

Where κ is a security parameter, a / b is the number of communications (a is the number of communications required for the commit phase, b is the number of communications required for the decommit phase), and T ^exp (G) is on the cyclic group G Represents the cost of one power-residue operation. Although it depends on the expression of G, it may be considered that | G | = κ. DDH means a decision DH assumption, and CRH means a collision-resistant hash function.

Note that the efficiency of the second embodiment is set to λ _m (κ) = κ and λ _c (κ) = κ so that the efficiency is equal to that of Non-Patent Document 3 and Non-Patent Document 4 in consideration of safety. . That is, in terms of safety, the invention of the second embodiment is comparable to DL type non-patent document 3 and non-patent document 4.

  The plaintext m that can be committed in Non-Patent Document 3, Non-Patent Document 4, and Embodiment 2 is | G | bits or less.

<Embodiment 3>
In the first embodiment, the general configuration method of the CRS reuse type and adaptive secure general-purpose combined commitment is shown. However, in some cases, static safety may be sufficient as the security required for a universal combinable commitment system. Also, commitments are often used without disclosure in combination with zero knowledge proofs. In this case, it is more desirable if the communication amount and calculation amount of the commit phase are as small as possible and the commit phase is non-interactive.

  Therefore, in the third embodiment, a general configuration method of a general-purpose combined commitment in which the commit phase is a non-interactive CRS reuse type and static safety will be described. Specifically, this is realized by changing a part of the transmission procedure in the first embodiment.

  The configuration of the CRS reuse type / static secure general-purpose combined commitment system is the same as the configuration of the commitment system 100. In addition, the configuration of the common reference information generation device included in the CRS reuse type / static secure general combined commitment system is the same as the configuration of the common reference information generation device 200 included in the commitment system 100. Therefore, hereinafter, the commit generation device 500 and the commit reception device 600 included in the CRS reuse type / static secure general-purpose combined commitment system will be described with reference to FIGS. FIG. 9 is a block diagram illustrating a configuration of the commit generation device 500. FIG. 10 is a block diagram illustrating a configuration of the commit reception device 600. FIG. 11 is a sequence diagram of the commit phase. FIG. 12 is a sequence diagram of the decommit phase.

  As illustrated in FIG. 9, the commit generation device 500 includes a secret information encryption unit 505, a second commit unit 540, a first message calculation unit 510, a hash value calculation unit 515, and a hash value encryption unit 520. , A first disclosure unit 525, a second message calculation unit 530, a second disclosure unit 550, a communication unit 580, and a disclosure information generation information recording unit 590. As illustrated in FIG. 10, the commit reception device 600 includes a random number generation unit 605, a hash value calculation unit 650, an unsealing unit 655, a communication unit 680, and a commit information recording unit 690.

[Commit (sealing) phase]
The commitment in this embodiment is a non-interactive protocol between the commit generation device 500 and the commit reception device 600.

The secret information encryption unit 505 of the commit generation device 500 takes the secret information mεMSP _{pk ^ enc} to be input as an input, generates a random number w ← COIN _{pk ^ enc,} and encrypts the encryption algorithms E and crs of the public key encryption PKE. The encrypted secret information CT = E _{pk ^ enc} (m, w) is calculated using pk ^enc that is the first element of (S505). However, MSP _{pk ^ enc} is a plaintext space and COIN _{pk ^ enc} is a random number space.

The secret information m and the CT set (m, CT) calculated in S505 have w∈COIN _{pk ^ enc} that satisfies L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w). ^Is the source of the language L ^enc defined by

  The second commit unit 540 of the commit generation device 500 transmits the quadruple ID (sid, ssid, C, R) and the encrypted confidential information CT to the commit reception device 600 (S540). The communication unit 680 is used to receive the quadruple ID (sid, ssid, C, R) and the encrypted confidential information CT, and the commit receiving device 600 enters an accepting state for the decommit phase (S680-). 1). sid is a session ID, ssid is a sub-session ID, C is an ID of a commit generation device 500, and R is an ID of a commit reception device 600, each represented by a finite bit string.

  The commit generation device 500 records a triplet (m, CT, w) including the confidential information m, the encrypted confidential information CT, and the random number w in the disclosed information generating information recording unit 590 as disclosed information generating information ( S590). Further, the commit receiving device 600 records the encrypted confidential information CT as commit information in the commit information recording unit 690 (S690).

[Decommit (open) phase]
In the decommitment of the present embodiment, the commit generation device 500 sends two pieces of disclosure information (first disclosure information and second disclosure information) to the commit reception device 600, and whether the commit reception device 600 accepts or rejects it. This is a protocol for determination. The first disclosure information is the same as the information transmitted by the first commit unit 325 of the first embodiment. Further, the second disclosure information is the same as the information transmitted by the disclosure unit 350 of the first embodiment.

The first message calculation unit 510 of the commit generation device 500 uses the first message generation algorithm P _Σ ^com of the sigma protocol Σ on the language L ^enc , and the first message calculation unit 510 of the sigma protocol Σ for the _element (m, CT) of the language L ^enc One message (α, ξ) ← P _Σ ^com ((m, CT), w) is calculated (S510). Here, m, CT, and w are those recorded in the disclosure information generation information recording unit 590 as disclosure information generation information in S590. Note that w is an element of COIN _{pk ^ enc} that satisfies CT = E _{pk ^ enc} (m, w).

  The hash value calculation unit 515 of the commit generation device 500 calculates the hash value φ = H (sid, ssid, C, R, m, CT, α) using the hash function H that is the third element of crs ( S515). Note that (sid, ssid, C, R) is received from the commit generation device 500 and held in the commit phase.

The hash value encryption unit 520 of the commit generation device 500 generates a random number r _tc ← COIN _{pk ^ tc} , and uses pk ^tc which is the second element of the encryption algorithm Com ^tc and crs of the trapdoor commitment TCOM, The encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ; r _tc ) is calculated (S520). Where COIN _{pk ^ tc} is a random number space.

  The first disclosure unit 525 of the commit generation device 500 transmits the encrypted hash value Ψ as the first disclosure information to the commit reception device 600 (S525), and the commit reception device 600 receives Ψ using the communication unit 680. (S680-2).

The random number generation unit 605 of the commit reception device 600 verifies (sid, ssid, C, R), and if there is no problem, generates a random number ε ← {0, 1} ^λ_c and transmits it to the commit generation device 500 (S605). . The commit generation device 500 receives ε using the communication unit 580 (S580-1).

The second message calculation unit 530 of the commit generation device 500 uses the second message generation algorithm P _Σ ^ans of the sigma protocol Σ on the language L ^enc , and the second message calculation unit 530 of the sigma protocol Σ for the _element (m, CT) of the language L ^enc Two messages γ = P _Σ ^ans ((m, CT), w, ξ, ε) are calculated (S530). Here, ξ is the second element of the first message calculated in S510.

The second disclosure unit 550 of the commit generation device 500 includes the second disclosure information (m, α, γ,) including the secret information m, the first element α of the first message, the second message γ, and the random number r _tc . r _tc ) is transmitted to the commit receiving device 600 (S550), and the commit receiving device 600 receives the second disclosure information (m, α, γ, r _tc ) using the communication unit 680 (S680-3).

  The hash value calculation unit 650 of the commit reception device 600 calculates a hash value φ ′ = H (sid, ssid, C, R, m, CT, α) using the hash function H that is the third element of crs. Restoration is performed (S650). Note that (sid, ssid, C, R) is received from the commit generation device 500 and held in the commit phase. CT is commit information recorded in the commit information recording unit 690.

Open portion 655 of the commit receiving apparatus 600, by using the verification algorithm V _sigma ^vrfy Sigma protocol sigma on encryption algorithms trapdoor commitments TCOM ^{Com tc} and language _{^{L enc, Com tc pk ^ tc}} (φ '; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)), and Ψ = Com ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), It is confirmed whether (α, ε, γ)) = 1 holds (S655). If it is confirmed that the above two formulas are established, it is determined that the opening has been normally performed and approved. On the other hand, opening is refused otherwise. Note that m, α, γ, r _tc are elements of the second disclosure information (m, α, γ, r _tc ) received in S680-3, CT is commit information recorded in the commit information recording unit 690, and Ψ is This is the first disclosure information received in S680-2.

  Note that (sid, ssid, C, R) is held in the commit generation device 500, and (sid, ssid, C, R) is transmitted from the commit generation device 500 to the commit reception device 600 again in S525 and S550. It may be.

<Embodiment 4>
The third embodiment is a general configuration method of a CRS reuse type / static secure general-purpose combined commitment in which the commit phase is non-interactive. Embodiment 4 may be a general-purpose binding of applying a public key cryptography PKE used in the second embodiment, the language L ^enc defined from the public key ^encryption, Sigma protocol Σ linguistic L ^enc, the trapdoor commitments TCOM to Embodiment 3 It is a commitment.

  As a result, a DL-type CRS reusable and statically safe general-purpose combined commitment can be configured.

<Theoretical Evaluation (Effect) of Invention of Embodiment 4>
The present invention has a non-interactive commit phase, the common reference information CRS can be reused with a fixed length, and a general configuration method of a statically safe general-purpose combined commitment (third embodiment) and a specific implementation example (implementation) Form 4). In particular, by configuring the public key cryptography, the commitment with trapdoors, and the sigma protocol using a cyclic group, the fourth embodiment becomes a DL-type CRS reusable / static secure general-purpose combinable commitment.

  FIG. 13 shows a comparison table between the present invention and Non-Patent Document 3 and Non-Patent Document 4. Note that non-patent document 3 (Lin11) and non-patent document 4 (BCPV13) in FIG. 13 are different from non-patent document 3 (Lin11) and non-patent document 4 (BCPV13) in FIG. Is a general-purpose combined commitment. As can be seen from this table, as in the case of the second embodiment, the fourth embodiment is similar to the non-patent document 3 and the non-patent document 4, but the common parameter length, communication amount, calculation You win in terms of quantity.

Note that the efficiency of the fourth embodiment is set to λ _m (κ) = κ and λ _c (κ) = κ so that the efficiency is equal to that of Non-Patent Document 3 and Non-Patent Document 4. This is the same as in the second embodiment. That is, in terms of safety, like the second embodiment, the invention of the fourth embodiment is comparable to the DL type non-patent document 3 and the non-patent document 4.

  The plaintext m that can be committed in Non-Patent Document 3, Non-Patent Document 4, and Embodiment 4 is the same as that of Embodiment 2 in that it is equal to or smaller than | G | bits.

<Supplementary note>
The apparatus of the present invention includes, for example, a single hardware entity as an input unit to which a keyboard or the like can be connected, an output unit to which a liquid crystal display or the like can be connected, and a communication device (for example, a communication cable) capable of communicating outside the hardware entity. Can be connected to a communication unit, a CPU (Central Processing Unit, may include a cache memory or a register), a RAM or ROM that is a memory, an external storage device that is a hard disk, and an input unit, an output unit, or a communication unit thereof , A CPU, a RAM, a ROM, and a bus connected so that data can be exchanged between the external storage devices. If necessary, the hardware entity may be provided with a device (drive) that can read and write a recording medium such as a CD-ROM. A physical entity having such hardware resources includes a general-purpose computer.

  The external storage device of the hardware entity stores a program necessary for realizing the above functions and data necessary for processing the program (not limited to the external storage device, for example, reading a program) It may be stored in a ROM that is a dedicated storage device). Data obtained by the processing of these programs is appropriately stored in a RAM or an external storage device.

  In the hardware entity, each program stored in an external storage device (or ROM or the like) and data necessary for processing each program are read into a memory as necessary, and are interpreted and executed by a CPU as appropriate. . As a result, the CPU realizes a predetermined function (respective component requirements expressed as the above-described unit, unit, etc.).

  The present invention is not limited to the above-described embodiment, and can be appropriately changed without departing from the spirit of the present invention. In addition, the processing described in the above embodiment may be executed not only in time series according to the order of description but also in parallel or individually as required by the processing capability of the apparatus that executes the processing. .

  As described above, when the processing functions in the hardware entity (the apparatus of the present invention) described in the above embodiments are realized by a computer, the processing contents of the functions that the hardware entity should have are described by a program. Then, by executing this program on a computer, the processing functions in the hardware entity are realized on the computer.

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

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, a hardware entity is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

Claims (10)

A commitment system including a common reference information generating device, a commit generating device, and a commit receiving device,
κ is a security parameter, λ _m (·), λ _c (·) is a function of κ, H: {0,1} ^* → {0,1} ^λ_m is a hard-to-collision hash function, K is a key of public key cryptography PKE Generation algorithm, E is the encryption algorithm of public key cryptography PKE, Gen ^tc is the key generation algorithm of the door-to-door commitment TCOM, Com ^tc is the encryption algorithm of the door-to-door commitment TCOM, L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) satisfying w∈COIN _{pk ^ enc} } is a language defined by public key cryptography PKE (where COIN _{pk ^ enc} is a random number space), P _Σ ^com is a language L ^enc on the first message generation algorithm sigma protocol sigma of the second message generation a sigma protocol sigma on P _sigma ^ans language ^{L enc} Lugorism, V _Σ ^vrfy as a verification algorithm for the sigma protocol Σ on the language L ^enc
The common reference information generation device includes:
From 1 ^kappa, the key generation algorithm K, using the ^{Gen tc,} 2 one public and private key pair ^{(pk enc, sk enc) ←} K (1 κ), (pk tc, sk tc) ← Gen tc ( 1 ^κ ) and a key generation unit for discarding the secret keys sk ^enc and sk ^tc ;
A public key pk ^enc , pk ^tc , and a CRS generator that generates crs = (pk ^enc , pk ^tc , H) as a set of hash functions H as common reference information,
The commit generation device includes:
A random number w ← COIN _{pk ^ enc} (where COIN _{pk ^ enc} is a random number space) is generated, and the secret information mεMSP _{pk ^ enc} (where MSP _pk is used) using the encryption algorithm E and the public key pk ^enc. _{^ enc} is a plaintext space), and a secret information encryption unit for calculating encrypted secret information CT = E _{pk ^ enc} (m, w);
Using the first message generation algorithm P _Σ ^com , the first message (α, ξ) ← P _Σ ^com (from the set (m, CT) of the secret information m and the encrypted secret information CT and the random number w. A first message calculator for calculating (m, CT), w);
The hash function H and a quadruple (sid, ssid, C, R) (where sid is a session ID, ssid is a sub-session ID, C is an ID of the commit generating device, and R is an ID of the commit receiving device) Using the finite bit string, the secret information m, the encrypted secret information CT, and the first element α of the first message have a hash value φ = H (sid, ssid, C, R, m, CT, α ) For calculating the hash value,
A random number r _tc ← COIN _{pk ^ tc} (where COIN _{pk ^ tc} is a random number space) is generated, and an encrypted hash value Ψ is obtained from the hash value φ using the encryption algorithm Com ^tc and the public key pk ^tc. = Hash value encryption unit for calculating Com ^tc _{pk ^ tc} (φ; r _tc ),
A first commit unit that transmits the quadruple (sid, ssid, C, R) and the encrypted hash value Ψ to the commit receiver;
Using the second message generation algorithm P _Σ ^ans , the set (m, CT) of the secret information m and the encrypted secret information CT, the random number w, the second element ξ of the first message, the commit reception A second message calculator for calculating a second message γ = P _Σ ^ans ((m, CT), w, ξ, ε) from a random number ε received from the device;
An erasure unit for erasing the random number w and the second element ξ of the first message;
A second commit unit that transmits the encrypted confidential information CT to the commit receiver;
A set of four pieces (m, α, γ, r _tc ) composed of the secret information m, the first element α of the first message, the second message γ, and the random number r _tc is transmitted as disclosure information to the commit receiver. Including the disclosure section
The commit receiver
The quadruplet (sid, ssid, C, R) received from the commit generation device is verified. If there is no problem, the random number ε ← {0, 1} ^λ_c is generated, and the random number ε is ^transmitted to the commit generation device. A random number generator to transmit;
Using the quadruple (sid, ssid, C, R) received from the commit generation device, the encrypted confidential information CT, the disclosed information (m, α, γ, r _tc ) and the hash function H A hash value calculator for calculating a hash value φ ′ = H (sid, ssid, C, R, m, CT, α);
Using the encryption algorithm Com ^tc and the verification algorithm V _Σ ^vrfy , the hash value φ ′, the disclosure information (m, α, γ, r _tc ), the encrypted confidential information CT, and the random number ε ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)) are calculated, and the encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ ′ A commitment system including: r _tc ) and an opening portion for confirming whether V _Σ ^vrfy ((m, CT), (α, ε, γ)) = 1 holds. A commitment system including a common reference information generating device, a commit generating device, and a commit receiving device,
κ is a security parameter, λ _m (·), λ _c (·) is a function of κ, H: {0,1} ^* → {0,1} ^λ_m is a hard-to-collision hash function, K is a key of public key cryptography PKE Generation algorithm, E is the encryption algorithm of public key cryptography PKE, Gen ^tc is the key generation algorithm of the door-to-door commitment TCOM, Com ^tc is the encryption algorithm of the door-to-door commitment TCOM, L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) satisfying w∈COIN _{pk ^ enc} } is a language defined by public key cryptography PKE (where COIN _{pk ^ enc} is a random number space), P _Σ ^com is a language L ^enc on the first message generation algorithm sigma protocol sigma of the second message generation a sigma protocol sigma on P _sigma ^ans language ^{L enc} Lugorism, V _Σ ^vrfy as a verification algorithm for the sigma protocol Σ on the language L ^enc
The common reference information generation device includes:
From 1 ^kappa, the key generation algorithm K, using the ^{Gen tc,} 2 one public and private key pair ^{(pk enc, sk enc) ←} K (1 κ), (pk tc, sk tc) ← Gen tc ( 1 ^κ ) and a key generation unit for discarding the secret keys sk ^enc and sk ^tc ;
A public key pk ^enc , pk ^tc , and a CRS generator that generates crs = (pk ^enc , pk ^tc , H) as a set of hash functions H as common reference information,
The commit generation device includes:
A random number w ← COIN _{pk ^ enc} (where COIN _{pk ^ enc} is a random number space) is generated, and the secret information mεMSP _{pk ^ enc} (where MSP _pk is used) using the encryption algorithm E and the public key pk ^enc. _{^ enc} is a plaintext space), and a secret information encryption unit for calculating encrypted secret information CT = E _{pk ^ enc} (m, w);
Quadruple (sid, ssid, C, R) (where sid is the session ID, ssid is the sub-session ID, C is the ID of the commit generating device, and R is a finite bit string indicating the ID of the commit receiving device), A second commit unit that transmits the encrypted confidential information CT to the commit receiver;
Using the first message generation algorithm P _Σ ^com , the first message (α, ξ) ← P _Σ ^com (from the set (m, CT) of the secret information m and the encrypted secret information CT and the random number w. A first message calculator for calculating (m, CT), w);
Using the hash function H and the (sid, ssid, C, R), the hash value φ = H (sid, Sid, m) from the secret information m, the encrypted secret information CT, and the first element α of the first message. hash value calculation unit for calculating ssid, C, R, m, CT, α),
A random number r _tc ← COIN _{pk ^ tc} (where COIN _{pk ^ tc} is a random number space) is generated, and an encrypted hash value Ψ is obtained from the hash value φ using the encryption algorithm Com ^tc and the public key pk ^tc. = Hash value encryption unit for calculating Com ^tc _{pk ^ tc} (φ; r _tc ),
A first disclosure unit that transmits the encrypted hash value ψ to the commit receiver;
Using the second message generation algorithm P _Σ ^ans , the set (m, CT) of the secret information m and the encrypted secret information CT, the random number w, the second element ξ of the first message, the commit reception A second message calculator for calculating a second message γ = P _Σ ^ans ((m, CT), w, ξ, ε) from a random number ε received from the device;
The commit reception device using the secret information m, the first element α of the first message, the second message γ, and the quadrature (m, α, γ, r _tc ) made up of the random number r _tc as second disclosure information A second disclosure part that transmits to
The commit receiver
The quadruplet (sid, ssid, C, R) received from the commit generation device is verified. If there is no problem, the random number ε ← {0, 1} ^λ_c is generated, and the random number ε is ^transmitted to the commit generation device. A random number generator to transmit;
Using the quadruple (sid, ssid, C, R) received from the commit generation device, the encrypted confidential information CT, the disclosed information (m, α, γ, r _tc ) and the hash function H A hash value calculator for calculating a hash value φ ′ = H (sid, ssid, C, R, m, CT, α);
Using the encryption algorithm Com ^tc and the verification algorithm V _Σ ^vrfy , the hash value φ ′, the disclosure information (m, α, γ, r _tc ), the encrypted confidential information CT, and the random number ε ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)) are calculated, and the encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ ′ A commitment system including: r _tc ) and an opening portion for confirming whether V _Σ ^vrfy ((m, CT), (α, ε, γ)) = 1 holds. The commitment system according to claim 1 or claim 2,
g is a generator of the cyclic group G of order q, κ is κ = log ₂ (q), and the hash function H is H ′: {0, 1} ^* → Z / qZ (that is, a finite-length bit string x ∈ {0,1} ^* is a hash function that hashes to Z / qZ))
Λ _m and λ _c satisfy λ _m and λ _c ≦ κ,
The key generation algorithm K takes x _e ← Z / qZ at random, calculates Y _e = g ^x_e , takes Z _e , Z _e ′ ← G at random, and then (pk ^enc , sk ^enc ) = ((Y _e , Z _e , Z _e ′), x _e )
The encryption algorithm E generates a random number w ← COIN _{pk ^ enc} , calculates t = H ′ (sid, ssid, C, R, g ^w ), and CT = (g ^w , (Z _e ^t Z _e). ') ^W , m · Y _e ^w ) (where m∈G),
The language L ^enc is ^expressed as L ^enc = {(m, CT) | CT = (CT ₁ , CT ₂ , CT ₃ ), CT ₁ = g ^w , CT ₂ = (Z _e ^t Z _e ′) ^w , CT ₃ = There exists wεCOIN _{pk ^ enc} that satisfies m · Y _e ^w . } (Where t = H ′ (sid, ssid, C, R, CT ₁ )),
The first message generation algorithm P _Σ ^com is (m, CT), w (where CT = (CT ₁ , CT ₂ , CT ₃ ), CT ₁ = g ^w , CT ₂ = (Z _e ^t Z _e ′). ^W , CT ₃ = m · Y _e ^w , where t = H ′ (sid, ssid, C, R, CT ₁ )) is input, and ξ ← Z / qZ is selected at random, α ₁ = g ^ξ , t = H ′ (sid, ssid, C, R, α ₁ ), α ₂ = (Z _e ^t Z _e ′) ^ξ , α ₃ = Y _e ^ξ and α = (α ₁ , α ₂ , α ₃ ) and (α, ξ) is output,
The second message generation algorithm P _Σ ^ans is (m, CT), w, ξ, ε∈ {0, 1} ^λ_c (where CT = (CT ₁ , CT ₂ , CT ₃ ), CT ₁ = g ^w , CT ₂ = (Z _e ^t Z _e ′) ^w , CT ₃ = m · Y _e ^w , where t = H ′ (sid, ssid, C, R, CT ₁ )) is input and γ = ξ−εw mod q is an algorithm that outputs γ,
The verification algorithm V _Σ ^vrfy takes (m, CT) εL ^enc and (α, ε, γ) as inputs, and α ₁ = g ^γ CT ₁ ^ε and α ₂ = (Z _e ^t Z _e ′) ^γ CT ₂ ^ε , α ₃ = Y _e ^γ (CT ₃ / m) An algorithm that outputs 1 if ^ε is satisfied, and outputs 0 otherwise.
The key generation algorithm Gen ^tc takes x _tc ← Z / qZ at random, calculates h = g ^x_tc , pk ^tc = (G, g, q, h), sk ^tc = (pk ^tc , x _tc ), and (pk ^tc , sk ^tc ) is output.
The encryption algorithm ^{Com tc} takes an internal random number _{r tc} ← Z / qZ randomly commitment system is an algorithm that calculates the ^c = ^g r_tc h ^x, outputs or c. The common reference information generation apparatus included in the commitment system according to any one of claims 1 to 3 . A commit generation device included in the commitment system according to any one of claims 1 to 3 . A commit receiver included in the commitment system according to any one of claims 1 to 3 . A commitment method executed by a commitment system including a common reference information generating device, a commit generating device, and a commit receiving device,
κ is a security parameter, λ _m (·), λ _c (·) is a function of κ, H: {0,1} ^* → {0,1} ^λ_m is a hard-to-collision hash function, K is a key of public key cryptography PKE Generation algorithm, E is the encryption algorithm of public key cryptography PKE, Gen ^tc is the key generation algorithm of the door-to-door commitment TCOM, Com ^tc is the encryption algorithm of the door-to-door commitment TCOM, L ^enc = {(m, CT) | CT = E _{pk ^ enc} (m, w) satisfying w∈COIN _{pk ^ enc} } is a language defined by public key cryptography PKE (where COIN _{pk ^ enc} is a random number space), P _Σ ^com is a language L ^enc on the first message generation algorithm sigma protocol sigma of the second message generation a sigma protocol sigma on P _sigma ^ans language ^{L enc} Lugorism, V _Σ ^vrfy as a verification algorithm for the sigma protocol Σ on the language L ^enc
The common reference information generation apparatus uses the key generation algorithm K and Gen ^tc from 1 ^κ , and sets of two public keys and secret keys (pk ^enc , sk ^enc ) ← K (1 ^κ ), (pk ^tc , Sk ^tc ) ← Gen ^tc (1 ^κ ), and the secret key sk ^enc , sk ^tc is discarded,
A CRS generating step in which the common reference information generation device generates crs = (pk ^enc , pk ^tc , H) as a set of the public keys pk ^enc , pk ^tc and the hash function H as common reference information;
The commit generating device, random number w ← COIN _{pk ^ enc} (However, COIN _{pk ^ enc} is random number space) to generate, using the public key ^{pk enc} and the encryption algorithm E, confidential information m∈MSP _{pk ^} a secret information encryption step for calculating encrypted secret information CT = E _{pk ^ enc} (m, w) from _enc (where MSP _{pk ^ enc} is a plaintext space);
The commit generation device uses the first message generation algorithm P _Σ ^com to generate a first message (α, ξ) from the set (m, CT) of the secret information m and the encrypted secret information CT and the random number w. ) ← First message calculation step of calculating P _Σ ^com ((m, CT), w);
The commit generation device is a quadruple (sid, ssid, C, R) with the hash function H (where sid is a session ID, ssid is a sub-session ID, C is a commit generation device ID, and R is a commit reception device) ) Using the secret information m, the encrypted secret information CT, and the first element α of the first message, the hash value φ = H (sid, ssid, C, R, m). , CT, α) for calculating a hash value,
The commit generation device generates a random number r _tc ← COIN _{pk ^ tc} (where COIN _{pk ^ tc} is a random number space), and uses the encryption algorithm Com ^tc and the public key pk ^tc from the hash value φ. A hash value encryption step of calculating an encrypted hash value Ψ = Com ^tc _{pk ^ tc} (φ; r _tc );
A first commit step in which the commit generating device transmits the quadruple (sid, ssid, C, R) and the encrypted hash value Ψ to the commit receiving device;
The commit receiver verifies the quadruplicate (sid, ssid, C, R), and if there is no problem, generates a random number ε ← {0, 1} ^λ_c and transmits the random number ε to the commit generator. A random number generation step;
The commit generation device uses the second message generation algorithm P _Σ ^ans to set the secret information m and the encrypted secret information CT (m, CT), the random number w, and the second of the first message. A second message calculation step of calculating a second message γ = P _Σ ^ans ((m, CT), w, ξ, ε) from the element ξ and the random number ε;
The commit generating device erasing the random number w and the second element ξ of the first message;
A second commit step in which the commit generating device transmits the encrypted confidential information CT to the commit receiving device;
The commit generation device uses the secret information m, the first element α of the first message, the second message γ, and the random number r _{tc as a} set of four (m, α, γ, r _tc ) as disclosure information. A disclosure step of transmitting to the commit receiver;
The commit receiver uses the quadruple (sid, ssid, C, R), the encrypted confidential information CT, the disclosed information (m, α, γ, r _tc ) and the hash function H, A hash value calculation step of calculating a hash value φ ′ = H (sid, ssid, C, R, m, CT, α);
Using the encryption algorithm Com ^tc and the verification algorithm V _Σ ^vrfy , the commit receiver uses the hash value φ ′, the disclosed information (m, α, γ, r _tc ), and the encrypted confidential information CT. Then, Com ^tc _{pk ^ tc} (φ ′; r _tc ) and V _Σ ^vrfy ((m, CT), (α, ε, γ)) are calculated from the random number ε, and the encrypted hash value Ψ = Com ^tc A commitment method including _{: pk ^ tc} (φ ′; r _tc ) and an unsealing step for checking whether V _Σ ^vrfy ((m, CT), (α, ε, γ)) = 1 holds. A program for causing a computer to function as the common reference information generating apparatus according to claim 4. A program for causing a computer to function as the commit generation device according to claim 5. A program for causing a computer to function as the commit receiver according to claim 6.

Images