Proof verification system, proving device, verifying device, proof verification method, and program

A proof verification system comprising:

• a proving device that includes:
• a proving device memory unit that stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, data of a cyclic group containing n elements, and data of a group that contains a plurality of elements;
• and a proving device control unit for:
• taking identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), upon receiving Commit value Com from the outside, storing the Commit value Com in said proving device memory unit, randomly choosing elements s_{j—1}, . . . , s_{j_p} of said cyclic group from said proving device memory unit, taking values realized by a hash function of each of s_{j_v} for v=1, . . . , p as Challenge value Challenge_{j_v}, and carrying out a simulation of a zero-knowledge proof that takes as input said elements y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j 1 }, Response_{j—1}), . . . , (Commit_{j_p}, Response_{j_p}), using x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, finding Commit values Commit—1, . . . , Commit_n that are composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit_{i_m}, randomly choosing element c—2 from said group that contains a plurality of elements, transmitting to the outside the element c—2 and Commit—1, . . . , Commit_n, upon receiving from the outside element c—1 of said group that contains a plurality of elements for calculating said Commit value Com, verifying whether the Commit value Com is a proper commitment of the element c—1 or not, denying continuation of the proof if not proper, but if proper, finding value c obtained by multiplying said c—1 and said c—2, generating the remaining elements s_{i—1}, . . . , s_{i_m} from said s_{j—1}, . . . , s_{j_p} and the value c, taking the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, using said y_i, said Commit_i, and said Challenge_i to calculate Response value Response_i, and transmitting to said verifying device elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n;
• and
• a verifying device that is communicably connected to said proving device and that includes:
• a verifying device memory unit that stores data of a group that contains a plurality of elements;
• and a verifying device control unit for:
• randomly choosing element c—1 from said group that contains a plurality of elements, calculating Commit value Com of the element c—1 to transmit to said proving device, upon receiving element c—2 of said group that contains a plurality of elements and Commit values Commit—1, . . . , Commit_n from said proving device, transmitting said element c—1 to said proving device, upon receiving elements s—1, . . . , s_n of the cyclic group and Response values Response—1, . . . , Response_n from said proving device, finding a value c obtained by multiplying said c—1 and said c—2, verifying whether s—1, . . . , s_n is secret sharing that has been generated from said value c by a proper method or not, if proper, taking hash values of said element s_i for i=1, . . . , n as Challenge value Challenge_i, verifying whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, and accepting the proof realized by said proving device if proper and not accepting the proof realized by said proving device if not proper.

A proof verification system comprising:

• a proving device that includes:
• a proving device memory unit that stores in (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, and data of a cyclic group containing n elements;
• and a proving device control unit for:
• taking identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), randomly choosing elements s_{j—1}, . . . , s_{j_p} of said cyclic group from said proving device memory unit, taking values realized by a hash function of each of s_{j_v} for v=1, . . . , p as a Challenge value Challenge_{j_v}, carrying out a simulation of a zero-knowledge proof that takes as input said elements y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response {j—1}), . . . , (Commit_{j_p}, Response_{j_p}), using x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_(i_u), finding Commit values Commit—1, . . . , Commit_n that are composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit_{i_m}, taking a hash value of data that contain Commit—1, . . . , Commit_n as c, generating the remaining elements s_{i—1}, . . . , s_{i_m} from the hash value c and said s_(j—1), . . . , s_{j_p}, taking the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, using said y_i, said Commit_i, and said Challenge_i to calculate a Response value Response_i, and transmitting to the outside elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n;
• and
• a verifying device that is communicably connected to said proving device and that includes:
• a verifying device memory unit that stores elements y—1, . . . , y_n of said set;
• and a verifying device control unit for:
• upon receiving elements s—1, . . . , s_n of said cyclic group, Commit values Commit—1, . . . , Commit_n, and Response values Response—1, . . . , Response_n from said proving device, taking hash values of data that include Commit—1, . . . , Commit_n as value c, verifying whether said s—1, . . . , s_n is secret sharing generated by a proper method from the hash value c or not, taking the hash value of said element s_i for i=1, . . . , n as a Challenge value Challenge_i if proper, verifying whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, and accepting the proof of realized by said proving device if proper and not accepting the proof realized by said proving device if not proper.

A proving device that is communicably connected to a verifying device for proving to said verifying device that said proving device holds secret data, said proving device comprising:

• a memory unit that stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, and data of a cyclic group containing n elements;
• and
• a control unit for taking identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), randomly choosing elements s_{j−1}, . . . , s_{j_p} of said cyclic group from said memory unit, taking values realized by a hash function of each of s_{j_v} for v=1, . . . , p as Challenge value Challenge_{j_v}, and carrying out a simulation of a zero-knowledge proof that takes as input said y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response_{j—1}), . . . , (Commit_{j_p}, Response_{j_p}), using x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, transmitting to said verifying device Commit values Commit—1, . . . , Commit_n composed of said Commit_{j—1}, . . . , Commit—{j_p} and said Commit_{i—1}, . . . , Commit_{i_m}, upon receiving Challenge value c from said verifying device, generating the remaining elements s_{i—1}, . . . , s_{i_m} from the Challenge value c and said s_{j—1}, . . . , s_{j_p}, taking the hash values at each s_i for i=1, . . . , n as the Challenge value Challenge_i, using said y_i, said Commit_i, and said Challenge_i to calculate Response value Response_i, and transmitting to said verifying device elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n.

A verifying device that is communicably connected to a proving device for verifying a proof statement issued by the proving device, said verifying device comprising:

• a memory unit that stores a plurality of random numbers and elements y—1, . . . , y_n of a set;
• and
• a control unit for:
• upon receiving Commit values Commit—1, . . . , Commit _n from said proving device, transmitting c that is chosen from said plurality of random numbers as a Challenge value to said proving device, upon receiving elements s—1, . . . , s_n of a cyclic group and Response values Response—1, . . . , Response_n from said proving device, verifying whether s—1, . . . , s_n is secret sharing that has been generated from said Challenge value c by a proper method or not, if proper, taking hash values of said s_i for i=1, . . . , n as Challenge value Challenge_i, verifying whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, and accepting the proof realized by said proving device if proper and not accepting the proof realized by said proving device if not proper.

A proving device that is communicably connected to a verifying device for proving to the verifying device that said proving device holds secret data, said proving device comprising:

• a memory unit that stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, data of a cyclic group containing n elements, and data of a group that contains a plurality of elements;
• and
• a control unit for:
• taking identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), upon receiving Commit value Com from said verifying device, storing Com in said memory unit, randomly choosing elements s_{j—1}, . . . , s_{j_p} of said cyclic group from said memory unit, taking values realized by a hash function of each of s_{j_v} for v=1, . . . , p as Challenge value Challenge_{j_v}, and carrying out a simulation of a zero-knowledge proof that takes as input said elements y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response_{j—1}), . . . , (Commit_{j_p}, Response_{j_p}), using x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, finding Commit values Commit—1, . . . , Commit_n that are composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit—{i_m}, randomly choosing element c—2 from said group that contains a plurality of elements, transmitting to said verifying device the c—2 and Commit—1, . . . , Commit_n, upon receiving from said verifying device element of said group that contains a plurality of elements for calculating said Com, verifying whether the Commit value Com is a proper commitment of said c—1 or not, denying continuation of the proof if not proper, but if proper, finding value c obtained by multiplying said c—1 and said c—2, generating the remaining elements s_{i—1}, . . . , s_{_m} from said s_{j—1}, . . . , s_{j_p} and said c, taking the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, using said y_i, said Commit_i, and said Challenge_i to calculate Response value Response_i, and transmitting to said verifying device elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n.

A verifying device that is communicably connected to a proving device for verifying a proof statement issued by said proving device, said verifying device comprising:

• a memory unit that stores data of a group that contains a plurality of elements and elements y—1, . . . , y_n of a set;
• and
• a control unit for:
• randomly choosing element c—1 from said group that contains a plurality of elements, calculating Commit value Com of the element c—1 to transmit to said proving device, upon receiving element c—2 of said group that contains a plurality of elements and Commit values Commit—1, . . . , Commit_n from said proving device, transmitting said c—1 to said proving device, upon receiving elements s—1, . . . , s_n of a cyclic group and Response values Response—1, . . . , Response_n from said proving device, finding a value c obtained by multiplying said c—1 and said c—2, verifying whether s—1, . . . , s_n is secret sharing that has been generated from said c by a proper method or not, if proper, taking hash values of said element s_i for i=1, . . . , n as Challenge value Challenge_i, verifying whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, and accepting the proof realized by said proving device if proper and not accepting the proof realized by said proving device if not proper.

A proving device that is communicably connected to a verifying device for proving to said verifying device that said proving device holds secret data, said proving device comprising:

• a memory unit that stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, and data of a cyclic group containing n elements;
• and
• a control unit for:
• taking identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), randomly choosing elements s_{j—1}, . . . , s—{j_p} of said cyclic group from said memory unit, taking values realized by a hash function of each of s_{j_v} for v=1, . . . , p as a Challenge value Challenge_{j_v}, and carrying out a simulation of a zero-knowledge proof that takes as input said elements y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response—{j—1}), . . . , (Commit_{j_p}, Response_{j_p}), using x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, finding Commit values Commit—1, . . . , Commit_n that are composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit_{i_m}, taking a hash value of data that contain said Commit—1, . . . , Commit_n as c, generating the remaining elements s_{i—1}, . . . , s_{i_m} from said c and said s_{j—1}, . . . , s_{j_p}, taking the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, using said y_i, said Commit_i, and said Challenge_i to calculate a Response value Response_i, and transmitting to said verifying device elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n.

A verifying device that is communicably connected to a proving device for verifying a proof statement issued by said proving device, said verifying device comprising:

• a memory unit that stores elements y—1, . . . , y_n of a set;
• and
• a control unit for:
• upon receiving elements s—1, . . . , s_n of a cyclic group, Commit values Commit—1, . . . , Commit_n, and Response values Response—1, . . . , Response_n from said proving device, taking hash values of data that include Commit—1, . . . , Commit_n as c, verifying whether said s—1, . . . , s_n is secret sharing generated by a proper method from said c or not, if proper, taking the hash value of said element s_i for i=1, . . . , n as a Challenge value Challenge_i, verifying whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, and accepting the proof realized by said proving device if proper and not accepting the proof realized by said proving device if not proper.

A proof verification method, being implemented by a proving device that issues a proof statement, and a verifying device that is communicably connected to said proving device for verifying said proof statement;

• wherein:
• said proving device stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, and data of a cyclic group containing n elements;
• said verifying device stores a plurality of random numbers and elements y—1, . . . , y_n of said set;
• said proving device takes identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), randomly chooses elements s13 {j—1}, . . . , s—{j_p} of said cyclic group, takes values realized by a hash function of each of s_{j_v} for v=1, . . . , p as Challenge value Challenge_{j_v}, and carries out a simulation of a zero-knowledge proof that takes as input said y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response_{j—1}), . . . , (Commit_{j_p}, Response_{j_p}), uses x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, and transmits to said verifying device Commit values Commit—1, . . . , Commit_n composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit_{i_m};
• said verifying device, upon receiving Commit values Commit—1, . . . , Commit_n from said proving device, transmits c that is chosen from said plurality of random numbers as a Challenge value to said proving device;
• said proving device, upon receiving said Challenge value c from said verifying device, generates the remaining elements s_{i—1}, . . . , s_{i_m} from the Challenge value c and said s—{j—1}, . . . , s_{j_p}, takes the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, uses said y_i, said Commit_i, and said Challenge_i to calculate Response value Response_i, and transmits to said verifying device elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n;
• and
• said verifying device, upon receiving said elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n from said proving device, verifies whether s—1, . . . , s_n is secret sharing that has been generated from said Challenge value c by a proper method or not, and if proper, takes a hash value of said s_i for i=1, . . . , n as a Challenge value Challenge_i, verifies whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, and accepts the proof realized by said proving device if proper and does not accept the proof realized by said proving device if not proper.

A proof verification method, being implemented by a proving device that issues a proof statement, and a verifying device that is communicably connected to said proving device for verifying said proof statement;

• wherein:
• said proving device stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, data of a cyclic group containing n elements, and data of a group that contains a plurality of elements;
• said verifying device stores data of said group that contains a plurality of elements;
• said verifying device randomly chooses element c—1 from said group that contains a plurality of elements, and calculates Commit value Com of the element c—1 to transmit to said proving device;
• said proving device takes identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), upon receiving said Commit value Com from said verifying device, stores said Com, randomly chooses elements s_{j—1}, . . . , s_{j_p} of said cyclic group, takes values realized by a hash function of each of s_{j_v} for v=1, . . . , p as Challenge value Challenge_{j_v}, carries out a simulation of a zero-knowledge proof that takes as input said elements y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response_{j—1}), . . . , (Commit_{j_p}, Response_{h_p}), uses x_{i_u} and y{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, finds Commit values Commit—1, . . . , Commit_n that are composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit_{i_m}, randomly chooses element c—2 from said group that contains a plurality of elements, and transmits to said verifying device said c—2 and said Commit—1, . . . , Commit_n;
• said verifying device, upon receiving said element c—2 and said Commit values Commit—1, . . . , Commit_n from said proving device, transmits said c—1 to said proving device,
• said proving device, upon receiving from said verifying device said element c—1, verifies whether said Commit value Com is a proper commitment of said c—1 or not, denies continuation of the proof if not proper, but if proper, finds c obtained by multiplying said c—1 and said c—2, generates the remaining elements s_{i—1}, . . . , s_{i_m} from said s_{j—1}, . . . , s_{j_p} and said c, takes the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, uses said y_i, said Commit_i, and said Challenge_i to calculate a Response value Response_i, and transmits to said verifying device elements s—1, . . . , and s_n and Response values Response—1, . . . , Response_n;
• and
• said verifying device, upon receiving said elements s—1, . . . , s_n and said Response values Response—1, . . . , Response_n from said proving device, finds a value c obtained by multiplying said c—1 and said c—2, verifies whether said s—1, . . . , s13 n is secret sharing that has been generated from said c by a proper method, if proper, takes hash values of said element s_i for i=1, . . . , n as a Challenge value Challenge_i, verifies whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement or not, accepts the proof realized by said proving device if proper and does not accept the proof realized by said proving device if not proper.

A proof verification method, being implemented by a proving device that issues a proof statement, and a verifying device that is communicably connected to said proving device for verifying said proof statement;

• wherein:
• said proving device stores m (m<n) items of secret data x_{i—1}, . . . , x_{i_m} of n items of secret data, elements y—1, . . . , y_n of a set, and data of a cyclic group containing n elements;
• said verifying device stores elements y—1, . . . , y_n of said set;
• said proving device takes identifiers that differ from any of identifiers i—1, . . . , i_m for said n items of secret data as j—1, . . . , j_p (where p=n−m), randomly chooses elements s_{j—1}, . . . , s_{j_p} of said cyclic group, takes values realized by a hash function of each of s_{j_v} for v=1, . . . , p as a Challenge value Challenge_{j_v}, carries out a simulation of a zero-knowledge proof that takes as input said elements y_{j_v} and said Challenge_{j_v} for v=1, . . . , p to generate sets of Commit values and Response values (Commit_{j—1}, Response_{j—1}), . . . , (Commit_{j_p}, Response_{j_p})), uses x_{i_u} and y_{i_u} for u=1, . . . , m to generate Commit value Commit_{i_u}, finds Commit values Commit—1, . . . , Commit_n that are composed of said Commit_{j—1}, . . . , Commit_{j_p} and said Commit_{i—1}, . . . , Commit{i_m}, takes a hash value of data that contain said Commit—1, . . . , Commit_n as c, generates the remaining elements s_{i—1}, . . . , s_{i_m} from said c and said s_{j—1}, . . . . , s_{j_p}, takes the hash value at each s_i for i=1, . . . , n as a Challenge value Challenge_i, uses said y_i, said Commit_i, and said Challenge_i to calculate a Response value Response_i, and transmits to said verifying device elements s—1, . . . , s_n and Response values Response—1, . . . , Response_n;
• and
• said verifying device, upon receiving said elements s—1, . . . , s_n, said Commit values Commit—1, . . . , Commit_n, and said Response values Response—1, . . . , Response_n from said proving device, takes Hash values of data that include said Commit—1, . . . , Commit_n as c, verifies whether said s—1, . . . , s_n is secret sharing generated by a proper method from said c or not, if proper, takes the hash value of said element s_i for i=1, . . . , n as a Challenge value Challenge_i, verifies whether the proof statement resulting from the set (Commit_i, Challenge_i, Response_i) is a proper proof statement of said y_i or not, accepts the proof realized by said proving device if proper and does not accept the proof realized by said proving device if not proper.