JP5264450B2 - Bit commitment verification system, bit commitment device, verification device, bit commitment verification method, bit commitment method, verification method, bit commitment program, verification program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a bit commitment method and the apparatus capable of being effectively used in other encryption protocols making opening information as an origin of G. <P>SOLUTION: A bit commitment verification system has a registration apparatus, a bit commitment apparatus, and a verification apparatus. The bit commitment apparatus uses generation origins of two groups, and generates a commitment key ck. C=&Pi;<SP>n</SP><SB>i=1</SB>g<SP>mi</SP>h<SB>1</SB><SP>ri</SP>is calculated from g, h<SB>1</SB>, and r<SB>i</SB>, and information to be committed m<SB>i</SB>, and it is output as commitment. Opening information H=&Pi;<SP>n</SP><SB>i=1</SB>h<SB>2</SB><SP>ri</SP>is calculated. The verification apparatus determines whether an equation e(C/&Pi;<SP>n</SP><SB>i=1</SB>g<SP>mi</SP>, h<SB>2</SB>)=e(h<SB>1</SB>, H) is right, if it is right, the verification is passed, and if it is not right, the verification is not passed. <P>COPYRIGHT: (C)2010,JPO&amp;INPIT

Description

  The present invention relates to a bit commitment verification system, a bit commitment device, a verification device, and a method for committing (verifying) and verifying information that is a telecommunication system.

  Bit commitment is a method of convincing the receiver later that the sender has held the message m at some point. For example, let us consider a method in which A and B perform fair fairness that does not allow later work. A first puts his choice ("Goo", "Choki" or "Par") written on the paper into the safe, locks it, and passes only the safe to B. Next, B tells A about his choice. A confirms the selection of B and then passes the key to B. B opens the safe with the received key, confirms A's selection, and confirms the victory or defeat of Janken. A bit commitment is a method of electronically providing a function corresponding to the “safe” or “key”.

  A bit commitment method (so-called “Pedersen's commitment”) described in Non-Patent Document 1 will be described.

  Let q be a large prime number and G be a (multiplicative) group of order q, where the discrete logarithm problem is difficult.

A person A who makes a commitment randomly selects two generators g and h having different G, and uses (G, q, g, h) as a commitment key. Hereinafter, Z _q is a set of integers from 0 to q−1, and Z _q ^* is a set obtained by removing 0 from Z _q . Let the information to be committed be mεZ _q .

Those who make commitments randomly select r from Z _q and use it as opening information.
C = g ^m h ^r ∈G (1)
And C is sent as a commitment to verifier B. Further, the information m and the opening information r are stored secretly.

After that, A releases information m and opening information r.
B is commitment key (G, q, g, h ) g and the information m from the unsealing information ^{r m h r = C (2} )
It is verified whether or not equation (2) holds. If true, it can be confirmed that the information m has not been changed since C was sent to the verifier B. If it does not hold, there is a possibility of falsification.

Knowing the information m from the commitment C = g ^m h ^r is information theoretically impossible. That is, the verifier B cannot know the information m when the commitment C is received. On the other hand, generating the commitment C by two types (m, r) and (m ′, r ′) is equivalent to obtaining the discrete logarithm log _g h∈Z _q , and assumes the difficulty of the discrete logarithm problem. Then, once committed C can be opened only with one piece of information m and opening information r. Therefore, A cannot tamper with the information m after sending the commitment C to the verifier B.

Bit commitment is closely related to cryptographic protocols. For example, it is used for zero knowledge proof, multi-party calculation, electronic money, electronic voting, group signature and the like.
Torben P. Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing", Advances in Cryptology-CRYPTO '91, Springer Berlin / Heidelberg, 1992, Volume 576/1992, p.129-140

When bit commitment is used in a cryptographic protocol, it may be necessary for the commitment creator to prove only the fact that he holds the correct opening information without actually publishing the opening information r. For example, using a non-interactive zero knowledge proof that shows various relationships between committed messages, the fact that r is kept, i.e., commitment C can be opened, while the opening information r is kept secret, is the third party Can be convinced. For example, Jens Groth, Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Advances in Cryptology-EUROCRYPT 2008, Springer Berlin / Heidelberg, June 3,2008, Volume 4965/2008, p415-432 (hereinafter "References" 1)), if the unsealing information r is an element of G, it is described that an efficient non-interactive zero knowledge proof can be constructed using pairing. As in Reference 1, the non-interactive zero knowledge proof for the case where the opening information r is an element of Z _q is known to have an efficient configuration in an ideal random oracle model. In models that do not assume, only inefficient configurations are known. In the bit comment method described in Non-Patent Document 1, since the opening information (m, r) is not an element of G, zero knowledge proof, group signature, etc. can be efficiently constructed using the element of G. I can't.

  SUMMARY OF THE INVENTION An object of the present invention is to provide a bit comment method and apparatus that can be used efficiently in other cryptographic protocols with unsealing information as a source of G.

The bit commitment verification system of the present invention comprises a registration device, a bit commitment device, and a verification device. The q is a prime _number, G _1, G 2, the _{G T} as a group of order q, e bilinear map e: and _{G 1 × G 2 → G T} , the public parameter _{v = (q, G 1,} G 2, Let G _T , e). Bit Comment apparatus, the generator g and h ₁ from G _1, the origin h ₂ from the G _2, randomly selected, to generate a commitment key ck using these origin. A random number r _i belonging to Z _q (where 1 ≦ i ≦ n, where n represents the number of pieces of information m) is generated. The public parameter v and the random number r _i are stored, and in particular, the random number r _i is stored secretly. g, a ^{_{C = Π n i = 1 g}} mi h 1 ri calculated from _{h 1} and _{r i} and committed information _{m i,} and outputs it as commitments. Opening information H = Π ⁿ _{i = 1} h ₂ ^ri is calculated. The verification device stores the commitment key ck, information M, and unsealing information H and C. Equation _{^{e (C / Π n i =}} 1 g mi, h 2) = e (h 1, H) , it is determined whether or not satisfied, the pass if satisfied, fail if not satisfied And The registration device has a storage unit that stores the public parameter v and the commitment key ck. The bit commitment device receives the public parameter v from the registration device, sends the commitment key ck to the registration device, sends the commitment C to the verification device, and sends the commitment C at the same time or after sending the information M including the information m and the opening Information H is sent to the verification device. The verification device receives the commitment key ck from the registration device and the commitment C, information M, and unsealing information H from the bit commitment device.

  According to the bit commitment verification method and apparatus of the present invention, the bit commitment method can be efficiently used as a component of various other cryptographic protocols.

  For example, when the bit commitment method of the present invention is used, since the unsealing information is an element of G, an efficient non-interactive zero knowledge proof using pairing can be configured.

  Here, examples of the present invention will be described.

[Bit commitment verification system 1]
FIG. 1 is a diagram illustrating a configuration example of the bit commitment verification system 1. FIG. 2 is a diagram illustrating an example of a sequence diagram of the bit commitment verification system 1. The bit commitment verification system 1 includes a registration device 300, a bit commitment device 100, and a verification device 200.

and a large prime number _q, and the group of _{G 1,} G _2, G _T the position number q, by e of efficiently computable linear map e: and _{G 1 × G 2 → G T} , v = (q, G ₁ , G ₂ , G _T , e) are public parameters. Here, G ₁ and G ₂ are groups having a property that h ₂ ^r can be calculated from arbitrary h ₁ ^r only when r is known. Note that g ^a means that the operation defined by the group G is performed a times for gεG. Examples of the bilinear map include Weil pairing and Tate pairing.

  In order to generate the commitment C, the bit commitment device 100 requests the public parameter v from the registration device 300 (s10). The registration device 300 sends v to the bit commitment device 100 (s12). The bit commitment device 100 generates a commitment key ck from the public parameter v and sends it to the registration device 300 (s14). The registration device 300 registers and discloses the commitment key ck (s16). Note that the commitment key may be generated by using the stored public parameter without requesting the public parameter every time it is sent. Further, a commitment C is generated using the information m, the commitment key ck, and the random number r. The bit commitment device 100 sends the commitment C to the verification device (s18). Simultaneously with or after sending, the unsealing information H calculated using the random number r and the information M including the information m are sent to the verification device (s19).

  The verification device 200 requests the registration device 300 for a commitment key ck corresponding to the commitment C (s20). The registration device 300 sends the commitment key ck to the verification device 200 (s22). The verification device 200 verifies whether falsification or impersonation has been performed using the commitment C, the information m, and the commitment key ck (s24), and the information m has been falsified from the time when the commitment C is certainly sent. Make sure it is not. Hereinafter, details of each device and each process will be described.

[Registration device 300]
The registration device 300 registers and publishes the public parameter v. For example, the registration apparatus 300 is managed by a trusted third party or the like, and includes a communication unit 301, a storage unit 303, and a control unit 305. The registration device 300 communicates with the bit commitment device and the verification device via the communication unit 301. Hereinafter, it is assumed that the communication with the bit comment device 100 and the verification device 200 is performed via the communication unit 301 even if not specifically described. The communication unit 301 is configured by a LAN adapter or the like, for example, and is connected to a communication line made up of a LAN, the Internet or the like. However, the communication unit may not necessarily be provided. For example, the public parameter may be input from an input device such as a keyboard, or the public parameter may be stored in a portable medium such as a USB memory and input. May be. Similarly, each device (bit comment device and verification device) may not have the transmission units 101 and 201, and data input / output between devices may be a method other than communication. The storage unit 303 stores public parameters, commitment keys, and the like. The “registration” may mean storing in the storage unit 303. In addition, “public” means that information (for example, public parameters) can be browsed or acquired according to a user's request. The control unit 305 controls each process.

[Bit Commitment Device 100]
FIG. 3 is a diagram illustrating a configuration example of the bit commitment device 100. FIG. 4 is a diagram illustrating an example of a processing flow of the bit commitment device 100. The bit commitment device 100 includes a communication unit 101, a storage unit 103, a control unit 105, a commitment key generation unit 120, a random number generation unit 130, an unsealing information generation unit 140, and a commitment generation unit 150.

<Control unit 105, communication unit 101, and storage unit 103>
The bit commitment device 100 according to this embodiment executes each process under the control of the control unit 105. The bit commitment device 100 receives the public parameter v from the registration device 300. For example, the communication unit 101 communicates with the registration device 300 and the verification device 200, and receives the public parameter v from the registration device 300 (s101). Hereinafter, it is assumed that the communication with the registration device 300 and the verification device 200 is performed via the communication unit 101 even if not specifically described.

  The received public parameter v is stored in the storage unit 103 (s103). Unless otherwise indicated, each input / output data and each data in the calculation process are stored / read out in the storage unit 103 one by one, and each calculation process proceeds. However, the data need not necessarily be stored in the storage unit 103, and data may be directly transferred between the units.

<Commitment key generation unit 120>
Commitment key generating unit 120, the generator g and _{h 1} from _{G 1,} the origin _{h 2} from the _{G 2,} randomly selected, to generate a commitment key ck using these origin (s120). For example, it is generated as a commitment key ck = (v, g, h ₁ , h ₂ ). Commitment key generating unit 120 via the communication unit 101, or, the public parameter v via the communication unit 101 and the storage unit 103 is inputted, the origin _{h 2} to unsealing information calculating unit 140, the generator g and h ₁ is output to the commitment generation unit 150. In addition, the commitment key ck is sent to the registration apparatus 300 via the communication unit 101. The commitment key ck may include pk = (i, g, h ₁ , h ₂ ) including information i indicating the public parameter used. In this case, the verification device 200 described below requests a public parameter v _i corresponding to the registration device 300 based on the information i. Further, when the corresponding public parameter can be specified from the public parameters stored in the registration apparatus 300, the commitment key ck need not include the public parameter v, the information i indicating the public parameter, or the like. The verification apparatus 200 requests the public parameter v from the registration apparatus 300 when receiving the information M and the opening information H.

<Random number generator 130 and opening information calculator 140>
Random number generation unit 130 generates a random number r which belongs to _{Z q} (s130). The random number r is output to the opening information calculation unit 140 and the commitment generation unit 150. The storage unit 103 stores the random number r in a secret (s135). The unsealing information calculation unit 140 calculates unsealing information H = h ₂ ^r (s140). Thereby, the unsealing information H becomes a source of difficulty in the discrete logarithm problem. The opening information calculation unit 140 receives the generation source h ₂ and the random number r of G ₂ and outputs the opening information H = h ₂ ^r .

<Commitment generator 150>
The commitment generation unit 150 calculates C = g ^m h ₁ ^r from g, h ₁ and r and the information m to be committed, and outputs this as a commitment (s150). The commitment generation unit 150 receives the random number r from the random number generation unit 130, the generation source g and h ₁ of G ₁ from the commitment key generation unit 120, and the information m, and outputs the commitment C. Information mεZ _q, which is data stored in an auxiliary storage device or memory, or data input from an input interface, keyboard, mouse, or the like.

The bit commitment device 100 sends the commitment key ck to the registration device 300 and the commitment C to the verification device 200 (s153). At the same time as sending or after sending, the information M including the information m and the opening information H are sent to the verification device 200 (s155). Note that the information M including the information m may be, for example, the information m itself (that is, M = m) or g ^m (that is, M = g ^m ). When the information M = g ^m is set, an information changing unit (not shown) may be provided, and the information changing unit may receive the generation source g and the information ^m , calculate M = g ^m , and output M. When M = g ^m , due to the difficulty of the discrete logarithm problem, the verification apparatus 200 cannot know m even when M is received. At this time, the bit comment device 100 can convince the verification device 200 that the commitment can be opened while the information m is kept secret. As in Non-Patent Document 1, once committed C can be opened only with one piece of information M and opening information H. Therefore, the bit commitment device 100 cannot falsify the information M after sending the commitment C to the verification device 200 (s153) and before sending the information M and the opening information H to the verification device 200 (s155). . Note that either the calculation of opening information (s140) or the generation of commitment (s150) may be performed first, but if the commitment C is not transmitted first, the sender holds the message m at a certain point. The effect of convincing the recipient later cannot be obtained.

[Verification device 200]
FIG. 5 shows a configuration example of the verification apparatus 200. FIG. 6 is a diagram illustrating an example of a processing flow of the verification apparatus 100. The verification device 200 includes a communication unit 201, a storage unit 203, a control unit 205, and a determination unit 220.

<Control unit 205, communication unit 201, and storage unit 203>
The verification apparatus 200 according to the present embodiment executes each process under the control of the control unit 205. The verification device 200 receives the commitment key ck from the registration device 300 and the commitment C, information M, and unsealing information H from the bit commitment device. For example, the communication unit 201 communicates with the registration device 300 and the verification device 100. The commitment key ck is received from the registration device 300 (s201). The commitment C is received from the bit commitment device 100 (s202a), and at the same time or thereafter, the information M and the unsealing information H are received from the bit commitment device 100 (s202b). The storage unit 203 stores commitment C, commitment key ck, information M, and unsealing information H (s203).

<Determining unit 220>
The determination unit 220 determines whether or not the following equation (11) is satisfied (s220).
e (C / g ^m , h ₂ ) = e (h ₁ , H) (11)
When it is established, it is determined as pass (s223), and when it is not satisfied, it is determined as reject (s225). The determination unit 220 receives the commitment key ck, the commitment C, the unsealing information H, and the information M (m or g ^m ) through the communication unit 201 or through the communication unit 201 and the storage unit 203.

Hereinafter, the verification method will be described. Equation (11) is obtained from C = g ^m h ₁ ^r and H = h ₂ ^r .
e (g ^m h ₁ ^r / g ^m , h ₂ ) = e (h ₁ , h ₂ ^r ) (11) ′
It can be expressed as. Due to the nature of the pairing, the equation is established only when m and r are correct, and the verification apparatus 200 cannot know the information m when the commitment C is received as in the prior art. On the other hand, the bit commitment device 100 cannot falsify the information m after sending the commitment C to the verification device 200. Further, when the information M is g ^m , it is possible to convince a third party that the commitment C can be opened while the information m is kept secret as well as the random number r.

With such a configuration, the bit commitment method can be efficiently used as a component of various other cryptographic protocols. For example, when the bit commitment method of the present invention is used, since the unsealing information H = h ₂ ^r is an element of the group G in which the discrete logarithm problem is difficult, an efficient non-interactive zero knowledge proof using pairing is obtained. Can be configured. As the group G, for example, a group formed by an elliptic curve can be used.

<Hardware configuration>
FIG. 7 is a block diagram illustrating a hardware configuration of the bit commitment device 100 according to the present embodiment. The verification device 200 and the registration device 300 have the same configuration.

  As illustrated in FIG. 7, the bit commitment device 100, the verification device 200, and the registration device 300 in this example are respectively a CPU (Central Processing Unit) 11, an input unit 12, an output unit 13, an auxiliary storage device 14, and a ROM (Read Only memory (RAM) 15, random access memory (RAM) 16, and bus 17 are included.

  The CPU 11 in this example includes a control unit 11a, a calculation unit 11b, and a register 11c, and executes various calculation processes according to various programs read into the register 11c. The input unit 12 is an input interface for inputting data, a keyboard, a mouse, and the like, and the output unit 13 is an output interface for outputting data. The auxiliary storage device 14 is, for example, a hard disk, an MO (Magneto-Optical disc), a semiconductor memory, or the like, and a program area in which programs for causing the computer to function as the bit commitment device 100, the verification device 200, and the registration device 300 are stored. 14a and a data area 14b for storing various data. The RAM 16 is an SRAM (Static Random Access Memory), a DRAM (Dynamic Random Access Memory), or the like, and has a program area 16a in which the above program is stored and a data area 16b in which various data are stored. The bus 17 connects the CPU 11, the input unit 12, the output unit 13, the auxiliary storage device 14, the ROM 15, and the RAM 16 in a communicable manner.

  In addition, as a specific example of such hardware, a server apparatus, a workstation, etc. other than a personal computer can be illustrated, for example.

<Program structure>
As described above, each program for executing the processing of the bit commitment device 100, the verification device 200, and the registration device 300 of the present embodiment is stored in the program areas 14a and 16a. Each program constituting the bit commitment program, the verification program, and the registration program may be described as a single program sequence, or at least some of the programs may be stored in the library as separate modules. In addition, each program may realize each function alone, or each program may read each other library to realize each function.

<Cooperation between hardware and program>
The CPU 11 (FIG. 7) writes the above-described program stored in the program area 14 a of the auxiliary storage device 14 in the program area 16 a of the RAM 16 in accordance with the read OS (Operating System) program. Similarly, the CPU 11 writes various data stored in the data area 14 b of the auxiliary storage device 14 in the data area 16 b of the RAM 16. The address on the RAM 16 where the program and data are written is stored in the register 11c of the CPU 11. The control unit 11a of the CPU 11 sequentially reads these addresses stored in the register 11c, reads a program and data from the area on the RAM 16 indicated by the read address, causes the calculation unit 11b to sequentially execute the operation indicated by the program, The calculation result is stored in the register 11c.

  3 and 5 are block diagrams illustrating functional configurations of the bit commitment device 100 and the verification device 200 configured by reading and executing the above-described program in the CPU 11 as described above.

  Here, the storage units 103 and 203 correspond to any one of the auxiliary storage device 14, the RAM 16, the register 11 c, other buffer memory and cache memory, or a storage area using these in combination. The communication unit 101, the storage unit 103, the control unit 105, the commitment key generation unit 120, the random number generation unit 130, the unsealing information generation unit 140, and the commitment generation unit 150 execute a bit commitment program on the CPU 11. It is comprised by doing. The communication unit 201, the storage unit 203, the control unit 205, and the determination unit 220 are configured by causing the CPU 11 to execute a verification program.

  In addition, the bit commitment device 100, the verification device 200, and the registration device 300 according to the present embodiment execute each process under the control of the control units 105, 205, and 305.

Only parts different from the first embodiment will be described. The bit commitment verification system 1000 according to the second embodiment processes a plurality of configurations shown in the first embodiment in parallel and combines both sides of the equation by multiplication, thereby obtaining a plurality of pieces of information m _i (where 1 ≦ i ≦ n, where n represents the number of pieces of information). Further, the bit lengths of the information m ₁ , m ₂ ,..., _Mn may be the same or different.

[Bit commitment verification system 1000]
The bit commitment verification system 1000 includes a registration device 300, a bit commitment device 1100, and a verification device 1200.

Bit Commitment device 1100, in order to produce a commitment C for more information _{m i,} to the registration device 300, and requests the public parameter v. The registration device 300 sends v to the bit commitment device 1100. The bit commitment device 1100 generates a commitment key ck from the public parameter v and sends it to the registration device 300. The registration device 300 registers and discloses the commitment key ck. Further, a plurality of information _{m i,} using a commitment key ck and a plurality of random number _{r i,} to produce a commitment C. The bit commitment device 1100 sends the commitment C to the verification device 1200. After simultaneous or sent Sending, by using a random number r _i, and generates the unsealing information H, sends the information M and the unsealing information H including information m _i to the verification apparatus 1200.

The verification device 1200 requests the registration device 300 for a commitment key ck corresponding to the commitment C. The registration device 300 sends the commitment key ck to the verification device 1200. Verification apparatus 1200, the commitment C, information M, using a commitment key ck, verifies whether falsification and spoofing or the like is not performed, have indeed commitment C information from the time sent is m _i is falsification Make sure there is no. Hereinafter, details of each device and each process will be described.

[Bit commitment device 1100]
The bit commitment apparatus 1100 includes a communication unit 101, a storage unit 1103, a control unit 105, a commitment key generation unit 120, a random number generation unit 1130, an unsealing information generation unit 1140, and a commitment generation unit 1150.

<Random number generation unit 1130, storage unit 1103, and unsealing information calculation unit 1140>
The random number generation unit 1130 generates a plurality of random numbers r _i belonging to Z _q . The random number r _i is output to the unsealing information calculation unit 1140 and the commitment generation unit 1150. The storage unit 1103 stores the random number r _i in secret. Unsealing information calculation unit 1140 calculates the unsealing information ^{_{H = Π n i = 1 h}} 2 ri ( where the ri, which means that the random number _{r i).} The unsealing information calculation unit 1140 receives the generation source h ₂ from the commitment key generation unit 120 and the random number r _i from the random number generation unit 130, and outputs unsealing information H = Π ⁿ _{i = 1} h ₂ ^ri .

<Commitment generator 1150>
Commitment generating unit 1150, g, and _{^{C = Π n i = 1 g}} mi h 1 ri calculated from _{h 1} and _{r i} and committed information _{m i,} and outputs it as commitment (s150). Commitment generating unit 1150, a generator g in _{G 1} from commitment key generating unit 120, a _{h 1,} a random number _{r i} from the random number generation unit 130, and is input information _{m i,} and outputs the commitment C. Note that the information m _i εZ _q .

The bit commitment device 1000 sends the commitment key ck to the registration device 300 and the commitment C to the verification device 1200. After simultaneous or send and send, send the information M and opening information H including the information m _i to the verification device 1200. Note that the information M including information _{m i,} for example, information _{m i} itself _{(i.e., M = (m 1, m} 2, ..., may be a _{m ^n),} may be a ^{g mi} ( That is, M = (g ^m1 , g ^m2 ,..., G ^mn ), or may be the total product of g ^mi (that is, M = ^{ｎ n} _{i = 1} g ^mi ).

By adopting such a configuration, the same effect as in the first embodiment can be obtained. Furthermore, since the bit commitment C can be generated for a plurality of pieces of information m _i (1 ≦ i ≦ n), compared to the case where a plurality of bit commitments are created for a plurality of pieces of information by the method of the first embodiment. , Processing can be reduced. In addition, the information amount and communication amount of bit commitment can be reduced.

[Verification apparatus 1200]
The verification device 1200 includes a communication unit 201, a storage unit 203, a control unit 205, and a determination unit 220.

<Determining unit 220>
The determination unit 220 determines whether or not the following equation (21) is established (s220).
e (C / Π ⁿ _{i = 1} g ^mi , h ₂ ) = e (h ₁ , H) (21)
When it is established, it is determined as pass (s223), and when it is not satisfied, it is determined as reject (s225).

Hereinafter, the verification method will be described. Equation (11) is obtained from C = Πg ^mi h ₁ ^ri and H = Π ⁿ _{i = 1} h ₂ ^ri .
e (Π ⁿ _{i = 1} g ^mi h ₁ ^ri / Π ⁿ _{i = 1} g ^mi , h ₂ ) = e (h ₁ , ^{ｎ n} _{i = 1} h ₂ ^ri ) (21) ′
It can be expressed as. Due to the nature of the pairing, when all m _i and r _i is correct only holds equality, it is possible to obtain the same effects as the first embodiment. Furthermore, by combining both sides of the equation by multiplication, the processing can be reduced as compared to verifying a plurality of commitments by the method of the first embodiment.

1 is a diagram illustrating a configuration example of a bit commitment verification system 1. FIG. The figure which shows an example of the sequence diagram of the bit commitment verification system. 1 is a diagram illustrating a configuration example of a bit commitment device 100. FIG. The figure which shows an example of the processing flow of the bit commitment apparatus. The figure which shows the structural example of the verification apparatus. The figure which shows an example of the processing flow of the verification apparatus. 1 is a block diagram illustrating a hardware configuration of a bit commitment device 100 according to a first embodiment.

Explanation of symbols

1 bit commitment verification system 100 bit commitment device 200 verification device 300 registration device 101, 201 communication unit 103, 203 storage unit 105, 205 control unit 120 commitment key generation unit 130 random number generation unit 140 unsealing information calculation unit 150 bit commitment generation unit 220 Judgment part

Claims (10)

A bit commitment verification system comprising a registration device, a bit commitment device, and a verification device,
The q is a prime _number, G _1, G 2, the _{G T} as a group of order q, e bilinear map e: and _{G 1 × G 2 → G T} , the public parameter _{v = (q, G 1,} G 2, G _T , e)
The bit comments apparatus, the generator g and h ₁ from G _1, the origin h ₂ from the G _2, randomly selected, and commitment key generating unit for generating a commitment key ck using these origin ,
A random number generator for generating random numbers r _i belonging to Z _q (where 1 ≦ i ≦ n, where n represents the number of pieces of information m);
The public parameter v and the random number r _i are stored, in particular the random number r _i is stored secretly;
Wherein g, compute the _{h 1} and _{r i} and C = Π ⁿ _i = ¹ from the information _{m i} committing g _mi ^{h 1 ri,} and commitment generator outputting this as commitments,
An unsealing information calculation unit that calculates unsealing information H = Π ⁿ _{i = 1} h ₂ ^ri ,
The verification device includes a storage unit for the commitment key ck, the information m information including _i M, the unsealing information H and commitments C are stored,
Equation _{^{e (C / Π n i =}} 1 g mi, h 2) = e (h 1, H) , it is determined whether or not satisfied, the pass if satisfied, fail if not satisfied And a determination unit
The registration device includes a storage unit that stores the public parameter v and the commitment key ck,
The bit commitment device receives the public parameter v from the registration device, sends the commitment key ck to the registration device, the commitment C to the verification device, and sends the commitment C at the same time or after sending the information. M and opening information H are sent to the verification device,
The verification device receives the commitment key ck from the registration device, and the commitment C, the information M, and the unsealing information H from the bit commitment device.
Bit commitment verification system characterized by that. The bit commitment verification system according to claim 1,
n = 1,
Bit commitment verification system characterized by The q is a prime _number, G _1, G 2, the _{G T} as a group of order q, e bilinear map e: and _{G 1 × G 2 → G T} , the public parameter _{v = (q, G 1,} G 2, G _T , e)
The generator g and h ₁ from G _1, the origin h ₂ from the G _2, randomly selected, and commitment key generating unit for generating a commitment key ck using these origin,
A random number generator for generating random numbers r _i belonging to Z _q (where 1 ≦ i ≦ n, where n represents the number of pieces of information m);
The public parameter v and the random number r _i are stored, in particular the random number r _i is stored secretly;
Wherein g, compute the _{h 1} and _{r i} and C = Π ⁿ _i = ¹ from the information _{m i} committing g _mi ^{h 1 ri,} and commitment generator outputting this as commitments,
An unsealing information calculation unit that calculates unsealing information H = Π ⁿ _{i = 1} h ₂ ^ri ,
Receiving the public parameter v from the registration device, the to commitment key ck registration device, wherein the commitment C a verification apparatus, feed, after simultaneous or sent Sending commitment C, information M and opening including the information m _i Sending information H to the verification device;
A bit commitment device characterized by that. The q is a prime _number, and a group of order q the _{G 1, G 2, G T} , by the e linear map e: and _{G 1 × G 2 → G T} ,
A storage unit commitment key ck, information M including information m _i, unsealing information H and commitments C are stored,
Equation _{^{e (C / Π n i =}} 1 g mi, h 2) = e (h 1, H) , it is determined whether or not satisfied, the pass if satisfied, fail if not satisfied And a determination unit
Receiving the commitment key ck from a registration device and the commitment C, the information M and the unsealing information H from a bit commitment device;
A verification apparatus characterized by that. A bit commitment verification method using a registration device, a bit commitment device, and a verification device,
The q is a prime _number, G _1, G 2, the _{G T} as a group of order q, e bilinear map e: and _{G 1 × G 2 → G T} , the public parameter _{v = (q, G 1,} G 2, G _T , e)
The bit commitment device receiving the public parameter v from the registration device;
The bit comments apparatus, the generator g and h ₁ from G _1, the origin h ₂ from the G _2, randomly selected, and commitment key generating step of generating a commitment key ck using these origin ,
The bit comment device sending the commitment key ck to the registration device;
The registration device registering and releasing the commitment key ck;
A random number generating step in which the bit comment device generates a random number r _i belonging to Z _q (where 1 ≦ i ≦ n, where n represents the number of pieces of information m);
A storage step wherein the bit comment device stores the public parameter v and the random number r _i, in particular random number r _i is stored in a secret,
The bit comments apparatus, wherein g, calculated from _{h 1} and _{r i} and committed information ^{_{m i C = Π n i =}} 1 g mi h 1 ri, and commitment generating step of outputting this as commitments,
The bit comment device sends the commitment C to a verification device;
The bit comment device calculates an opening information H = Π ⁿ _{i = 1} h ₂ ^ri ;
The bit comments apparatus, after the simultaneous or sent when sending the commitment C, a step of sending information M and the unsealing information H including the information m _i to the verification device,
The verification device receives the commitment C from the bit commitment device;
The verification device receiving the commitment key ck from the registration device;
The verification device receives the information M and the unsealing information H from the bit commitment device;
A storage step in which the verification device stores the commitment key ck, the information M, the opening information H, and the commitment C;
The verification device, the equation _{^{e (C / Π n i =}} 1 g mi, h 2) = e (h 1, H) , it is determined whether or not satisfied, the pass if satisfied, not satisfied And a determination step for rejecting the case,
A bit commitment verification method characterized by that. The bit commitment verification method according to claim 5,
n = 1,
Bit commitment verification method characterized by The q is a prime _number, G _1, G 2, the _{G T} as a group of order q, e bilinear map e: and _{G 1 × G 2 → G T} , the public parameter _{v = (q, G 1,} G 2, G _T , e)
A bit commitment device receiving the public parameter v from a registration device;
The bit comments apparatus, the generator g and h ₁ from G _1, the origin h ₂ from the G _2, randomly selected, and commitment key generating step of generating a commitment key ck using these origin ,
The bit comment device sending the commitment key ck to the registration device;
A random number generating step in which the bit comment device generates a random number r _i belonging to Z _q (where 1 ≦ i ≦ n, where n represents the number of pieces of information m);
A storage step wherein the bit comment device stores the public parameter v and the random number r _i, in particular random number r _i is stored in a secret,
The bit comments apparatus, wherein g, calculated from _{h 1} and _{r i} and committed information ^{_{m i C = Π n i =}} 1 g mi h 1 ri, and commitment generating step of outputting this as commitments,
The bit comment device sends the commitment C to a verification device;
The bit comment device calculates an opening information H = Π ⁿ _{i = 1} h ₂ ^ri ;
The bit comments apparatus, after the simultaneous or sent when sending the commitment C, a step of sending information M and the unsealing information H including the information m _i to the verification device,
Having
A bit commitment method characterized by that. The q is a prime _number, G _1, G 2, the _{G T} as a group of order q, e bilinear map e: and _{G 1 × G 2 → G T} , the public parameter _{v = (q, G 1,} G 2, G _T , e)
The verification device receives a commitment C from the bit commitment device;
The verification device receives a commitment key ck from a registration device;
The verification device receives information M and unsealing information H from the bit commitment device;
A storage step in which the verification device stores the commitment key ck, the information M, the opening information H, and the commitment C;
The verification device, the equation _{^{e (C / Π n i =}} 1 g mi, h 2) = e (h 1, H) , it is determined whether or not satisfied, the pass if satisfied, not satisfied And a determination step for rejecting the case,
A verification method characterized by that.   A bit commitment program for causing a computer to function as the bit commitment device according to claim 3.   A verification program for causing a computer to function as the verification device according to claim 4.

Images