WO2007091531A2 - 証明検証システム、証明装置、検証装置、証明検証方法、およびプログラム - Google Patents

証明検証システム、証明装置、検証装置、証明検証方法、およびプログラム Download PDF

Info

Publication number
WO2007091531A2
WO2007091531A2 PCT/JP2007/051959 JP2007051959W WO2007091531A2 WO 2007091531 A2 WO2007091531 A2 WO 2007091531A2 JP 2007051959 W JP2007051959 W JP 2007051959W WO 2007091531 A2 WO2007091531 A2 WO 2007091531A2
Authority
WO
WIPO (PCT)
Prior art keywords
commit
value
response
proof
challenge
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2007/051959
Other languages
English (en)
French (fr)
Other versions
WO2007091531A1 (ja
Inventor
Isamu Teranishi
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Priority to US12/278,874 priority Critical patent/US20100169643A1/en
Priority to EP07708077A priority patent/EP1986105A4/en
Priority to JP2007557834A priority patent/JP4775597B2/ja
Publication of WO2007091531A1 publication Critical patent/WO2007091531A1/ja
Publication of WO2007091531A2 publication Critical patent/WO2007091531A2/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3236—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using cryptographic hash functions
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3271—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response

Definitions

  • Certification verification system certification device, verification device, certification verification method, and program
  • the present invention enables a proof of knowing some of a plurality of pieces of information, and a proof verification system, a proof device, and a verification for enabling verification of the validity of the proof
  • the present invention relates to an apparatus, a proof verification method, and a program for causing a computer to execute the method.
  • a protocol for proving that an information processing device called a proof device knows secret information satisfying some property to another information processing device called a verification device is called "knowledge proof”.
  • the verification device verifies the validity of the proof performed by the verification device and determines whether it is valid or not.
  • the knowledge proofing system is used as a component in creating various cryptographic protocols.
  • Direct application examples include authentication and signature methods. Both the authentication method and the signature method are technologies used to prove the identity of others on the Internet.
  • a certain type of authentication method and signature method has been put into practical use as IPSec (Security Architecture for Internet Protocol) and has high industrial utility value.
  • n secrets be x_l,..., x_n.
  • Cramer's knowledge proof method is a combination of x-1 knowledge proof method, x-2 knowledge proof method, ..., x-n knowledge proof method Can be used. However, it is possible to use the knowledge proof method of Cramer et al. X-1 knowledge proof method, X-2 knowledge proof method, ... x-n knowledge proof method Only when the following conditions 1 and 2 are satisfied.
  • x-1 knowledge proof method, X-2 knowledge proof method, ⁇ -n knowledge proof method is a 3-move public coin proof method.
  • the knowledge proofing method such as Cramer can be used only when the above two conditions are satisfied. In addition, the same effect as the proof method of knowledge such as Cramer is obtained, and it is necessary. It is necessary to make a method with fewer conditions.
  • An object of the present invention has been made in view of the above problems, and is a proof verification system, a proof device, a verification device, a proof verification method, and a proof verification method that enable verification of secret data retention verification more quickly. And a program for causing a computer to execute the method.
  • a proof verification system of the present invention comprises:
  • n secret data m (m ⁇ n) secret data X— ⁇ i— 1 ⁇ ,..., x— ⁇ i— m ⁇ , the element y— 1,..., y—n , And a proof device storage unit storing cyclic group data including n elements, and an identifier i ⁇ 1,...
  • a proof device including a proof device control unit for transmitting
  • a verifier storage unit that is connected to a proving device in a communicable manner and stores a plurality of random numbers and elements y—1,..., Y—n, and the proving device power is also a commit value Commit— 1,. , Comm it—
  • the selected random number c is sent as a challenge value to the proving device, and the elements of the cyclic group s— 1,..., S—n and the response value Response— 1,. ..., Response—
  • a verification device including a verification device control unit that does not accept the certification by
  • proof verification system of the present invention is
  • n secret data m (m ⁇ n) secret data X— ⁇ i— 1 ⁇ ,..., x— ⁇ i— m ⁇ , elements y— 1,..., y— n Is different from any of the identifiers i_l, ..., i_m for the certifying device storage unit storing the data of the cyclic group including n elements and the data of the group including a plurality of elements, and the n secret data
  • the response value Response—i is calculated using the range value Challenge—i, y—i, Commit—i, and Challenge—i, and the elements s—1,..., S—n and the response value Response— 1,..., Response—Proof device controller that sends n to the verification device
  • a verification device comprising:
  • a verification device storage unit that is communicably connected to the proving device and stores data of a group including a plurality of elements, and a group power that includes a plurality of elements.
  • the group element c—2 including a plurality of elements and the commit value Commit—1,... c-1 is transmitted to the proving device, and when the elements of the cyclic group s—1,..., s—n and the response value Response—1,..., Respon Se _n are received by the proving device, c_l multiplied by c_2 is obtained as c, and s_l, ..., s --n verifies whether or not the power is a secret sharing generated from the value c by a valid method.
  • the hash value of the element s—i is the challenge value Challenge—i
  • the proof text of the pair (Commit_i, Challenge—i, Response—i) is the valid proof text of y—i Verify whether there is A verification device that includes a verification device control unit that accepts a proof by a certification device if it is valid, and that does not accept a proof by a certification device if it is not valid;
  • proof verification system of the present invention is
  • n secret data m (m ⁇ n) secret data X— ⁇ i— 1 ⁇ ,..., x— ⁇ i— m ⁇ , the element y— 1,..., y—n , And a proof device storage unit storing cyclic group data including n elements, and an identifier i ⁇ 1,...
  • randomly select the cyclic group element s— ⁇ j_l ⁇ ,..., S— ⁇ j— p ⁇ from the proof device storage unit, and v l
  • the verification device storage unit that is connected to the proving device in a communicable manner and stores the set elements y ⁇ 1,..., Y ⁇ n, and the cyclic group elements s ⁇ 1,. , Commit value Commit— 1,..., Comm mit—n, and response value Response— 1,.
  • C is a hash value of data including s—1,..., S —n force S hash value c is verified whether it is a secret sharing generated by a legitimate method.
  • the verification device storage unit that is connected to the proving device in a communicable manner and stores the set elements y ⁇ 1,..., Y ⁇ n, and the cyclic group elements s
  • the commit value is also transmitted to the verification device, and the response value is transmitted from the verification device to the challenge device transmitted from the verification device to the verification device.
  • the device certificate is verified. In this way, it is possible to verify whether or not the proving device is properly holding the secret data. Therefore, it is possible to prove to the verification device that the proving device holds m of n secret data. It can be verified by satisfying one condition against the conventional knowledge proof method that requires two conditions.
  • FIG. 1 is a block diagram showing a configuration example of a proof verification system according to Embodiment 1.
  • FIG. 2 is a flowchart showing an operation procedure of data transmission / reception of the certification verification system in the first embodiment.
  • FIG. 3 is a flowchart showing an operation procedure of commit calculation means of the proving apparatus according to the first embodiment.
  • FIG. 4 is a flowchart showing an operation procedure of a challenge calculation means of the verification apparatus in the first embodiment.
  • FIG. 5 is a flowchart showing the operation procedure of the response calculation means of the proving apparatus according to the first embodiment.
  • FIG. 6 is a flowchart showing the operation procedure of the verification means of the verification apparatus in the first embodiment.
  • FIG. 7 is a block diagram showing a configuration example of a proof verification system in the second embodiment.
  • FIG. 8 is a flowchart showing an operation procedure of data transmission / reception of the certification verification system in the second embodiment.
  • FIG. 9 is a flowchart showing an operation procedure of data transmission / reception of the certification verification system in the second embodiment.
  • FIG. 10 is a flowchart showing an operation procedure of the challenge commit calculation means of the verification apparatus according to the second embodiment.
  • FIG. 11 is a flowchart showing an operation procedure of commit calculation means of the proving apparatus according to the second embodiment.
  • FIG. 12 is a flowchart showing the operation procedure of the challenge calculation means of the verification apparatus in the second embodiment.
  • FIG. 13 is a flowchart showing the operation procedure of the response calculation means of the proving apparatus in the second embodiment.
  • FIG. 14 is a flowchart showing the operation procedure of the verification means of the verification apparatus in the second embodiment.
  • FIG. 15 is a block diagram showing a configuration example of a proof verification system in the third embodiment.
  • FIG. 16 is a flowchart showing an operation procedure of data transmission / reception of the certification verification system in the third embodiment.
  • FIG. 17 is a flowchart showing the operation procedure of the proof sentence creating means of the proof device in the third embodiment.
  • FIG. 18 is a flowchart showing the operation procedure of the challenge calculation means of the proving apparatus in the third embodiment.
  • FIG. 19 is a flowchart showing the operation procedure of the verification means of the verification apparatus in the third embodiment.
  • ⁇ be a set. ( ⁇ , X, Func and ommit, Hash, FuncResponse, ChaliengeSpace, Verily, Simulator) 3-Move public coin proof system.
  • ChaliengeSpace is a set.
  • Hash is a hash function that takes a value in ChaliengeSpace.
  • (y, x) is the origin of Y X X
  • Challenge is the origin of ChaliengeSpace.
  • FuncResponse outputs Response when y, X, Commit, Challenge, State is input.
  • the challenge value Challenge is information for asking what kind of answer to the communication partner device, and generally a random number is known.
  • Commit value C The ommit is information related to the secret data held by the device itself and is sent to the device of the communication partner so that the secret data is not directly known.
  • Response value Response is information on the challenge value question and response to the challenge value challenge sent back to the transmission source device.
  • Simulator is a 3-move public coin proof system.
  • FuncCommit, Hash, FuncResponse, Verify, and 3 ⁇ 4imulator are said to be a public coin proof system of ⁇ 3 ⁇ M ⁇ bu that 3 ⁇ 4
  • the present invention can be used for any 3-move public coin certification scheme. However, in practice, it is desirable to use a 3-move public coin proof system for some relational expression R.
  • n be a natural number.
  • n be a natural number and k be a natural number less than or equal to n.
  • S ⁇ l, "-, n ⁇ , and let ⁇ be a subset of S that has more than k elements, where ⁇ is the access structure on S.
  • A ⁇ i— 1, ⁇ , ⁇ —m ⁇ be an element of ⁇ .
  • s— ⁇ i— 1 ⁇ ,..., s— ⁇ i— m ⁇ is the source of SharSp.
  • l n-m.
  • B ⁇ j_l,..., j_l ⁇ be the set excluding A from S.
  • c be the source of KeySp.
  • A ⁇ i— 1, ⁇ , ⁇ —m ⁇ be an element of ⁇ .
  • s— ⁇ i— 1 ⁇ ,..., s— ⁇ i— m ⁇ is the source of SharSp.
  • l n-m.
  • B ⁇ j_l,..., j_l ⁇ be the set excluding A from S.
  • c be the source of KeySp.
  • c be a C element and DomPar be FuncGen output.
  • Com and ComState are the outputs of Fun cCom when DomPar and c are input. At this time, if DomPar, c, Com, or ComState is input, FuncComVer outputs “accept”.
  • FIG. 1 is a block diagram showing an example of the configuration of the proof verification system of this embodiment.
  • the proof verification system includes a proof device 100 for performing proof and a verification device 200 for performing verification.
  • the proving device 100 and the verification device 200 are communicably connected via a communication network (not shown).
  • the proving device 100 includes a proving device control unit 102, a proving device storage unit 101, and a proving device communication unit (not shown).
  • the certification device control unit 102 includes a commit calculation unit 111 and a response calculation unit 112.
  • the verification device 200 includes a verification device control unit 202, a verification device storage unit 201, and a verification device communication unit (not shown).
  • the verification device control unit 202 includes a challenge calculation unit 211 and a response calculation unit 112.
  • the control unit of each device performs communication unit control, storage unit control, and data calculation processing.
  • the control unit is provided with a CPU (Central Processing Unit) that executes predetermined processing according to a program and a memory for storing the program.
  • the commit calculation means 111, the response calculation means 112, the challenge calculation means 211, and the verification means 212 are virtually configured in the computer by the CPU executing the program.
  • the communication network for example, the Internet or a LAN (Local Area Network) can be used.
  • the communication network may be either wired or wireless, or a combination of wired and wireless.
  • FIG. 1 in order to facilitate understanding of the information flow between devices, the communication unit of each device is not shown in the figure.
  • a hard disk, a semiconductor memory, or the like can be used for the storage unit.
  • Hash be a hash function that takes values in G.
  • l l, ⁇ ⁇ ⁇ , n ⁇ ⁇ ; ⁇ T (Y 1, X 1, Func and ommit i, Hash i, FuncResponse ⁇ , and halle ngeSpace—i, Verify—i, Simulator—i) is a 3-move public coin proof system
  • n a natural number
  • p nm
  • H—i be a hash function from SharSp to ChallengeSpace—i.
  • Simulator—2 is the zero knowledge proof simulator. Since the zero knowledge proof simulator is the same as the prior art, a detailed description thereof is omitted here.
  • This X— ⁇ i—1 ⁇ ,..., ⁇ — ⁇ i—m ⁇ corresponds to m secret data out of n secret data.
  • Y elements y— 1,..., Y—n are stored in the verification device storage unit 201.
  • FIG. 2 is a flowchart showing the data transmission / reception operation.
  • Proof device 100 performs commit calculation means 111 (step 1101).
  • the certification device 100 transmits the output of the commit calculation means 111 to the verification device 200 using the certification device communication unit (step 1102).
  • the verification device 200 receives the output of the commit calculation means 111 using the verification device communication unit, and writes the received data into the verification device storage unit 201 (step 1103).
  • the verification device 200 performs challenge calculation means 211 (step 1104).
  • the verification device 200 outputs the challenge calculation means 211 using the verification device communication section. Is transmitted to the certification device 100 (step 1105).
  • the certification device 100 receives the output of the challenge calculation means 211 using the certification device communication unit, and writes the received data in the certification device storage unit 101 (step 1106).
  • Proof device 100 performs response calculation means 112 (step 1107).
  • the verification device 100 transmits the output of the response calculation means 112 to the verification device 200 using the verification device communication unit (step 1108).
  • the verification device 200 receives the output of the response calculation means 112 using the verification device communication unit, and writes the received data in the verification device storage unit 201 (step 1109).
  • the verification apparatus 200 performs verification means 212 (step 1110).
  • FIG. 3 is a flowchart showing an operation procedure of the commit calculation means 111.
  • FIG. 4 is a flowchart showing the operation procedure of the challenge calculation means 211.
  • FIG. 5 is a flowchart showing an operation procedure of the response calculation means 112.
  • Commit—1 ′ and Commit—n are read from the certification device storage unit 101 (step 1 401).
  • Resl-2.c is read from the certification device storage unit 101 (step 1402).
  • the verification apparatus 200 performs means Verl-l,, Verl-4 described below.
  • FIG. 6 is a flowchart showing the operation procedure of the verification means 212.
  • Verl-1.c, s_l,..., S—n and Response—1,..., Response—n are read from the verification device storage unit 201 (step 1501).
  • Verl-4. 1 1, "'' nf, Verify (y ⁇ , ommit i, Challenge ⁇ , Response I will count.
  • FIG. 7 is a block diagram showing a configuration example of the proof verification system of this embodiment.
  • the proof verification system includes a proof device 100 for performing proof and a verification device 200 for performing verification.
  • the proving device 100 and the verification device 200 are communicably connected via a communication network (not shown).
  • the certification device 100 includes a certification device control unit 102, a certification device storage unit 101, and a certification device communication unit (not shown).
  • the proving device control unit 102 includes commit calculation means 114 and response calculation means 115.
  • the verification device 200 includes a verification device control unit 202, a verification device storage unit 201, and a verification device communication unit (not shown).
  • the verification device control unit 202 includes a challenge commit calculation unit 210, a challenge calculation unit 213, and a verification unit 214.
  • the control unit of each device is provided with a CPU that executes predetermined processing according to a program and a memory for storing a program.
  • the commit calculation means 114, the response calculation means 115, the challenge commit calculation means 210, the challenge calculation means 213, and the verification means 214 are virtually configured in the computer by the CPU executing the program. Other configurations are the same as those in the first embodiment, and thus detailed description thereof is omitted.
  • Embodiment 1 The same premise as in Embodiment 1 is imposed. In addition, the following assumptions 1 and 2 are imposed.
  • ChallengeSp is a group.
  • the certification device 100 and the verification device 200 perform data transmission / reception in the order of Prot2-l, ', Prot2-13, which will be described below.
  • 8 and 9 are flowcharts showing an operation procedure of data transmission / reception.
  • the verification device 200 performs challenge commit calculation means 210 (step 2101).
  • the verification device 200 transmits the output of the challenge commit calculation means 210 to the verification device 100 using the verification device communication unit (step 2102).
  • the proving apparatus 100 receives the output of the challenge commit calculation means 210 using the proving apparatus communication unit, and writes the received data into the proving apparatus storage unit 101 (step 2103).
  • Proof device 100 performs commit calculation means 114 (step 2104).
  • the certification device 100 transmits the output of the commit calculation means 114 to the verification device 200 using the certification device communication unit (step 2105).
  • the verification device 200 receives the output of the commit calculation means 114 using the verification device communication unit, and writes the received data in the verification device storage unit 201 (step 2106).
  • the verification apparatus 200 performs challenge calculation means 213 (step 2107).
  • the verification device 200 transmits the output of the challenge calculation means 213 to the verification device 100 using the verification device communication unit (step 2108).
  • the certification device 100 receives the output of the challenge calculation means 213 using the certification device communication unit, and writes the received data in the certification device storage unit 101 (step 2109).
  • Proof device 100 performs response calculation means 115 (step 2110).
  • Proof device 100 transmits the output of response calculation means 115 to verification device 200 using the proof device communication unit (step 2111).
  • the verification device 200 receives the output of the response calculation means 115 using the verification device communication unit, and writes the received data in the verification device storage unit 201 (step 2112).
  • Verification apparatus 200 performs verification means 214 (step 2113).
  • the verification apparatus 200 performs the following means ChaCom2-l, '", ChaCom2-5.
  • FIG. 10 is a flowchart showing the operation procedure of the challenge commit calculation means 210.
  • ChaCom2-l. DomPar is read from the verification device storage unit 201 (step 2201).
  • FIG. 11 is a flowchart showing the operation procedure of the commit calculating means 114.
  • Com2-3. C—2 is written in the certification device storage unit 101 (step 2303).
  • Com2-4. (C_2, Commit_l, '", Commit_n) is output (step 2304).
  • FIG. 12 is a flowchart showing the operation procedure of the challenge calculating means 213.
  • Cha2-1 Read c-l and ComState from the verification device storage unit 201 (step 2401).
  • Cha2-2. C— 1, ComState is output (step 2402).
  • FIG. 13 is a flowchart showing the operation procedure of the response calculation means 115.
  • Res2— 1. Commit 1 1,..., Commit 1 n, c 1 l, c 1 2, DomPar, Com, ComState Read from the certificate storage unit 101 (step 2501).
  • C c_lc_2 is calculated (step 2503).
  • Res2-4. Resl-3, “′”, Resl-7 of Embodiment 1 are performed using c (step 2504).
  • FIG. 14 is a flowchart showing the operation procedure of the verification means 214.
  • Ver2-2. C c—lc—2 is calculated (step 2602).
  • ⁇ 1, ⁇ , ⁇ , Verify (y ⁇ 1, do ommit ⁇ i, Challenge ⁇ i, Response ⁇ ly add.
  • 1 1, ⁇ ⁇ ⁇ , !!
  • Verify (y 1 ⁇ , ommit 1 i, Challenge 1 i, Response 1 Accept if accept and exit, otherwise reject and exit (step 2605).
  • the verification device 200 executes the challenge commit calculation means 210 before receiving information from the verification device 100, so that the verification device 200 can perform data selection.
  • the influence of information from 100 is suppressed, and the confidentiality of confidential information stored in the certification device 100 is improved.
  • FIG. 15 is a block diagram showing a configuration example of the proof verification system of this embodiment.
  • the proof verification system includes a proof device 100 for performing proof and a verification device 200 for performing verification.
  • the proving device 100 and the verification device 200 are communicably connected via a communication network (not shown).
  • the certification device 100 includes a certification device control unit 102, a certification device storage unit 101, and a certification device communication unit (not shown).
  • the proof device control unit 102 is provided with a proof text creating means 110.
  • the certificate creating unit 110 includes a commit calculating unit 116, a challenge calculating unit 113, and a response calculating unit 117.
  • the verification device 200 includes a verification device control unit 202, a verification device storage unit 201, and a verification device communication unit (not shown).
  • the verification device control unit 202 includes a verification unit 215.
  • the control unit of each device is provided with a CPU that executes predetermined processing according to a program and a memory for storing a program.
  • the commit calculation means 116, the response calculation means 117, the challenge calculation means 113, and the verification means 215 are virtually configured in the computer by the CPU executing the program. Since other configurations are the same as those in the first embodiment, detailed description thereof is omitted.
  • HashCha be a hash function that takes a value in SharSp.
  • M be a bit string. Assume that the proving device 100 and the verification device 200 share M in advance. It doesn't matter how M was shared. M is a spare input, and M is set in various ways according to the purpose. You may choose an empty column as M. For example, the following 1 ', 6 can be set as M.
  • X elements X— ⁇ i— 1 ⁇ ,..., ⁇ — ⁇ i— m ⁇ , Y elements y— 1,..., ⁇ — n, and M are stored in the proving device storage unit 101. ing. Y elements y—1,..., Y—n, and M are stored in the verification device storage unit 201.
  • FIG. 16 is a flowchart showing an operation procedure of data transmission / reception.
  • Prot3-l. Proof device 100 performs proof sentence creation means 110 (step 3101).
  • the certification device 100 transmits the output of the certification sentence creation means 110 to the verification device 200 using the certification device communication unit (step 3102).
  • the verification device 200 receives the output of the proof sentence creation means 110 using the verification device communication unit, and writes the received data to the verification device storage unit 201 (step 3103).
  • the verification apparatus 200 performs verification means 215 (step 3104).
  • FIG. 17 is a flowchart showing the operation procedure of the certificate creating unit 110.
  • the proving apparatus 100 performs Comml-l, “′”, Coml- 7 of the commit calculation unit 111 of the first exemplary embodiment.
  • the proving apparatus 100 performs the following means Cha3-1 and Cha3-2 (Fig. 18).
  • the proving apparatus 100 performs Resl-l, “', Resl-6 of the response calculation unit 112 of the first embodiment.
  • FIG. 19 is a flowchart showing the operation procedure of the verification means 215.
  • the secret of the proof device 100 since the operation of the challenge calculation unit 113 in the proof device 100 has been improved so as not to be affected by the commit calculation unit 116, in addition to the effects of the first embodiment, the secret of the proof device 100 The confidentiality of information is improved, and the number of communications between the certification device 100 and the verification device 200 can be reduced.
  • proof verification method described in the first to third embodiments may be applied to a program for causing a computer to execute.
  • a component for creating various cryptographic protocols as a knowledge proofing method for a proof verification system, a proof device and a verification device, a proof verification method, and a program for causing a computer to execute the method of the present invention It can be used as an authentication method and signature method.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Storage Device Security (AREA)

Description

明 細 書
証明検証システム、証明装置、検証装置、証明検証方法、およびプログラ ム
技術分野
[0001] 本発明は、複数の情報のうちいくつかを知っていることの証明を可能にし、また、そ の証明の正当性の検証を可能にするための証明検証システム、証明装置および検 証装置と、証明検証方法と、その方法をコンピュータに実行させるためのプログラムと に関する。
背景技術
[0002] 証明装置と呼ばれる情報処理装置が検証装置と呼ばれる他の情報処理装置に何 らかの性質を満たす秘密情報を知っていることを証明するプロトコルを「知識の証明」 という。検証装置は証明装置の行った証明の正当性を検証し、正当であるかそうでな いかを判断する。
[0003] 知識の証明方式は様々な暗号プロトコルを作る際の部品として用いられている。直 接的な応用例として認証方式や署名方式がある。認証方式も署名方式も、インター ネット上で他の人に当人性を証明するために用いられる技術である。ある種の認証方 式、署名方式は IPSec(Security Architecture for Internet Protocol)として実用化さ れており、産業上の利用価値が高い。
[0004] 文献 (R.Cramer, I.Damgaara, ana B.bchoenmakers., Proofs of partial knowle dge and simplified design of witness hiding protocols , In CRYPTO '94, LNC S 2139, Springer- Verlag, 1994, pp. 174- 187 :以下では、この文献を文献 1と称 する）において、 Cramer等は、俗に「Orの証明」と呼ばれる知識の証明方式を提案し た。 nを自然数とし、 kを n以下の自然数とすると、この方式では、証明装置が n個の秘 密のうち少なくとも k個を知っていることを検証者に証明できる。
[0005] 「Orの証明」はある種の匿名性を持つ認証方式を実現するのに必要で、これも様々 な暗号プロトコルに応用されている。「Orの証明」は、例えば、文献（Isamu Teranishi, Jun Furukawa, and Kazue bako., "k— Times Anonymous Autnentication (Ext ended Abstract) ", In ASIACRYPT 2004, LNCS 3329, Springer— Verlag, 2004, pp. 308-322 :以下では、この文献を文献 2と称する）や文献 (寺西勇， 「離散対数 問題に tight安全でかつ計算量が少ない署名方式」， In Proceedings of the 2005 Symposium on Cryptography and Information Security, 3E3— 4, January 2005 : 以下では、この文献を文献 3と称する）で利用されている。文献 3は電子投票、電子 現金、匿名視聴といった応用を持つ方式であり、これも産業上の利用価値が高い。
[0006] また、 Cramer等は文献 1で、次のような一般的な知識の証明方式も提案して 、る。
あら力じめ「アクセス構造」（Douglas R. Stinson, 「暗号理論の基礎」，共立出版株 式会社， P355-356を参照）と呼ばれるものを決めておく。この方式では、証明装置は n個の秘密のうち複数個を知っていて、し力もその複数個は前述のアクセス構造を満 たすものであることを証明できる。
n個の秘密を x_l, … ，x_nとする。
Cramer等は、 X— 1, … ，χ—ηが満たす性質が同じである場合に対して知識の証明 方式を提案している。
Cramer等の知識の証明方式は、 x— 1の知識の証明方式、 x— 2の知識の証明方式、 · ··、 x—nの知識の証明方式を組み合わせることで、より一般の場合にも用いることが できる。し力し、 Cramer等の知識の証明方式を使うことができるのは、 x— 1の知識の 証明方式、 X— 2の知識の証明方式、 · ··、 x—nの知識の証明方式が以下の条件 1,2を 満たす場合のみである。
条件 1. x—1の知識の証明方式、 X— 2の知識の証明方式、 ·、χ— nの知識の証明 方式は 3-ムーブのパブリックコイン証明方式である。
条件 2. X— iの知識の証明方式で Challengeを選ぶ空間を ChallengeSpace— iとすると き、 ChallengeSpace— 1= · ··= ChallengeSpace— nでなければならない。
なお、「3-ムーブのパブリックコイン証明方式」および「Challenge」等の言葉の説明は
、後述の (定義)の章で行う。
発明の開示
[0007] Cramer等の知識の証明方式は、上述した 2つの条件を満たす場合にしか使うこと ができない。また、 Cramer等の知識の証明方式と同様な効果が得られ、かつ、必要と される条件がより少ない方式を作る必要がある。
[0008] 本発明の目的は、上記問題点に鑑みてなされたものであり、秘密データ保持の証 明をより速く検証可能にした証明検証システム、証明装置および検証装置と、証明検 証方法と、その方法をコンピュータに実行させるためのプログラムとを提供することに ある。
[0009] 上記目的を達成するための本発明の証明検証システムは、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータが格納された証明装 置記憶部、ならびに、 n個の秘密データに対する識別子 i—1, ···, i— mのいずれとも 異なる識別子を j— 1, ···, j_p(p= n-m)とし、証明装置記憶部から巡回群の元 s— {j_l}, ···, s— {j_p}をランダムに選び、 v=l, ···, pに対して各 s— {j_v}のハツシ ュ関数による値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して y— {j— v }と Challenge_{j_v}を入力とするゼロ知識証明のシミュレーションを行うことで、コミ ット値とレスポンス値の糸且（Commit一 {j一 1}, Response一 {j一 1}) , ···, (Commit_{ j一 p}， Response一 {j一 p}) 生成し、 u=l, ···, mに对して x一 {i一 u}と y一 {i一 u}を 用 ヽてコミット値 Commit― {i― u}を生成し、 Commit― {j― 1|, ···, Commit― {j― p) および Commit— {i—l}， ···， Commit— {i—m}力らなるコミット値 Commit— 1, ···, Commit_nを外部に送信し、外部力もチャレンジ値 cを受信すると、チャレンジ値 cお よび s_{j_l}， ···, s— {j_p}から残りの元 s— {i_l}， ···, s— {i_m}を生成し、 i= 1,···,ηに対して各 s— iにそのハッシュ値をチャレンジ値 Challenge— iとし、 y— i、 Comm it— iおよび Challenge— iを使ってレスポンス値 Response— iを算出し、元 s—1, ···, s —nとレスポンス値 Response— 1, ···, Response— nを外部に送信する証明装置制御 部を含む証明装置と、
証明装置と通信可能に接続され、複数の乱数および集合の元 y—1, ···, y—nが 格納された検証装置記憶部、ならびに、証明装置力もコミット値 Commit— 1,···, Comm it— nを受信すると、複数の乱数力 選択した cをチャレンジ値として証明装置に送信 し、巡回群の元 s— 1, ···, s—nおよびレスポンス値 Response— 1, ···, Response— n を証明装置から受信すると、 s—1, ···, s—nがチャレンジ値 cから正当な方法で生成 された秘密分散であるか否かを検証し、正当であれば、 i=l, ···, nに対して s— iのハ ッシュ値をチャレンジ値 Challenge― iとし、糸且 (Commit― i, Challenge― i, Response _i)による証明文が y—iの正当な証明文である力否かを検証し、正当である場合、証 明装置による証明を受理し、正当でない場合、証明装置による証明を受理しない検 証装置制御部を含む検証装置と、
を有する構成である。
また、本発明の証明検証システムは、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y— n、 n個の元を含む巡回群のデータおよび複数の元を含む群 のデータが格納された証明装置記憶部、ならびに、 n個の秘密データに対する識別 子 i_l, ···, i_mのいずれとも異なる識別子を j_l, ···, j_p(p= n- m)とし、外部 力もコミット値 Comを受信すると、コミット値 Comを証明装置記憶部に格納し、証明装 置記憶部から巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに選び、 v=l, ···, p に対して各 s—{j—v}のハッシュ関数による値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して元 y_{j_v}と Challenge_{j_v}を入力とするゼロ知識証明の シミュレーションを行うことで、コミット値とレスポンス値の組（Commit— {j—l}， Respo nse― ij― 1}) , ···, (Commit― {j― p;, Response― {j― p}) 生成し、 u=l, ···, m に対して x_{i_u}と y_{i_u}を用いてコミット値 Commit_{i_u}を生成し、 Commit 一 ij一 1}, ···, Commit一 {j一 およびし ommit一 {ι一 1}, ···, Commit一 {ι一 m}力 らなるコミット値 Commit— 1, ···, Commit— nを求め、複数の元を含む群からランダム に元 c— 2を選び、元 c— 2および Commit— 1, ···, Commit— nを外部に送信し、コミツ ト値 Comを算出するための、複数の元を含む群の元 c—1を外部力 受信すると、コミ ット値 Comが元 c—1の正当なコミットメントであるか否かを検証し、正当でない場合、 証明の続行を拒否し、正当である場合、 c— 1と c— 2を乗算した値 cを求め、 s_{j_l} , ···, s— {j_p}と値 cから残りの元 s— {i_l}， ···, s— {i— m}を生成し、 ί=1 ·,ηに 対して各 s—iにそのハッシュ値をチャレンジ値 Challenge— iとし、 y— i、 Commit— i、お よび Challenge— iを使ってレスポンス値 Response— iを算出し、元 s—1, ···, s— nとレ スポンス値 Response— 1, ···, Response— nを検証装置に送信する証明装置制御部 を含む証明装置と、
証明装置と通信可能に接続され、複数の元を含む群のデータが格納された検証装 置記憶部、ならびに、複数の元を含む群力 ランダムに元 c—1を選び、元 c— 1のコミ ット値 Comを算出して証明装置に送信し、複数の元を含む群の元 c— 2、およびコミツ ト値 Commit— 1, ···, Commit— nを証明装置から受信すると、元 c—1を証明装置に 送信し、巡回群の元 s— 1, ···, s—n、およびレスポンス値 Response— 1, ···, Respo nSe_nを証明装置カゝら受信すると、 c_lと c_2を乗算した値 cを求め、 s_l, ···, s —nが値 cから正当な方法で生成された秘密分散である力否かを検証し、正当であれ ば、 i=l, ···, nに対して元 s—iのハッシュ値をチャレンジ値 Challenge— iとし、組（Co mmit_i, Challenge— i, Response— i)による証明文が y—iの正当な証明文であるか 否かを検証し、正当である場合、証明装置による証明を受理し、正当でない場合、証 明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する構成である。
また、本発明の証明検証システムは、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータが格納された証明装 置記憶部、ならびに、 n個の秘密データに対する識別子 i—1, ···, i— mのいずれとも 異なる識別子を j— 1, ···, j_p(p= n-m)とし、証明装置記憶部から巡回群の元 s— {j_l}, ···, s— {j— p}をランダムに選び、 v=l, ···, pに対して各 s— {j— v}のハツシ ュ関数による値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して元 y— {j —v}と Challenge— {j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、 コミット値とレスポンス値の組（Commit— {j—l}， Response— {j—1}) , ···, (Commit 一 {j一 p}， Response一 {j一 p})を生成し、 u=l, ···, mに;^して x一 {i一 u}と y一 {i一 u }を用いてコミット値 Commit_{i_u}を生成し、 Commit_{j_l}， ···， Commit_{j —p}および Commit— {i—l}， ···， Commit— {i—m}力らなるコミット値 Commit— 1, ···, Commit― nを求め、 Commit― 1, ···, Commit― nを含むデータのノヽッシュ値を c とし、ハッシュ値 cと s— {j_l}， ···, s— {j_p}とから残りの元 s— {i_l}， ···, s_{i m}を生成し、 i=l, ···, nに対して各 s iにそのハッシュ値をチャレンジ値 Challenge — iとし、 y— i、 Commit— iおよび Challenge— iを使ってレスポンス値 Response— iを算 出し、元 s一 1, ···, s一 nとレスポンス値 Response一 1, ···, Response一 nを外咅 |5に送 信する証明装置制御部を含む証明装置と、
証明装置と通信可能に接続され、集合の元 y—1, ···, y—nが格納された検証装 置記憶部、ならびに、巡回群の元 s—1, ···, s—n、コミット値 Commit— 1, ···, Com mit—n、およびレスポンス値 Response— 1, ···, Response— nを証明装置から受信す ると、 Commit— 1, ···, Commit— nを含むデータのハッシュ値を cとし、 s—1, ···, s —n力 Sハッシュ値 cから正当な方法で生成された秘密分散であるか否かを検証し、正 当であれば、 i=l, ···, nに対して元 s—iのハッシュ値をチャレンジ値 Challenge— し 、組（Commit— i, Challenge— i, Response— i)による証明文が y—iの正当な証明文 であるか否かを検証し、正当である場合、証明装置による証明を受理し、正当でない 場合、証明装置による証明を受理しな!、検証装置制御部を含む検証装置と、 を有する構成である。
[0012] 本発明では、証明装置力もコミット値が検証装置に送信され、検証装置から証明装 置に送信されたチャレンジ値に対して証明装置カゝらレスポンス値が送信され、検証装 置で証明装置の証明文が検証される。このようにして、証明装置が秘密データを正 規に保持している力否かが検証可能となる。よって、証明装置が n個の秘密データの うち m個を保持していることを検証装置に証明可能となる。 2つの条件が必要な従来 の知識の証明方式に対し、 1つの条件を満たすことで検証できる。
図面の簡単な説明
[0013] [図 1]図 1は実施形態 1における証明検証システムの一構成例を示すブロック図であ る。
[図 2]図 2は実施形態 1における証明検証システムのデータ送受信の動作手順を示 すフローチャートである。
[図 3]図 3は実施形態 1における証明装置のコミット計算手段の動作手順を示すフロ 一チャートである。
[図 4]図 4は実施形態 1における検証装置のチャレンジ計算手段の動作手順を示す フローチャートである。 圆 5]図 5は実施形態 1における証明装置のレスポンス計算手段の動作手順を示すフ ローチャートである。 圆 6]図 6は実施形態 1における検証装置の検証手段の動作手順を示すフローチヤ ートである。
[図 7]図 7は実施形態 2における証明検証システムの一構成例を示すブロック図であ る。
圆 8]図 8は実施形態 2における証明検証システムのデータ送受信の動作手順を示 すフローチャートである。
圆 9]図 9は実施形態 2における証明検証システムのデータ送受信の動作手順を示 すフローチャートである。
圆 10]図 10は実施形態 2における検証装置のチャレンジコミット計算手段の動作手 順を示すフローチャートである。
[図 11]図 11は実施形態 2における証明装置のコミット計算手段の動作手順を示すフ ローチャートである。 圆 12]図 12は実施形態 2における検証装置のチャレンジ計算手段の動作手順を示 すフローチャートである。
圆 13]図 13は実施形態 2における証明装置のレスポンス計算手段の動作手順を示 すフローチャートである。
圆 14]図 14は実施形態 2における検証装置の検証手段の動作手順を示すフローチ ヤートである。
[図 15]図 15は実施形態 3における証明検証システムの一構成例を示すブロック図で ある。
[図 16]図 16は実施形態 3における証明検証システムのデータ送受信の動作手順を 示すフローチャートである。
圆 17]図 17は実施形態 3における証明装置の証明文作成手段の動作手順を示すフ ローチャートである。 圆 18]図 18は実施形態 3における証明装置のチャレンジ計算手段の動作手順を示 すフローチャートである。 [図 19]図 19は実施形態 3における検証装置の検証手段の動作手順を示すフローチ ヤートである。
符号の説明
[0014] 100 証明装置
101 証明装置記憶部
102 証明装置制御部
200 検証装置
201 検証装置記憶部
202 検証装置制御部
発明を実施するための最良の形態
[0015] (定義）
[3-ムーブのパブリックコイン証明方式]
Χ,Υを集合とす 。 (Υ, X, Funcし ommit, Hash, FuncResponse, ChaliengeSpace, Verily, Simulator)の証明文が次の性質 1 ', 7を満たすとき、（Υ, X, FuncCommit, Hash, FuncResponse, Verily, Simulator)を 3-ムーブのパブリックコイン証明方式 という。
1, 糸且 FuncCommit, Hash, FuncResponse, Simulator, Verifyは関数である。
2, ChaliengeSpaceは集合である。
3, FuncCommitは Y X Xの元を入力とし、データ Commitと Stateを出力する。
4, Hashは ChaliengeSpaceに値を取るハッシュ関数である。
5, (y,x)を Y X Xの元とし、 Challengeを ChaliengeSpaceの元とする。 FuncResponseは 、 y, X, Commit, Challenge, Stateが入力されると、 Responseを出力する。
6, Verifyは、 y, Commit, Challenge, Response力 S入力されると、 Acceptもしくは Reje ctを出力する。
7, Simulatorは、 Yの元が入力されると、糸且（Commit, Challenge, Response)を出力 する。
[0016] なお、チャレンジ値 Challengeは、通信相手の装置に対して、どのような回答をする かを試すための問いかけの情報であり、一般的には乱数が知られている。コミット値 C ommitは、自装置が保持する秘密データに関連している力 その秘密データが直接 わからないようにして、通信相手の装置に送る情報である。レスポンス値 Responseは、 チャレンジ値 Challengeの送信元の装置に対して返信する、チャレンジ値の問!、かけ に対する回答の情報である。
[3-ムーブのパブリックコイン証明方式の例]
qを素数とし、 Gを位数 qの有限群とし、 mを自然数とし、 H= G½とする。
(Y, X, FuncCommit, Hash, FuncResponse, し hallengeSpace, Verily, Simulator )を以下の 1,···, 8のように決めると、（Y, X, FuncCommit, Hash, FuncResponse, C hallengeSpace, Verily, Simulator)は 3-ムーブのパブリックコイン証明方式である。
1. Y=HXHとする。
2. Xを位数 qの巡回群 (Z/qZ)とする。
3. Cnallenge¾pace= (Z/qZ)とする。
4. y=((g_l, … ,g_m) , (h_l, … ，h— m))を Yの元とし、 xを Xの元とする。 YX Xの元（y, X)が入力されると、 FuncCommitは、（Z/qZ)の元 rをランダムに選んで、（C 一 1, … ,C_n)= (g一 Γ{Γ}， … ,g_nT{r})を計算し、 Commit= (C一 1, … ,C — n)、 State= rを出力する。
5. Hashは ChallengeSpace=(Z/qZ)に値を取るハッシュ関数である。
6. cを（Z/qZ)の元とし、 Challengesとする。 Yの元 y= ((g_l, … ,g_m) , (h_l, ··· ,h一 m) )、 Xの兀 x、し ommit= (し一 1, ··· ，し一 n)、し hallenge= cお び State= r力 21入力 れると、 FuncResponseは、 = cx+ r mod q 十算し、 Response= p ¾r 出力する。
7. y= ((g— 1, … ,g_m),(h_l, … ，h— m) )、 Commit= (C— 1, … ，C— n)ゝ Challenge= c、 Response= p力入力されると、 Verifyは、 (g一 { p}, … ,g一 π { p})と（h_r{c} C_l, … ,h_m c} C_m)を計算する。そして、（g_r{ p }, … ,g_m })= (h— Γ{ο} C— 1, … ,h_n c} C— n)が成立すれば「accept」 を出力し、そうでなければ「 」を出力する。
8. y=((g— l,"',g— m),(h— l,"',h— m))が入力されると、 Simulatorは、ランダムに c と /0を選び、（C 1, … ,C m)= (g_ Γ{ ρ } h Γ{- c}， … ,g m } h m ~{— c})とし、 Commit= (C― 1, … ,C― m)、 Challenge= c、 Response= pを出力す る。
[0018] [Rに関する 3-ムーブのパブリックコイン証明方式]
Rを Y X X上の関係式とする。 3-ムーブのパブリックコイン証明方式（Υ, X, FuncCom mit, Hash, FuncResponse, Verify,Simulator)が次の性質 1、 2を満たすとき、（Υ, X,
FuncCommit, Hash, FuncResponse, Verify,¾imulator)は Rに ¾|する《3—ム ~~ブの パブリックコイン証明方式であるという。
丄. R (y,x) 、 7こす任, iCの、 y,x)に对し、 (Commit, State) = FuncCommit (y,x)、 Cha ilenge= Hash、y,Commit)、 Response= FuncResponse、y, し ommit, challenge, Sta te)とすると、 Verify (y, Commit, Challenge, Response) = acceptとな 。
2. Yの任意の元 yに対し、（Commit,Challenge,Response) =Simulator (y)とすると、 Ver ily (y, Commit, Cnailenge, Responseノ = acceptとなる。
本発明は任意の 3-ムーブのパブリックコイン証明方式に対して用いることができる。し かし、実用的には何らかの関係式 Rに対する 3-ムーブのパブリックコイン証明方式で あることが望ましい。
[0019] [Rに関する 3-ムーブのパブリックコイン証明方式の例]
(Υ, X, Funcし ommit, Hash, FuncResponse, Challengebpace, Verily, simulator )を [3-ムーブのパブリックコイン証明方式の例]と同様に決める。 Xの元 Xと Yの元 y= ( (g_l, … ,g_m) , (h_l, … ，h_m) )に対し、 R (y, x)を関係式「(h_l, - " ,h 一 m) = (g一 1 tx} , · · · ,g一 m { })」とす0と、 (Y, X, FuncCommit, Hash, Func Response, ChallengeSpace, Verily, Simulator)は Rに関する 3-ムーブのパブリックコ イン証明方式である。
[0020] [アクセス構造]
Sを整数の有限集合とする。 Sの部分集合の族 Γが次の性質 1を満たすとき、 Γを S上 のアクセス構造であると 、う。
1. Sの任意の部分集合 A、 Bに対し Aが Γの元でかつ Aが Bの部分集合なら Bは Γの 元である。
[アクセス構造の例 1] nを自然数とする。 S={l,"-,n}とし、 r={S}の集合とする。このとき Γは S上のアクセス 構造である。
[アクセス構造の例 2]
nを自然数とし、 kを n以下の自然数とする。 S={l,"-,n}とし、 Γを Sの部分集合で k個 以上元を持つものの集合とする。このとき Γは S上のアクセス構造である。
[0021] [秘密分散方式]
Sを有限集合とし、 Γを S上のアクセス構造とし、 nを Sの元の数とする。組 (FuncShar, FuncReconstruct, SharSp, KeySp)が次の性質 1,···, 5を満たすとき、（FuncShar, Fu ncReconstruct, SharSp, KeySp)はアクセス構造 Γを持つ秘密分散方式であると!/、う
1. FuncSharと FuncReconstructは関数である。
2. SharSpと KeySpは集合である。
3. KeySpの元 cが入力されると、 FuncSharは、 SharSpの元 s—1, … ，s— nを出力す る。
4. 整数と SharSpの元との組（i— l,u— 1) ,···, (i_m,u_m)が入力されると、 FuncShar は KeySpの元を出力する力、または文字列「reject」を出力する。
5. cを KeySpの元とする。 FuncSharに cを入力したときの出力を s—1,… —とする。 A = {i_l, … ，i_m}を Γの元とする。このとき（i_l, s_{i_l}), … , (i_m, s一 {i—m})を FuncSharに入力すると、 FuncSharは cを出力する。
[0022] [秘密分散方式の例 1]
n、 S、 Γを [アクセス構造の例 1]で説明したように決める。さらに、 qを自然数とする。 (F uncShar, FuncReconstruct, SharSp, KeySp)を次の 1,···,4のように決めると、（Func Shar, FuncReconstruct , Sharbp, KeySp)は秘密分 ¾：方式である。
1. SharSpを巡回群（Z/qZ)とする。
2. KeySpを巡回群 (Z/qZ)とする。
3. KeySpの元 cが入力されると、 FuncSharは、 SharSpの元 s—1, '" —{n- 1}をランダ ムに選び、 s_n= c- s_l ',s_{n- 1} mod qを計算し、（s—1, … ，s_n)を出 力する。 4. ( (l,s—l) ,"-, (n,s— n) )が入力されると、 FuncReconstructは s—l+ … +s— nを 出力する。
[0023] [秘密分散方式の例 2]
n、 k、 S、 Γを [アクセス構造の例 2]で説明したように決める。さらに、 qを自然数とする。 (FuncShar, FuncReconstruct, SharSp, KeySp)を次の 1,· ··,4のように決めると、（Fu ncShar, FuncReconstruct , SharSp, KeySp)は秘密分散方式である。
1. SharSpを巡回群（Z/qZ)とする。
2. KeySpを巡回群 (Z/qZ)とする。
3. KeySpの元 cが入力されると、 FuncSharは、（Z/qZ)の元 a— l,"',a— {k- 1 }をランダ ムに選び、多項式 f(u)を f(u) = c+ a_lx+ &_2 2+ … +a_{k- l }x~{k- 1 } mod qと決め、 s一 1= f(l) mod q、 … 、s一 n= f(n) mod qとし、 (s一 1, … ,s一 n) を出力する。
4. ( (i_l, s_{i_l }) , … , (i_k, s—{k}) )が入力されると、 FuncReconstructは 多項式 f(u)で、 f(i— 1) = s— {i— 1 } mod q、 … 、f(i— {k}) = s_{i_k} mod q となるものを選び、 c= f(0) mod qとし、 cを出力する。
[0024] [特別な秘密分散方式]
Sを有限集合とし、 Γを S上のアクセス構造とし、 nを Sの元の数とする。組 (FuncShar, FuncReconstruct, FuncReShar, FuncVerShar, SharSp, KeySp)力次の'性質 1,· ··, 4 、/ 7こすとき、 (FuncShar, FuncReconstruct , FuncVerShar, SharSp, KeySp)はァ クセス構造 Γを持つ特別な秘密分散方式であると!/ヽぅ。
丄. (FuncShar, FuncReconstruct, SharSp, Key¾p)は秘密分散である。
2. A={i— 1,· ··,ί— m}を Γの元とする。 s— {i— 1 } , … ，s— {i— m}を SharSpの元とす る。そして l=n-mとする。 Sから Aを除いた集合を B= {j_l, … ，j_l}とする。さらに、 c を KeySpの元とする。このとき、 cと（i_l, s_{i_l }) , … , (i_m, s_{i_m})を Fu ncReSharに入力すると、 FuncReSharは、 Sの元と SharSpの元の組（j—1, s_{j_l }) ,
… ，(j_l, s_{j_l})を出力するか、または「1" 」を出力する。
3. SharSpの元 s— 1, … ，s—nと KeySpの元 cとが入力されると、 FuncVerSharは文字 列「accept」または文字列「reject」を出力する。 4. cを KeySpの元とする。 cを FuncSharに入力したときの出力を s— 1, … ，s— nとす る。このとき VerSharSp (,s _ 1 , · · · ,s _ n,c) =acceptが成立する。
[0025] [特別な秘密分散方式の例 1]
n、 S、 Γを [アクセス構造の例 1]で説明したように決める。さらに、 qを自然数とする。 (F uncShar, FuncReconstruct, SharSp, KeySp)を [秘密分散方式の例 1]で説明したよ うに決める。
1. A={i— 1,· ··,ί— m}を Γの元とする。 s— {i— 1 } , … ，s— {i— m}を SharSpの元とす る。そして l=n-mとする。 Sから Aを除いた集合を B= {j_l, … ，j_l}とする。さら〖こ、 c を KeySpの元とする。 cと（i—1, s_{i_l }) , … , (i_m, s— {i— m})が入力される と、 FuncReSharは、 s—{j—l }， … ，s— {j— - 1 } }をランダムに選び、 s— {j— 1}= c- (s_l+ · ··+ s_{j_{l-l } }+ s_{j_{j+l } }+ · ··+ s_n) mod qとし、（j— 1, s_ {j_l }) , … ，(j— 1, s— {j— 1})を出力する。
2. SharSpの元 s— 1, … ，s— nと KeySpの元 cとが入力されると、 FuncVerSharは、 s— 1+ · ··+ s一 n mod qを十算し、 c= s一 1+ · ··+ s一 n mod qなら「accept」 出力し 、そうでないなら「reject」を出力する。
[0026] [特別な秘密分散方式の例 2]
n、 k、 S、 Γを [アクセス構造の例 2]で説明したように決める。さらに、 qを自然数とする。 (FuncShar, FuncReconstruct, SharSp, KeySp)を [秘密分散方式の例 2]で説明した ように決める。（FuncReShar, FuncVerShar)を次の 1,2のように決めると、（FuncShar, FuncReconstruct , FuncReSnar, FuncVerShar, bharbp, KeySp) ίま/'クセス構造 Γ を持つ特別な秘密分散方式である。
1. A={i— 1,· ··,ί— m}を Γの元とする。 s— {i— 1 } , … ，s— {i— m}を SharSpの元とす る。そして l=n-mとする。 Sから Aを除いた集合を B= {j_l, … ，j_l}とする。さら〖こ、 c を KeySpの元とする。 cと（i—1, s_{i_l }) , … , (i_m, s— {i— m})が入力される と、 FuncReSharは、多項式 fCf(0) = c mod q, f(i_l) = s」i— 1 } mod q, · ··, f(i_m) = s_{i_m} mod qとなるものを探す。
2. もしそのような 1¾S存在しなければ、 FuncReSharは「reject」を出力する。そのような f が存在すれば、 FuncReSharは、 s {j 1 }= f(j 1) mod q, · ··, s {j 1}= f(j _1) mod qを (j_l, s_{j_l }) , … , (j_l, s— {j— 1})を出力する。
3. SharSpの元 s— 1, … ，s— nと KeySpの元 cとが入力されると、 FuncVerSharは、多 項式 fCf(0) = c mod q, f(l) = s— 1 mod q, · ··, f(n) = s_n mod qとなるもの を探す。そのような 1¾S存在すれば、 FuncVerSharは「accept」を出力し、そうでなけれ ば「reject」を出力する。
[0027] [コミットメント方式]
(C,FuncGen,FuncCom,FuncComVer)が次の 1,· ··,6を満たすとき、（C, FuncGen, F uncCom, FuncComVer)をコミットメント方式と 、つ。
1. Cを集合とする。
2. FuncGen、 FuncCom ^ Funcし omVerは関数である。
3. FuncGenは DomParを出力する。
4. DomParと Cの元 cとが入力されると、 FuncComは Comと ComStateを出力する。
5. DomPar, Cの元 c、データ Com'、およびデータ ComState'が入力されると、 FuncC omVerは文字列「accept」または文字列「reject」を出力する。
6. cを Cの元とし、 DomParを FuncGenの出力とする。 DomParと cが入力したときの Fun cComの出力を Comと ComStateとする。このとき DomPar、 c、 Com、 ComStateが入力さ れると、 FuncComVerは「accept」を出力する。
[0028] [コミットメント方式の例]
qを素数とし、 Gを位数 qの有限群とする。（C, FuncGen, FuncCom, FuncComVer) を次のように決めると、（C, FuncGen, FuncCom, FuncComVer)はコミットメント方式 になる。
1. C= (Z/qZ)とする。
2. FuncGenは、 Gの 2つの元 g, hを選び、 DomPar= (g, h)を出力する関数である。
3. DomPar= (g, h)と Cの元 cが入力されると、 FuncComは、（Z/qZ)の元 rをランダム に選び、 Com= g^c h と ComState= rを出力する。
4. DomPar= (g, h)と Cの元 cと Comと ComState=rが入力されると、 FuncComVerは、 g^c h を計算し、 Com= g^c h なら「accept」を出力し、そうでなければ「reject」を出 力する。 [0029] (実施形態 1)
[装置構成]
本実施形態の証明検証システムの構成を説明する。
図 1は本実施形態の証明検証システムの一構成例を示すブロック図である。
図 1に示すように、証明検証システムは、証明を行うための証明装置 100と、検証を行 うための検証装置 200とを有する。証明装置 100および検証装置 200は、通信ネットヮ ーク (不図示)を介して通信可能に接続される。
証明装置 100は、証明装置制御部 102、証明装置記憶部 101、および証明装置通信 部 (不図示)を有する。証明装置制御部 102は、コミット計算手段 111とレスポンス計算 手段 112とを有する。
検証装置 200は、検証装置制御部 202、検証装置記憶部 201、および検証装置通信 部（不図示）を有する。検証装置制御部 202は、チャレンジ計算手段 211と、レスポンス 計算手段 112とを有する。
[0030] [装置の実装]
各装置の制御部は、通信部の制御、記憶部の制御、およびデータの演算処理を行 う。制御部には、プログラムにしたがって所定の処理を実行する CPU (Central Proce ssing Unit)、およびプログラムを格納するためのメモリが設けられている。コミット計 算手段 111、レスポンス計算手段 112、チャレンジ計算手段 211および検証手段 212は 、 CPUがプログラムを実行することで、コンピュータ内に仮想的に構成される。
通信ネットワークとして、例えば、インターネットや LAN (Local Area Network)を用い ることができる。通信ネットワークは有線および無線のいずれでもよぐまた有線と無 線の組み合わせでもよい。図 1では、装置間における情報の流れをわかりやすくする ために、各装置の通信部を図に示すことを省略して 、る。
記憶部にはハードディスクや半導体メモリなどを用いることが可能である。
[0031] [記号]
Gを加法群とし、 Hashを Gに値を取るハッシュ関数とする。
i=l ,… ,ηに対し R_iを関係式とし、 y_iをデータとする。
l=l,· · ·,nίこ;<Tし(Y 1, X 1, Funcし ommit i, Hash i, FuncResponse ι, し halle ngeSpace— i, Verify— i, Simulator— i)を 3-ムーブのパブリックコイン証明方式とする
(FuncShar, FuncReconstruct , FuncReShar, FuncVerShar, SharSp, KeySp)を特 別な秘密分散方式とする。
さらに、 nを自然数とし、 S={ l,"-,n}とする。 Γを S上のアクセス構造とし、 A= {i_l, · ··, i_m}を Γの元とする。そして、 p= n-mとする。 Sから Aを除いた集合を B= {j_l, · ··, j— p}とする。
H— iを SharSpから ChallengeSpace— iへのハッシュ関数とする。 Simulator— 2をゼロ知 識証明シミュレータとする。ゼロ知識証明シミュレータは、従来技術と同様であるため 、ここでは詳細な説明を省略する。
[0032] [実施形態 1を使用する上での前提]
Xの元 X— {i— 1 } ,· · ·,χ— {i— m}と Yの元 y— 1, · · ',y— nが証明装置記憶部 101に保存さ れている。この X— {i— 1 } ,· ··,χ— {i— m}は、 n個の秘密データのうちの m個の秘密デ ータに相当する。
Yの元 y— 1 ,· ·· ,y— nが検証装置記憶部 201に保存されて 、る。
(Y― 1, X― 1, Funcし ommit― i, Hash― i, FuncResponse― i, ChallengeSpace― ι, Verify— i, Simulator— i)が関係式 R—iに関する 3ムーブのパブリックコイン証明方式 である場合は、 R(y_j, X _j)が満たされていることが望ましい。
[0033] [データ送受信]
証明装置 100と検証装置 200は、以下に説明する Protl-1, … ，Portl-10の順でデ ータ送受信を行う。図 2はデータ送受信の動作を示すフローチャートである。
Protl-1. 証明装置 100はコミット計算手段 111を行う（ステップ 1101)。
Protl-2. 証明装置 100は証明装置通信部を使ってコミット計算手段 111の出力を検 証装置 200に送信装置する (ステップ 1102)。
Protl-3. 検証装置 200は検証装置通信部を使ってコミット計算手段 111の出力を受 信し、受信したデータを検証装置記憶部 201に書き込む (ステップ 1103)。
Protl-4. 検証装置 200はチャレンジ計算手段 211を行う（ステップ 1104)。
Protl-5. 検証装置 200は検証装置通信部を使ってチャレンジ計算手段 211の出力 を証明装置 100に送信する (ステップ 1105)。
Protl-6. 証明装置 100は証明装置通信部を使ってチャレンジ計算手段 211の出力 を受信し、受信したデータを証明装置記憶部 101に書き込む (ステップ 1106)。
Protl-7. 証明装置 100はレスポンス計算手段 112を行う（ステップ 1107)。
Protl-8. 証明装置 100は証明装置通信部を使ってレスポンス計算手段 112の出力を 検証装置 200に送信する (ステップ 1108)。
Protl-9. 検証装置 200は検証装置通信部を使ってレスポンス計算手段 112の出力を 受信し、受信したデータを検証装置記憶部 201に書き込む (ステップ 1109)。
Protl-10. 検証装置 200は検証手段 212を行う（ステップ 1110)。
[0034] [コミット計算手段 111]
証明装置 100は、以下に説明する手段 Coml-1, … ，Coml-8を順に行う。図 3はコ ミット計算手段 111の動作手順を示すフローチャートである。
Coml-1. 秘密データ x_{i_l }， … ，x_{i_m}と集合 Yの元 y_l, … ，y_nを証 明装置記憶部 101から読み込む (ステップ 1201)。
Coml-2. v=l,〜,pに対して SharSpの元 s— {j_v}をランダムに選び Challenge_{j_ v}= H_i (s—{j_v})とする（ステップ 1202)。
Coml-3. v=l,〜,pに対して s— {j— v}を証明装置記憶部 101に書き込む (ステップ 12 03)。
し om丄— 4. ν=1,· ··,ρに对して (し ommit一 ij一 v}， Response一 ij一 v}) = simulator一 2
(y_{j_v} , Challenge— {j_v} )を計算する (ステップ 1204)。
し om丄— 5. ν=1,· ··,ρに对して (し ommit一 ij一 v}， Challenge一 {j一 v}， Response一 ij —v})を証明装置記憶部 101に書き込む (ステップ 1205)。
し om丄一り. u=l,"',m【こ对して (Commit一 {ι一 u; , State一 {ι一 u}) = Funcし ommit一 ti _u} (x_{i_u} , y_{i_u})を計算する（ステップ 1206)。
Coml-7. u=l,… に対して Commit— {i—u}， State— {i—u}を証明装置記憶部 101 に書き込む (ステップ 1207)。
Coml-8. (Commit_l,"',Commit_n)を出力する（ステップ 1208)。
[0035] [チャレンジ計算手段 211] 検証装置 200は、以下に説明する手段 Chal-l,〜,Chal-3を行う。図 4はチャレンジ 計算手段 211の動作手順を示すフローチャートである。
Chal-1. SharSpの元 cをランダムに選ぶ（ステップ 1301)。
Chal-2. cを検証装置記憶部に書き込む (ステップ 1302)。
Chal-3. cを出力する（ステップ 1303)。
[0036] [レスポンス計算手段 112]
証明装置 100は、以下に説明する手段 Resl-l," ',Resl-7を順に行う。図 5はレスポ ンス計算手段 112の動作手順を示すフローチャートである。
Resl-1. Commit— 1 ', Commit— nを証明装置記憶部 101から読み込む（ステップ 1 401)。
Resl-2. cを証明装置記憶部 101から読み込む (ステップ 1402)。
Resl-3. ν=1 ·,ρに対して State— {j— v}を証明装置記憶部 101から読み込む (ステ ップ 1403)。
Res 1-4. FuncReSharに cと（j一 l,s— {j_l }) , ' ", (j一 p,s— {j一 p})を入力して出力（i _1, s_{i_l }) , · · ·, (i_m, s— {i— m})を得る（ステップ 1404)。
Resl-5. ν=1 ·,ρに対して Challenge— {i_v}=H_i (s_v)とする（ステップ 1405)。 Resl- o. u=l, ' ",mに对して Response― ti― u}= FuncResponse― {i― u} (y _ {i― u } , Commit一 {i一 u}， Challenge一 {i一 u}， State一 {i一 u})とする（ステップ 1406)。 Resl- 7. s— l,' ",s— nと Response— 1 ", Response— nを出力する（ステップ 1407)。
[0037] [検証手段 212]
検証装置 200は、以下に説明する手段 Verl-l, ,Verl-4を行う。図 6は検証手段 21 2の動作手順を示すフローチャートである。
Verl-1. c,s_l , · · · ,s—nと Response— 1 , · · · , Response— nを検証装置記憶部 201から 読み込む (ステップ 1501)。
Verl-2. FuncVerShar (s― l, " ',s― n,c)を言十算し、 FuncVerShar (s― 1, · · ·, s― n, c ) = rejectなら rejectを出力して終了する（ステップ 1502)。
Verl-3. i=l,〜,nに対して Challenge_i=H_i (s_i)とする（ステップ 1503)。
Verl-4. 1=1, " ''nfこ对し、 Verify (y ι, し ommit i, Challenge ι, Response リ 言十算する。 i=l, · " ,ηに対し、 Verify (y _ i, Commit一 i, Challenge一 i, Response一 0= acceptなら acceptを出力して終了し、そうでなければ rejectを出力して終了する（ ステップ 1504)。
[0038] 本実施形態の証明検証システムでは、上述のようにして、証明装置 100が n個の秘 密データのうち m個を保持していることを検証装置 200に証明可能となる。そのため、 文献 1で開示された、 2つの条件を必要とする知識の証明方式について、条件 1を満 たせばよい。
[0039] (実施形態 2)
[装置構成]
本実施形態の証明検証システムの構成を説明する。なお、実施形態 1と同様な構 成についてはその詳細な説明を省略する。
図 7は本実施形態の証明検証システムの一構成例を示すブロック図である。
図 7に示すように、証明検証システムは、証明を行うための証明装置 100と、検証を行 うための検証装置 200とを有する。証明装置 100および検証装置 200は、通信ネットヮ ーク (不図示)を介して通信可能に接続される。
[0040] 証明装置 100は、証明装置制御部 102、証明装置記憶部 101、および証明装置通信 部 (不図示)を有する。証明装置制御部 102は、コミット計算手段 114と、レスポンス計 算手段 115とを有する。
検証装置 200は、検証装置制御部 202、検証装置記憶部 201、および検証装置通信 部 (不図示)を有する。検証装置制御部 202は、チャレンジコミット計算手段 210と、チ ャレンジ計算手段 213と、検証手段 214とを有する。
[0041] [装置の実装]
各装置の制御部には、プログラムにしたがって所定の処理を実行する CPUと、プロ グラムを格納するためのメモリとが設けられている。コミット計算手段 114、レスポンス計 算手段 115、チャレンジコミット計算手段 210、チャレンジ計算手段 213および検証手 段 214は、 CPUがプログラムを実行することで、コンピュータ内に仮想的に構成される 。その他の構成については、実施形態 1と同様であるため、詳細な説明を省略する。
[0042] [記号] 実施形態 1と同じ記号を使う。 C= ChallengeSpとし、 (C, FuncGen, FuncCom, Fun cComVer)をコミットメント方式とする。
[0043] [実施形態 2を使用する上での前提]
実施形態 1と同じ前提を課す。加えて次の前提 1,2を課す。
1. ChallengeSpは群である。
2. FuncGenの出力 DomParを証明装置 100と検証装置 200が事前に共有している。
[0044] [データ送受信]
証明装置 100と検証装置 200は、以下に説明する Prot2-l, ',Prot2-13順でデータ 送受信を行う。図 8および図 9は、データ送受信の動作手順を示すフローチャートで ある。
Prot2-l. 検証装置 200はチャレンジコミット計算手段 210を行う（ステップ 2101)。 Prot2-2.検証装置 200は検証装置通信部を使ってチャレンジコミット計算手段 210の 出力を証明装置 100に送信する (ステップ 2102)。
Prot2-3.証明装置 100は証明装置通信部を使ってチャレンジコミット計算手段 210の 出力を受信し、受信したデータを証明装置記憶部 101に書き込む (ステップ 2103)。 Prot2- 4.証明装置 100はコミット計算手段 114を行う（ステップ 2104)。
Prot2-5.証明装置 100は証明装置通信部を使ってコミット計算手段 114の出力を検証 装置 200に送信装置する (ステップ 2105)。
Prot2-6.検証装置 200は検証装置通信部を使ってコミット計算手段 114の出力を受信 し、受信したデータを検証装置記憶部 201に書き込む (ステップ 2106)。
Prot2-7.検証装置 200はチャレンジ計算手段 213を行う（ステップ 2107)。
Prot2-8.検証装置 200は検証装置通信部を使ってチャレンジ計算手段 213の出力を 証明装置 100に送信する (ステップ 2108)。
Prot2-9. 証明装置 100は証明装置通信部を使ってチャレンジ計算手段 213の出力 を受信し、受信したデータを証明装置記憶部 101に書き込む (ステップ 2109)。
Prot2-10.証明装置 100はレスポンス計算手段 115を行う（ステップ 2110)。
Prot2-ll.証明装置 100は証明装置通信部を使ってレスポンス計算手段 115の出力を 検証装置 200に送信する (ステップ 2111)。 Prot2-12.検証装置 200は検証装置通信部を使ってレスポンス計算手段 115の出力を 受信し、受信したデータを検証装置記憶部 201に書き込む (ステップ 2112)。
Prot2-13.検証装置 200は検証手段 214を行う（ステップ 2113)。
[0045] [チャレンジコミット計算手段 210]
検証装置 200は、以下に説明する手段 ChaCom2-l,' ",ChaCom2-5を行う。図 10は チャレンジコミット計算手段 210の動作手順を示すフローチャートである。
ChaCom2-l. DomParを検証装置記憶部 201から読み込む（ステップ 2201)。
ChaCom2-2. ChallengeSpの元 c— 1をランダムに選ぶ（ステップ 2202)。
ChaCom2-3. (Com.ComState) =FuncCom (DomPar,c_l)を計算する（ステップ 220
3)。
ChaCom2-4. c— 1、 Com, ComStateを検証装置記憶部 201に書き込む（ステップ 22
04)。
ChaCom2-5. Comを出力する（ステップ 2205)。
[0046] [コミット計算手段 114]
証明装置 100は、以下に説明する手段 Com2- l," ',Com2- 4を行う。図 11はコミット 計算手段 114の動作手順を示すフローチャートである。
Com2-l. 実施形態 1の Coml- l ',Coml- 7を行う（ステップ 2301)。
Com2-2. ChallengeSpの元 c— 2をランダムに選ぶ（ステップ 2302)。
Com2-3. c— 2を証明装置記憶部 101に書き込む（ステップ 2303)。
Com2-4. (c_2,Commit_l, ' ",Commit_n)を出力する（ステップ 2304)。
[0047] [チャレンジ計算手段 213]
検証装置 200は、以下に説明する手段 Cha2-l,Cha2-2を行う。図 12はチャレンジ計 算手段 213の動作手順を示すフローチャートである。
Cha2-1. 検証装置記憶部 201から c—l、 ComStateを読み込む（ステップ 2401)。 Cha2-2. c— 1、 ComStateを出力する（ステップ 2402)。
[0048] [レスポンス計算手段 115]
証明装置 100は、以下に説明する手段 Res2-l, ',Res2-7を順に行う。図 13はレス ポンス計算手段 115の動作手順を示すフローチャートである。 Res2— 1. Commit一 1,· · ·, Commit一 n, c一 l,c一 2,DomPar,Com,ComState 証明装 置記憶部 101から読み込む (ステップ 2501)。
Res2- 2. FuncComVer (DomPar.c― l,Com,ComState) 十算し、 FuncComVer (Do mPar, c_l, Com, ComState) = rejectなら rejectを出力して終了する（ステップ 25 02)。
Res2-3. c=c_lc_2を計算する（ステップ 2503)。
Res2-4. cを用いて実施形態 1の Resl- 3," ',Resl- 7を行う（ステップ 2504)。
[0049] [検証手段 214]
検証装置 200は、以下に説明する手段 Ver2-l, ,Ver2-5を行う。図 14は検証手段 214の動作手順を示すフローチャートである。
Ver2-1. c― 1 ,c― 2,s― 1 , · · · ,s― nと Response― 1 , · · ·, Response― nを検証装置記' fe咅 |5
201力ら読み込む（ステップ 2601)。
Ver2-2. c=c— lc— 2を計算する（ステップ 2602)。
Ver2- 3. FuncVerShar (s― 1 , · · · ,s― n,c)を十算し、 FuncVerShar、s― 1 , · · · ,s― n,c) =re jectなら rejectを出力して終了する（ステップ 2603)。
Ver2-4. i=l,〜,nに対して Challenge_i=H_i (s_i)とする（ステップ 2604)。
Ver2~5. ι=1,· · ·,ηίこ对し、 Verify (y― 1, し ommit― i, Challenge― i, Response―リ 十算する。 1=1, · · ·,!!に对し、 Verify (y一 ι, し ommit一 i, Challenge一 i, Response一リ = acceptなら acceptを出力して終了し、そうでなければ rejectを出力して終了する（ステ ップ 2605)。
[0050] 本実施形態では、実施形態 1の効果の他に、検証装置 200が証明装置 100から情 報を受信する前にチャレンジコミット計算手段 210を実行することで、データ選択の際 に証明装置 100からの情報による影響が抑制され、証明装置 100に格納された秘密 情報の秘匿性が向上する。
[0051] (実施形態 3)
[装置構成]
本実施形態の証明検証システムの構成を説明する。なお、実施形態 1と同様な構 成についてはその詳細な説明を省略する。 図 15は本実施形態の証明検証システムの一構成例を示すブロック図である。
図 15に示すように、証明検証システムは、証明を行うための証明装置 100と、検証を 行うための検証装置 200とを有する。証明装置 100および検証装置 200は、通信ネット ワーク (不図示)を介して通信可能に接続される。
[0052] 証明装置 100は、証明装置制御部 102、証明装置記憶部 101、および証明装置通信 部 (不図示)を有する。証明装置制御部 102には証明文作成手段 110が設けられてい る。証明文作成手段 110は、コミット計算手段 116と、チャレンジ計算手段 113と、レス ポンス計算手段 117とを有する。
検証装置 200は、検証装置制御部 202、検証装置記憶部 201、および検証装置通信 部（不図示）を有する。検証装置制御部 202は、検証手段 215を有する構成である。
[0053] [装置の実装]
各装置の制御部には、プログラムにしたがって所定の処理を実行する CPUと、プロ グラムを格納するためのメモリとが設けられている。コミット計算手段 116、レスポンス計 算手段 117、チャレンジ計算手段 113および検証手段 215は、 CPUがプログラムを実行 することで、コンピュータ内に仮想的に構成される。その他の構成については、実施 形態 1と同様であるため、詳細な説明を省略する。
[0054] [記号]
実施形態 1と同じ記号を使う。 HashChaを SharSpに値を取るハッシュ関数とする。さら に、 Mをビット列とする。証明装置 100と検証装置 200は事前に Mを共有しているとする 。どのような方法で Mを共有したのかは問わない。 Mは予備の入力で、目的に応じて Mを様々なものにセットする。 Mとして空列を選んでもよい。 Mにセットするものとして、 例えば、次の 1 ',6があり得る。
1. (y_l,-,y_n)
2. 証明者の ID
3. 検証者の ID
4. 時刻
5. 何らかのメッセージ
6. 1,· ··, 5の全てまたは一部を連結したもの [実施形態 3を使用する上での前提]
Xの元 X— {i— 1 } ,· ··,χ— {i— m}、 Yの元 y— 1,· ··,γ— n、および Mが証明装置記憶部 10 1に保存されている。 Yの元 y— 1, · ··, y—n、および Mが検証装置記憶部 201に保存 されている。
[0055] [データ送受信]
証明装置 100と検証装置 200は、以下に説明する Prot3-l,' Prot3-4の順でデータ 送受信を行う。図 16はデータ送受信の動作手順を示すフローチャートである。
Prot3-l. 証明装置 100は証明文作成手段 110を行う（ステップ 3101)。
Prot3-2. 証明装置 100は証明装置通信部を使って証明文作成手段 110の出力を検 証装置 200に送信装置する (ステップ 3102)。
Prot3-3. 検証装置 200は検証装置通信部を使って証明文作成手段 110の出力を受 信し、受信したデータを検証装置記憶部 201に書き込む (ステップ 3103)。
Prot3-4. 検証装置 200は検証手段 215を行う（ステップ 3104)。
[0056] [証明文作成手段 110]
証明装置 100は、以下に説明する手段 GenPfi-l,GenPf3-2を順に行う。図 17は証 明文作成手段 110の動作手順を示すフローチャートである。
GenP13-l. [コミット計算手段 116]、 [チャレンジ計算手段 113]、 [レスポンス計算手段 1 17]を順に行う（ステップ 3201)。
enPw-2. し ommit一 1,· ··, Commit一 n、 s一 l,- --,s一 n、 Response一 1,· ··, Response一 nを出力する（ステップ 3202)。
[コミット計算手段 116]
証明装置 100は、実施形態 1のコミット計算手段 111の Coml- l,"',Coml- 7を行う。
[チャレンジ計算手段 113]
証明装置 100は以下の手段 Cha3-1、 Cha3-2を行う（図 18)。
Cha3-1. Commit— 1 ', Commit— η,Μを証明装置記憶部 101から読み込む。 （ステツ プ 3301)
Cha3-2. c=HashCha (Commit— 1 ', Commit— η,Μ)を計算し、 cを証明装置記憶部 101に書き込む。（ステップ 3302) [レスポンス計算手段 117]
証明装置 100は、実施形態 1のレスポンス計算手段 112の Resl-l, " ',Resl-6を行う。
[0057] [検証手段 215]
検証装置 200は、以下に説明する手段 Ver3-l, ,Ver3-5を行う。図 19は検証手段 215の動作手順を示すフローチャートである。
Ver3— 1. s一 l,- - -,s一 n, Commit一 1, · · ·, Commit一 n, M, Response一丄, · · ·, Response —nを検証装置記憶部 201から読み込む (ステップ 3401)。
Ver3-2. c=HashCha (Commit— 1 ", Commit— η,Μ)を計算する（ステップ 3402)。 Ver3- 3. FuncVerShar (s― l, " ',s― n,c)を十算し、 FuncVerShar (s― 1, · · ·, s― n, c) = rejectなら rejectを出力して終了する（ステップ 3403)。
Ver3-4. i=l,〜,nに対して Challenge_i=H_i (s_i)とする（ステップ 3404)。
Ver3— 5. ι=1,· · ·,ηίこ对し、 Verify (y― 1, し ommit― i, Challenge― i, Response―リ 十算する。 1=1, ···,!!に对し、 Verify (y一 ι, し ommit一 i, Challenge一 i, Response一リ = acceptなら acceptを出力して終了し、そうでなければ rejectを出力して終了する（ステ ップ 3405)。
[0058] 本実施形態では、証明装置 100におけるチャレンジ計算手段 113の動作がコミット計 算手段 116の影響を受けないように改善したので、実施形態 1の効果の他に、証明装 置 100の秘密情報の秘匿性が向上するとともに、証明装置 100と検証装置 200との通 信回数を低減できる。
[0059] なお、実施形態 1から 3で説明した証明検証方法を、コンピュータに実行させるため のプログラムに適用してもよい。
[0060] また、本発明の証明検証システム、証明装置および検証装置と、証明検証方法と、 その方法をコンピュータに実行させるためのプログラムについて、知識の証明方式を 様々な暗号プロトコルを作る際の部品として用いることができ、認証方式や署名方式 に応用できる。
[0061] なお、本発明は上記実施形態に限定されることなぐ発明の範囲内で種々の変形 が可能であり、それらも本発明の範囲内に含まれることはいうまでもない。

Claims

請求の範囲
n個の秘密データのうち m個（m<n)の秘密データ x— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータが格納された証明装 置記憶部、ならびに、前記 n個の秘密データに対する識別子 i—1, ···, i— mのいず れとも異なる識別子を j—1, ···, j_p(p= n-m)とし、前記証明装置記憶部から前記 巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに選び、 v=l, ···, pに対して各 s —{j—v}のハッシュ関数による値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, p に対して前記 y—{j—v}と前記 Challenge— {j—v}を入力とするゼロ知識証明のシミュ レーシヨンを行うことで、コミット値とレスポンス値の組（Commit— {j—l}， Response— {j― 1}) , ···, (Commit― {j― p}， Response― {j― p}) 生成し、 u=l, ···, mに対し て x_{i_u}と y_{i_u}を用いてコミット値 Commit_{i_u}を生成し、前記 Commit_ {j一 1}, ···, Commit一 {j一 p}および ij tiし ommit一 ti一 1}, ···, Commit一 {ι一 m} 力 なるコミット値 Commit— 1, ···, Commit— nを外部に送信し、外部からチャレンジ 値 cを受信すると、該チャレンジ値 cおよび前記 s— {j— 1}, ···, s— {j— p}から残りの 元 s_{i_l}， ···, s_{i_m}を生成し、 ί=1,···,ηに対して各 s_iにそのハッシュ値を テャレンジ値 Challenge― iとし、目 ij gciy― i、目 ij gcCommit― iおよび目 ij gdChallenge― i 使ってレスポンス値 Response— iを算出し、元 s—1, ···, s— nとレスポンス値 Respons e_l, ···, Response— nを外部に送信する証明装置制御部を含む証明装置と、 前記証明装置と通信可能に接続され、複数の乱数および前記集合の元 y—1, ···, y—nが格納された検証装置記憶部、ならびに、前記証明装置力もコミット値 Commit — 1 , · · ·, Commit— nを受信すると、前記複数の乱数力 選択した cをチャレンジ値とし て該証明装置に送信し、前記巡回群の元 s—1, ···, s— nおよびレスポンス値 Respo nse― 1, ···, Response― nを flj己証明装置力ら受信すると、該 s― 1, ···, s― n力 ij 記チャレンジ値 cから正当な方法で生成された秘密分散である力否かを検証し、正当 であれば、 i=l, ···, nに対して前記 s—iのハッシュ値をチャレンジ値 Challenge— し 、糸且 (Commit一 i, Challenge一 i, Response一 i)による gil5文か目 ij dy一 iの正当な g正 明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正 当でない場合、該証明装置による証明を受理しない検証装置制御部を含む検証装 置と、
を有する証明検証システム。
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y— n、 n個の元を含む巡回群のデータおよび複数の元を含む群 のデータが格納された証明装置記憶部、ならびに、前記 n個の秘密データに対する 識別子 i— 1, ···, i— mのいずれとも異なる識別子を j— 1, ···, j_p(p= n- m)とし、 外部からコミット値 Comを受信すると、該コミット値 Comを前記証明装置記憶部に格納 し、該証明装置記憶部力 前記巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに 選び、 v=l, ···, pに対して各 s— {j— v}のハッシュ関数による値をチャレンジ値 Chall enge_{j_v}とし、 v=l, ···, pに対して刖記元 y_{j_v}と ij記 Challenge_U_v}を 入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組 (Commit― {j― l}, Response― {j―丄 ), ···, (Commit― {j― p}， Response― ij― p})を生成し、 u=l, ···, mに対して X— {i— u}と y— {i— u}を用いてコミット値 Commit 一 11一 u}を生成し、目 ij 己 Commit一 {j一丄 , ···, し ommit一 ij一 p}および目 ij 己 Commit 一 {i一 1}, ···, Commit一 {i一 m};g iDなるコ ット値 Commit一 1, ···, Commit一 nを 求め、前記複数の元を含む群力 ランダムに元 c— 2を選び、該元 c— 2および該 Com mit— 1, ···, Commit— nを外部に送信し、前記コミット値 Comを算出するための、前 記複数の元を含む群の元 c—1を外部力 受信すると、該コミット値 Comが該元 c—1の 正当なコミットメントである力否かを検証し、正当でない場合、証明の続行を拒否し、 正当である場合、前記 c— 1と前記 c— 2を乗算した値 cを求め、前記 s— {j— 1}, ···, s — {j— p}と該値 cから残りの元 s— {i— 1}, ···, s— {i— m}を生成し、 i=l,〜,nに対して 各 s—iにそのハッシュ値をチャレンジ値 Challenge— iとし、前記 y— i、前記 Commit— i 、および前記 Challenge— iを使ってレスポンス値 Response— iを算出し、元 s— 1, ···, s _ nとレスポンス値 Response _ 1, ···, Response _ nを ij記検証装置に送信する証 明装置制御部を含む証明装置と、
前記証明装置と通信可能に接続され、複数の元を含む群のデータが格納された検 証装置記憶部、ならびに、前記複数の元を含む群からランダムに元 c—1を選び、該 元 c—1のコミット値 Comを算出して前記証明装置に送信し、前記複数の元を含む群 の元 c— 2、およびコミット値 Commit— 1, ···, Commit— nを前記証明装置から受信 すると、前記元 c—1を該証明装置に送信し、巡回群の元 s—1, ···, s— n、およびレ スポンス値 Response— 1, ···, Response— nを前記証明装置から受信すると、該 c—1 と該 c— 2を乗算した値 cを求め、該 s—1, ···, s—nが該値 cから正当な方法で生成さ れた秘密分散である力否かを検証し、正当であれば、 i=l, ···, nに対して前記元 s— iのハッシュ値をチャレンジ値 Challenge— iとし、糸且（Commit— i, Challenge— i, Respo nse_i)による証明文が前記 y—iの正当な証明文である力否かを検証し、正当である 場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明 を受理しな!ヽ検証装置制御部を含む検証装置と、
を有する証明検証システム。
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータが格納された証明装 置記憶部、ならびに、前記 n個の秘密データに対する識別子 i—1, ···, i— mのいず れとも異なる識別子を j—1, ···, j_p(p= n-m)とし、前記証明装置記憶部から前記 巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに選び、 v=l, ···, pに対して各 s —{j—v}のハッシュ関数による値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, p に対して前記元 y—{j—v}と前記 Challenge— {j—v}を入力とするゼロ知識証明のシミ ユレーシヨンを行うことで、コミット値とレスポンス値の組（Commit— {j—l}， Response ― {j― 1}) , ···, (Commit― {j― p}， Response― {j― p}) 生成し、 u=l, ···, mに 対して x_{i_u}と y_{i_u}を用いてコミット値 Commit— {i_u}を生成し、前記 Com mit一 {j一 1}, ···, Commit一 {j一 p}および目 ij己 Commit一 {ι一 1|, ···, Commit一 {i —m}力らなるコミット値 Commit— 1, ···, Commit— nを求め、該 Commit— 1, ···, C ommit― nを含むデータのノヽッシュ値を cとし、該ノヽッシュ値 cと肯 ij記 s― {j― 1}, ···, s — {j— p}と力 残りの元 s— {i— 1}, ···, s— {i— m}を生成し、 i=l, ···, nに対して各 s—iにそのハッシュ値をチャレンジ値 Challenge— iとし、前記 y— i、前記 Commit— iお よび前記 Challenge— iを使ってレスポンス値 Response— iを算出し、元 s—1, ···, s一 nとレスポンス値 Response— 1, ···, Response— nを外部に送信する証明装置制御部 を含む証明装置と、 前記証明装置と通信可能に接続され、前記集合の元 y—1, ···, y— nが格納され た検証装置記憶部、ならびに、前記巡回群の元 s—1, ···, s—n、コミット値 Commit 一 1, ···, し ommit一 n、およびレス 3ヽンス値 Response一丄, ···, Response一 nを目 ij，己 証明装置から受信すると、該 Commit— 1, ···, Commit— nを含むデータのハッシュ 値を cとし、該 s— 1, ···, s—nが該ハッシュ値 cから正当な方法で生成された秘密分 散であるか否かを検証し、正当であれば、 i=l, ···, nに対して前記元 s—iのハッシュ 値をチャレンジ値 Challenge _ iとし、糸且 (Commit _ i, Challenge _ i, Response _ i)に よる証明文が前記 y—iの正当な証明文である力否かを検証し、正当である場合、前 記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理し な ヽ検証装置制御部を含む検証装置と、
を有する証明検証システム。
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明す る証明装置であって、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y—1, ···, y—n、および n個の元を含む巡回群のデータが格納された記憶部 と、
前記 n個の秘密データに対する識別子 i—1, ···, i—mのいずれとも異なる識別子 を j— 1, ···, j_p(p= n-m)とし、前記記憶部から前記巡回群の元 s— {j— 1}, ···, s — {j— p}をランダムに選び、 v=l, ···, pに対して各 s— {j— Wのハッシュ関数による 値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して前記 y— {j— v}と前記 Challenge— {j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、コミット 値とレスポンス値の組（Commit一 {j一 1}, Response一 {j一 1}) , ···, (Commit一 {j一 p}, Response _ {j一 p})を生成し、 u=l, ···, mに对して x一 {i _ u}と y一 {i _ u}を用 いてコミット値 Commit一 {i一 u}を生成し、前記 Commit一 {j一 1}, ···, Commit一 {j一 p}および前記 Commit— {i_l}， ···， Commit— {i_m}からなるコミット値 Commit_l,
···, Commit— nを前記検証装置に送信し、前記検証装置カゝらチャレンジ値 cを受信 すると、該チャレンジ値 cおよび前記 s— {j— 1}, ···, s— {j— p}から残りの元 s— {i— 1}, ···, s {i m}を生成し、 ί=1 ·,ηに対して各 s iにそのハッシュ値をチャレンジ 値 Challenge _ iとし、目 ij己 y _ i、前記 Commit _ iおよび前記 Challenge _ iを使ってレス ポンス値 Response― iを算出し、元 s― 1, ···, s― nとレスポンス値 Response― 1, ···,
Response— nを前記検証装置に送信する制御部と、
を有する証明装置。
[5] 証明装置と通信可能に接続され、該証明装置が発行する証明文を検証する検証 装置であって、
複数の乱数および集合の元 y—1, ···, y—nが格納された記憶部と、
前記証明装置力もコミット値 Commit_l,"',Commit_nを受信すると、前記複数の 乱数力 選択した cをチャレンジ値として該証明装置に送信し、巡回群の元 s— 1, … , s—nおよびレスポンス値 Response— 1, ···, Response— nを前記証明装置から受 信すると、該 s— 1, ···, s—nが前記チャレンジ値 cから正当な方法で生成された秘密 分散であるか否かを検証し、正当であれば、 i=l, ···, nに対して前記 s— iのハッシュ 値をチャレンジ値 Challenge _ iとし、糸且 (Commit _ i, Challenge _ i, Response _ i)に よる証明文が前記 y—iの正当な証明文である力否かを検証し、正当である場合、前 記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理し ない制御部と、
を有する検証装置。
[6] 検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明す る証明装置であって、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y—1, ···, y— n、 n個の元を含む巡回群のデータおよび複数の元を含む群 のデータが格納された記憶部と、
前記 n個の秘密データに対する識別子 i—1, ···, i—mのいずれとも異なる識別子 を j— 1, ···, j_p(p= n-m)とし、前記検証装置力もコミット値 Comを受信すると、該 C omを前記記憶部に格納し、該記憶部から前記巡回群の元 s— {j— 1}, ···, s_{j_p }をランダムに選び、 v=l, ···, pに対して各 s— {j— v}のハッシュ関数による値をチヤ レンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して前記元 y— {j— v}と前記 Challe nge—{j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレ スポンス値の糸且（Commit— {j— 1}, Response— {j—1}) , ···, (Commit— {j—p}, R esponse一 {j一 p})を生成し、 u=l, ···, mに対して x一 {i一 u}と y一 {i一 u}を用いてコミ ット値 Commit一 {i一 u}を生成し、 j己 Commit一 {j一 1}, ···, Commit一 {j一 p}およ び前記 Commit— {i— 1}, ···, Commit— {i—m}力らなるコミット値 Commit— 1, ···, Commit— nを求め、前記複数の元を含む群からランダムに元 c— 2を選び、該 c— 2お よび該 Commit_l, ···, Commit_nを前記検証装置に送信し、前記 Comを算出する ための、前記複数の元を含む群の元 c—1を該検証装置力 受信すると、該コミット値 Comが該 c—1の正当なコミットメントであるか否かを検証し、正当でない場合、証明の 続行を拒否し、正当である場合、前記 c— 1と前記 c— 2を乗算した cを求め、前記 s— {j _1}, ···, s— {j— p}と該 cから残りの元 s— {i— 1}, ···, s— {i— m}を生成し、 ί=1,··· ,ηに対して各 s—iにそのハッシュ値をチャレンジ値 Challenge— iとし、前記 y— i、前記 Commit— i、および前記 Challenge— iを使ってレスポンス値 Response— iを算出し、元 s ― 1, ···, s― nとレスポンス値 Response― 1, ···, Response― nを肯 ij記検証装置に送 信する制御部と、
を有する証明装置。
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証する検証 装置であって、
複数の元を含む群のデータおよび集合の元 y—1, ···, y—nが格納された記憶部 と、
前記複数の元を含む群からランダムに元 c—1を選び、該元 c—1のコミット値 Comを 算出して前記証明装置に送信し、前記複数の元を含む群の元 c— 2、およびコミット値 Commit— 1, ···, Commit— nを前記証明装置力も受信すると、前記 c—1を該証明装 置に送信し、巡回群の元 s—1, ···, s—n、およびレスポンス値 Response— 1, ···, R esponse— nを前記証明装置力 受信すると、該 c—1と該 c— 2を乗算した cを求め、該 s— 1, ···, s—nが該 cから正当な方法で生成された秘密分散であるか否かを検証し 、正当であれば、 i=l, ···, nに対して前記元 s— iのハッシュ値をチャレンジ値 Challen ge一 iとし、糸且 (Commit一 i, Challenge一 i, Response一 i)による証明乂;^目 ij dy _ iの 正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を 受理し、正当でない場合、該証明装置による証明を受理しない制御部と、 を有する検証装置。
[8] 検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明す る証明装置であって、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータが格納された記憶部 と、
前記 n個の秘密データに対する識別子 i—1, ···, i—mのいずれとも異なる識別子 を j— 1, ···, j_p(p= n-m)とし、前記記憶部から前記巡回群の元 s— {j— 1}, ···, s — {j— p}をランダムに選び、 v=l, ···, pに対して各 s— {j— Wのハッシュ関数による 値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して前記元 y— {j— v}と前 記 Challenge— {j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、コミ ット値とレスポンス値の糸且（Commit一 {j一 1}, Response一 {j一 1}) , ···, (Commit_{ j一 p}， Response一 {j一 p}) 生成し、 u=l, ···, mに对して x一 {i一 u}と y一 {i一 u}を 用いてコミット値 Commit_{i_u}を生成し、前記 Commit_{j_l}， ···， Commit_{j _p}および前記 Commit— {i_l}， ···， Commit_{i_m}力らなるコミット値 Commit ― 1, ···, Commit― nを求め、該 Commit― 1, ···, Commit― nを含むテータのノヽッ シュ値を cとし、該 cと前記 s— {j— 1}, ···, s— {j— p}と力 残りの元 s— {i— 1}, ···, s— {i— m}を生成し、 i=l, ···, nに対して各 s— iにそのハッシュ値をチャレンジ値 Chal lenge _ iとし、目 ij Cy _ i、目 ij dCommit _ iおよび目 ij dChallenge _ i 使ってレスポンス 値 Response― i 算出し、元 s― 1, ···, s― nとレスポンス値 Response― 1, ···, Respo nse—nを前記検証装置に送信する制御部と、
を有する証明装置。
[9] 証明装置と通信可能に接続され、該証明装置が発行する証明文を検証する検証 装置であって、
集合の元 y— 1, ···, y—nが格納された記憶部と、
巡回群の元 s— 1, ···, s—n、コミット値 Commit— 1, ···, Commit— n、およびレス ポンス値 Response 1, ···, Response nを前記証明装置から受信すると、該 Commi t_l, ···, Commit— nを含むデータのハッシュ値を cとし、該 s—1, ···, s— nが該 c 力 正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、 i=l, ···, nに対して前記元 s—iのハッシュ値をチャレンジ値 Challenge— iとし、組（Commit _i, Challenge— i, Response— i)による証明文が前記 y—iの正当な証明文であるか 否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場 合、該証明装置による証明を受理しない制御部と、
を有する検証装置。
証明文を発行する証明装置と、該証明装置に通信可能に接続され、該証明文を検 証する検証装置とによる証明検証方法であって、
前記証明装置が、 n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ,x— {i— m}、集合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータを 格納し、
前記検証装置が、複数の乱数および前記集合の元 y—1, ···, y— nを格納し、 前記証明装置が、前記 n個の秘密データに対する識別子 i—1, ···, i— mのいずれ とも異なる識別子を j—1, ···, j_p(p= n- m)とし、前記巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに選び、 v=l, ···, pに対して各 s— {j— v}のハッシュ関数によ る値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して前記 y— {j— v}と前 記 Challenge— {j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、コミ ット値とレスポンス値の糸且（Commit一 {j一 1}, Response一 {j一 1}) , ···, (Commit_{ j _ p}， Response _ {j一 p})を生成し、 u=l, ···, mに対して x _ {i _ u}と y一 {i _ u}を 用いてコミット値 Commit_{i_u}を生成し、前記 Commit_{j_l}， ···， Commit_{j _p}および前記 Commit— {i_l}， ···， Commit_{i_m}力らなるコミット値 Commit _1, ···, Commit_nを前記検証装置に送信し、
前記検証装置力 前記証明装置カゝらコミット値 Commit_l,"-,Commit_nを受信す ると、前記複数の乱数力 選択した cをチャレンジ値として該証明装置に送信し、 前記証明装置が、前記検証装置から前記チャレンジ値 cを受信すると、該チヤレン ジ値 cおよび前記 s— {j— 1}, ···, s— {j— p}から残りの元 s— {i— 1}, ···, s_{i_m }を生成し、 ί=1 ·,ηに対して各 s iにそのハッシュ値をチャレンジ値 Challenge iとし 、前記 y _ i、目 ij記 Commit一 iおよび目 ij ciChallenge一 iを使ってレスポンス値 Response ― iを算出し、 s― 1, ···, s― nと Response― 1, ···, Response― n 目 1』 検止装置に 送信し、
前記検証装置が、前記元 s—1, ···, s—nおよびレスポンス値 Response— 1, ···, Response— nを前記証明装置力 受信すると、該 s—1, ···, s—nが前記チャレンジ 値 cから正当な方法で生成された秘密分散である力否かを検証し、正当であれば、 i= 1, ···, nに対して前記 s—iのハッシュ値をチャレンジ値 Challenge— iとし、組（Commit _i, Challenge— i, Response— i)による証明文が前記 y—iの正当な証明文であるか 否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場 合、該証明装置による証明を受理しない、証明検証方法。
証明文を発行する証明装置と、該証明装置に通信可能に接続され、該証明文を検 証する検証装置とによる証明検証方法であって、
前記証明装置が、 n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, …
,x— {i— m}、集合の元 y— 1, ···, y— n、 n個の元を含む巡回群のデータおよび複 数の元を含む群のデータを格納し、
前記検証装置が、前記複数の元を含む群のデータを格納し、
前記検証装置が、前記複数の元を含む群からランダムに元 c—1を選び、該元 c— 1 のコミット値 Comを算出して前記証明装置に送信し、
前記証明装置が、前記 n個の秘密データに対する識別子 i—1, ···, i— mのいずれ とも異なる識別子を j_l, ···, j_p(p= n-m)とし、前記検証装置カゝら前記コミット値 Comを受信すると、該 Comを格納し、前記巡回群の元 s_{j_l}， ···， s— {j_p}をラ ンダムに選び、 v=l, ···, pに対して各 s—{j—v}のハッシュ関数による値をチヤレン ジ値 Challenge_{j一 v}とし、 v=l, ···, pに対して前記元 y一 {j一 v}と前記 Challenge —{j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポ ンス値の糸且（Commit— {j— 1}, Response— {j—1}) , ···, (Commit— {j—p}, Resp onse一 {j一 p})を生成し、 u=l, ···, mに対して x一 {i一 u}と y一 {i一 u}を用いてコミット 値 Commit一 {i一 u}を生成し、 J cCommit一 {j一 1}, ···, Commit一 {j一 p}および刖 己 Commit {i 1|, ···, Commit {i m}» ioな コミット値し ommit 1, ···, し om mit— nを求め、前記複数の元を含む群からランダムに元 c— 2を選び、該 c— 2および 該 Commit _ 1, ···, Commit _ nを刖記検証装置に送信し、
前記検証装置は、前記元 c— 2および前記コミット値 Commit— 1, ···, Commit— nを 前記証明装置から受信すると、前記 c—1を該証明装置に送信し、
前記証明装置が、前記元 c—1を前記検証装置から受信すると、前記コミット値 Com が該 c—1の正当なコミットメントであるか否かを検証し、正当でない場合、証明の続行 を拒否し、正当である場合、前記 c— 1と前記 c— 2を乗算した cを求め、前記 s— {j— 1} , ···, s— {j_p}と該 cから残りの元 s— {i_l}， ···, s— {i— m}を生成し、 ί=1 ·,ηに 対して各 s—iにそのハッシュ値をチャレンジ値 Challenge— iとし、前記 y— i、前記 Com mit— i、および前記 Challenge— iを使ってレスポンス値 Response— iを算出し、元 s— 1,
···, s― nとレスポンス値 Response― 1, ···, Response― nを flj '己検証装置に送信し 前記検証装置が、前記元 s—1, ···, s—n、および前記レスポンス値 Response— 1, ···, Response— nを前記証明装置力 受信すると、該 c—1と該 c— 2を乗算した cを 求め、該 s— 1, ···, s—nが該 cから正当な方法で生成された秘密分散である力否か を検証し、正当であれば、 i=l, ···, nに対して前記元 s—iのハッシュ値をチャレンジ 値 Challenge― iとし、糸且 (Commit― i, Challenge― i, Response― ιリによる証明文か目 ij 記 y—iの正当な証明文である力否かを検証し、正当である場合、前記証明装置によ る証明を受理し、正当でない場合、該証明装置による証明を受理しない、証明検証 方法。
証明文を発行する証明装置と、該証明装置に通信可能に接続され、該証明文を検 証する検証装置とによる証明検証方法であって、
前記証明装置が、 n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ,x— {i— m}、集合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータを 格納し、
前記検証装置が、前記集合の元 y—1, ···, y— nを格納し、
前記証明装置が、前記 n個の秘密データに対する識別子 i—1, ···, i— mのいずれ とも異なる識別子を j—1, ···, j_p(p= n- m)とし、前記巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに選び、 v=l, ···, pに対して各 s— {j— v}のハッシュ関数によ る値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して前記元 y— {j— v}と 前記 Challenge— {j—v}を入力とするゼロ知識証明のシミュレーションを行うことで、コ ミット値とレスポンス値の組（Commit— {j—l}， Response— {j—1}) , ···, (Commit 一 {j一 p}， Response一 {j一 p})を生成し、 u=l, ···, mに;^して x一 {i一 u}と y一 {i一 u }を用いてコミット値 Commit_{i_u}を生成し、前記 Commit_{j_l}， ···， Commit 一 {j一 p}および前記 Commit一 {i一 1}, ···, Commit一 {i一 m}からなるコミット値 Com mit― 1, ···, Commit― nを求め、該 Commit― 1, ···, Commit― nを含むテータのノヽ ッシュ値を cとし、該 cと前記 s— {j— 1}, ···, s— {j— p}と力も残りの元 s— {i— 1}, ···, s— {i— m}を生成し、 i=l, ···, nに対して各 s—iにそのハッシュ値をチャレンジ値 Ch allenge― iとし、目 ij gciy _ i、目 ij gcCommit― iおよび目 ij Challenge― i 使ってレスポン ス値 Response— iを算出し、元 s—1, ···, s—nとレスポンス値 Response— 1, ···, Res ponse— nを肯 ij 己検証装置に送信し、
刖記恢証装置は、刖記元 s― 1, ···, s― n、刖記コミット値 Commit― 1, ···, Commi t—n、および前記レスポンス値 Response— 1, ···, Response— nを前記証明装置から 受信すると、該 Commit— 1, ···, Commit— nを含むデータのハッシュ値を cとし、該 s — 1, ···, s—nが該 cから正当な方法で生成された秘密分散である力否かを検証し、 正当であれば、 i=l, ···, nに対して前記元 s— iのハッシュ値をチャレンジ値 Challeng e一 iとし、糸且 (Commit一 i, Challenge一 i, Response一 i)による giti^文が目 ij dy一 iの正 当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受 理し、正当でない場合、該証明装置による証明を受理しない、証明検証方法。
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明す るコンピュータに実行させるためのプログラムであって、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y—n、および n個の元を含む巡回群のデータを格納し、
前記 n個の秘密データに対する識別子 i—1, ···, i—mのいずれとも異なる識別子 を ···, j_p(p= n- m)とし、前記巡回群の元 s— {j_l}， ···， s— {j_p}をラン ダムに選び、 v=l, ···, pに対して各 s—{ j—v}のハッシュ関数による値をチャレンジ 値 Challenge一 { j一 v}とし、
v=l, ···, pに対して前記 y— {j— v}と前記 Challenge— {j— v}を入力とするゼロ知識 証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit— {j—l}， Response― {j― 1}) , ···, (し ommit― ij― p}， Response― ij― p})を生成し、 u=l, ···, mに対して x_{i_u}と y_{i_u}を用いてコミット値 Commit_{i_u}を生 成し、目 ij tiし ommit一 {j一 1}, ···, Commit一 {j一 p}および ij tiし ommit一 ti一 1}, ···
, Commit— {i—m}力らなるコミット値 Commit— 1, ···, Commit— nを前記検証装置 に送信し、
前記検証装置力 チャレンジ値 cを受信すると、該チャレンジ値 cおよび前記 s—{j _1}, ···, s— {j_p}から残りの元 s— {i_l}， ···, s— {i_m}を生成し、
i=l , · · · ,ηに対して各 s— iにそのハッシュ値をチャレンジ値 Challenge— iとし、
—刖記 y _ i、目 ij記 Commit _ iおよび目 ij ciChallenge _ iを使ってレスポンス値 Response ― iを算出し、元 s― 1, ···, s― nとレスポンス値 Response― 1, ···, Response― nを前 記検証装置に送信する処理を前記コンピュータに実行させるためのプログラム。
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証するコンビ ユータに実行させるためのプログラムであって、
複数の乱数および集合の元 y—1, ···, y— nを格納し、
前記証明装置力もコミット値 Commit_l,"',Commit_nを受信すると、前記複数の 乱数力 選択した cをチャレンジ値として該証明装置に送信し、
巡回群の元 s— 1, ···, s—nおよびレスポンス値 Response— 1, ···, Response— nを 前記証明装置から受信すると、該 s—1, ···, s—nが前記チャレンジ値 cから正当な 方法で生成された秘密分散であるカゝ否かを検証し、
前記 s— 1, ···, s—nが前記チャレンジ値 cから正当な方法で生成された秘密分散 であれば、 i=l, ···, nに対して前記 s—iのハッシュ値をチャレンジ値 Challenge— し 、糸且 (Commit一 i, Challenge一 i, Response一 i)による gil5文か目 ij dy一 iの正当な g正 明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正 当でない場合、該証明装置による証明を受理しない処理を前記コンピュータに実行 させるためのプログラム。 検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明す るコンピュータに実行させるためのプログラムであって、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1}, … ，x— {i— m}、集 合の元 y— 1, ···, y— n、 n個の元を含む巡回群のデータおよび複数の元を含む群 のデータを格納し、
前記 n個の秘密データに対する識別子 i—1, ···, i—mのいずれとも異なる識別子 を j— 1, ···, j_p(p= n-m)とし、前記検証装置力もコミット値 Comを受信すると、該 C omを格納し、
前記巡回群の元 s— {j— 1}, ···, s— {j— p}をランダムに選び、 v=l, ···, pに対し て各 s—{j—v}のハッシュ関数による値をチャレンジ値 Challenge— {j—v}とし、 v=l, ···, pに対して前記元 y— {j—v}と前記 Challenge— {j—v}を入力とするゼロ知 識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit— {j—1 }, Response― ij― 1}) , ···, (Commit― {j― p}， Response― {j― p})を生成し、 u=l, ···, mに対して x_{i_u}と y_{i_u}を用いてコミット値 Commit_{i_u}を生 成し、 f!ij tiし ommit一 {j一 1}, ···, Commit一 {j一 p}および ij tiし ommit一 {i一 1}, ··· , Commit— {i—m}力らなるコミット値 Commit— 1, ···, Commit— nを求め、前記複 数の元を含む群からランダムに元 c— 2を選び、該 c— 2および該 Commit— 1, ···, Co mmit— nを 〗記検証装置に送 1§し、
前記 Comを算出するための、前記複数の元を含む群の元 c—1を前記検証装置か ら受信すると、該コミット値 Comが該 c—1の正当なコミットメントである力否かを検証し 前記コミット値 Comが前記 c—1の正当なコミットメントでな 、場合、証明の続行を拒 否し、正当なコミットメントである場合、前記 c— 1と前記 c— 2を乗算した cを求め、前記 s_{j_l}, ···, s— {j— p}と該 cから残りの元 s— {i— 1}, ···, s— {i—m}を生成し、 i =1,···,ηに対して各 s— iにそのハッシュ値をチャレンジ値 Challenge— iとし、前記 y— i、 前記 Commit— i、および前記 Challenge— iを使ってレスポンス値 Response— iを算出し 、元 s _ 1, ···, s _ nとレス ンス値 Response _ 1, ···, Response _ nを目 ij' ci検証装置 に送信する処理を前記コンピュータに実行させるためのプログラム。 [16] 証明装置と通信可能に接続され、該証明装置が発行する証明文を検証するコンビ ユータに実行させるためのプログラムであって、
複数の元を含む群のデータおよび集合の元 y—1, · ··, y— nを格納し、 前記複数の元を含む群からランダムに元 c—1を選び、該元 c—1のコミット値 Comを 算出して前記証明装置に送信し、
前記複数の元を含む群の元 c— 2、およびコミット値 Commit— 1, · ··, Commit— nを 前記証明装置から受信すると、前記 c—1を該証明装置に送信し、
巡回群の元 s— 1, · ··, s—n、およびレスポンス値 Response— 1, · ··, Response— n を前記証明装置から受信すると、該 c— 1と該 c— 2を乗算した cを求め、該 s— 1, · ··, s—nが該 cから正当な方法で生成された秘密分散である力否かを検証し、
前記 s— 1, · ··, s—nが前記 cから正当な方法で生成された秘密分散であれば、 i=l , · ··, nに対して前記元 s—iのハッシュ値をチャレンジ値 Challenge— iとし、組（Comm it_i, Challenge— i, Response— i)による証明文が前記 y—iの正当な証明文である か否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない 場合、該証明装置による証明を受理しない処理を前記コンピュータに実行させるため のプログラム。
[17] 検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明す るコンピュータに実行させるためのプログラムであって、
n個の秘密データのうち m個（m<n)の秘密データ X— {i— 1 } , … ，x— {i— m}、集 合の元 y— 1, · ··, y—n、および n個の元を含む巡回群のデータを格納し、
前記 n個の秘密データに対する識別子 i—1, · ··, i—mのいずれとも異なる識別子 を ···, j_p (p= n- m)とし、前記巡回群の元 s— {j_l }， · ··， s— {j_p}をラン ダムに選び、 v=l, · ··, pに対して各 s—{j—v}のハッシュ関数による値をチャレンジ 値 Challenge一 { j一 v}とし、
v=l, · ··, pに対して前記元 y— {j— v}と前記 Challenge— {j— v}を入力とするゼロ知 識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit— {j—1 } , Response― {j― 1 }) , · · · , (し ommit― ij― p}， Response― ij― p})を生成し、 u=l, · ··, mに対して x {i u}と y_ii u}を用いてコミット値 Commit {i u}を生 成し、 Bij tiし ommit一 {j一 1}, ···, Commit一 {j一 p}および Bij tiし ommit一 {i一 1}, ··· , Commit一 {i一 m}力らなるコミット値 Commit一 1, ···, Commit一 nを求め、該 Commi t_l, ···, Commit— nを含むデータのハッシュ値を cとし、前記 cと前記 s— {j— 1}, ···, s— {j_p}とから残りの元 s— {i_l}， ···, s— {i_m}を生成し、 i=l, ···, nに対 して各 s—iにそのハッシュ値をチャレンジ値 Challenge— iとし、前記 y— i、前記 Commit —iおよび前記 Challenge— iを使ってレスポンス値 Response— iを算出し、元 s— 1, ···, s—nとレスポンス値 Response— 1, ···, Response— nを前記検証装置に送信する処 理を前記コンピュータに実行させるためのプログラム。
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証するコンビ ユータに実行させるためのプログラムであって、
集合の元 y— 1, ···, y— nを格納し、
巡回群の元 s— 1, ···, s—n、コミット値 Commit— 1, ···, Commit— n、およびレス ポンス値 Response— 1, ···, Response— nを前記証明装置から受信すると、該 Commi t_l, ···, Commit— nを含むデータのハッシュ値を cとし、該 s—1, ···, s—nが該 c から正当な方法で生成された秘密分散であるか否かを検証し、
前記 s— 1, ···, s—nが前記 cから正当な方法で生成された秘密分散であれば、 i=l , ···, nに対して前記元 s—iのハッシュ値をチャレンジ値 Challenge— iとし、組（Comm it_i, Challenge— i, Response— i)による証明文が前記 y—iの正当な証明文である か否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない 場合、該証明装置による証明を受理しない処理を前記コンピュータに実行させるため のプログラム。
PCT/JP2007/051959 2006-02-09 2007-02-06 証明検証システム、証明装置、検証装置、証明検証方法、およびプログラム Ceased WO2007091531A2 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US12/278,874 US20100169643A1 (en) 2006-02-09 2007-02-06 Proof verification system, proving device, verifying device, proof verification method, and program
EP07708077A EP1986105A4 (en) 2006-02-09 2007-02-06 VERIFICATION SYSTEM, VERIFICATION DEVICE, VERIFICATION DEVICE, VERIFICATION METHOD, AND PROGRAM
JP2007557834A JP4775597B2 (ja) 2006-02-09 2007-02-06 証明検証システム、証明装置、検証装置、証明検証方法、およびプログラム

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2006032650 2006-02-09
JP2006-032650 2006-02-09

Publications (2)

Publication Number Publication Date
WO2007091531A1 WO2007091531A1 (ja) 2007-08-16
WO2007091531A2 true WO2007091531A2 (ja) 2007-08-16

Family

ID=38345553

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2007/051959 Ceased WO2007091531A2 (ja) 2006-02-09 2007-02-06 証明検証システム、証明装置、検証装置、証明検証方法、およびプログラム

Country Status (4)

Country Link
US (1) US20100169643A1 (ja)
EP (1) EP1986105A4 (ja)
JP (1) JP4775597B2 (ja)
WO (1) WO2007091531A2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2014087738A1 (ja) * 2012-12-05 2014-06-12 ソニー株式会社 情報処理装置、検証処理装置、情報処理方法、検証処理方法、およびプログラム

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2714780B1 (fr) * 1993-12-30 1996-01-26 Stern Jacques Procédé d'authentification d'au moins un dispositif d'identification par un dispositif de vérification.
US6076163A (en) * 1997-10-20 2000-06-13 Rsa Security Inc. Secure user identification based on constrained polynomials

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
DOUGLAS R. STINSON: "Cryptography: Theory and Practice", KYORITSU SHUPPAN CO., LTD., pages: 355 - 356
ISAMU TERANISHI; JUN FURUKAWA; KAZUE SAKO: "ASiACRYPT 2004", 2004, SPRINGER-VERLAG, article "k-Times Anonymous Authentication (Extended Abstract", pages: 308 - 322
R. CRAMER; I. DAMGAARD; B. SCHOENMAKERS: "CRYPTO '94", 1994, SPRINGER-VERLAG, article "Proofs of partial knowledge and simplified design of witness hiding protocols", pages: 174 - 187
TERANISHI ISAMU: "A Signature Method Having Reduced Computations and Tight Safety in a Discrete Logarithm Problem", PROCEEDINGS OF THE 2005 SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY, vol. 3E3-4, January 2005 (2005-01-01)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2014087738A1 (ja) * 2012-12-05 2014-06-12 ソニー株式会社 情報処理装置、検証処理装置、情報処理方法、検証処理方法、およびプログラム
US9516007B2 (en) 2012-12-05 2016-12-06 Sony Corporation Verifier and prover have an authentication protocol with challenge-response with the challenge from prover having identification of the verifier
JPWO2014087738A1 (ja) * 2012-12-05 2017-01-05 ソニー株式会社 情報処理装置、検証処理装置、情報処理方法、検証処理方法、およびプログラム

Also Published As

Publication number Publication date
US20100169643A1 (en) 2010-07-01
EP1986105A4 (en) 2009-05-20
JPWO2007091531A1 (ja) 2009-07-02
JP4775597B2 (ja) 2011-09-21
EP1986105A2 (en) 2008-10-29

Similar Documents

Publication Publication Date Title
US10129029B2 (en) Proofs of plaintext knowledge and group signatures incorporating same
US9973342B2 (en) Authentication via group signatures
JP4477616B2 (ja) 署名システム及び署名方法
CN119783138B (zh) 区块链驱动的分布式隐私数据存储与访问控制方法及系统
JP5099003B2 (ja) グループ署名システムおよび情報処理方法
EP3161996B1 (en) System and device binding metadata with hardware intrinsic properties
CN111835526B (zh) 一种生成匿名凭证的方法及系统
US11856095B2 (en) Apparatus and methods for validating user data by using cryptography
US11831778B2 (en) zkMFA: zero-knowledge based multi-factor authentication system
Byun A generic multifactor authenticated key exchange with physical unclonable function
US9292671B1 (en) Multi-server authentication using personalized proactivization
Dong et al. Cryptographic protocol
Mir et al. Decentralized, Privacy‐Preserving, Single Sign‐On
US20100251351A1 (en) information and communication system, an organization apparatus and a user apparatus
CN119720142A (zh) 一种区块链跨链访问方法、可读存储介质及设备
US9230075B1 (en) Multi-server authentication using proactivization journaling
WO2007091531A2 (ja) 証明検証システム、証明装置、検証装置、証明検証方法、およびプログラム
JPWO2007010903A1 (ja) 鍵発行方法、グループ署名システム
El Kassem Lattice-based direct anonymous attestation.
Amar et al. Comment on``SRAM-PUF Based Entities Authentication Scheme for Resource-constrained IoT Devices''
Wang et al. A quantum concurrent signature scheme based on the quantum finite automata signature scheme
Hahn et al. Enhanced authentication for outsourced educational contents through provable block possession
Chakraborty Advanced Techniques in Symmetric Key Cryptanalysis
Lesaignoux et al. On the Implementation of a Lattice-Based DAA for Vanet System
Wang et al. Constructing an authentication token to access external services in service aggregation

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application
DPE1 Request for preliminary examination filed after expiration of 19th month from priority date (pct application filed from 20040101)
ENP Entry into the national phase

Ref document number: 2007557834

Country of ref document: JP

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 2007708077

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 12278874

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

DPE1 Request for preliminary examination filed after expiration of 19th month from priority date (pct application filed from 20040101)