Integrated shuffle validity proving device, proof integrating device, integrated shuffle validity verifying device, and mix net system

A proof integrating device having a central processing unit for executing processing using a program stored within a memory of the central processing unit, upon receipt of a mix net input cryptogram, for supplying a mix net output cryptogram which is a result of shuffling said mix net input cryptogram, and for supplying a same conversion knowledge proof commitment and a permutation proof commitment for proving a validity of a shuffle by harmonizing with a plurality of integrated shuffle validity proving devices provided in correspondence with an order number κ which is an integer indicating an order, and subsequently upon receipt of a challenge value for authentication, for operating as a single shuffle validity proving device for supplying a response corresponding to said challenge value, said proof integrating device comprising:

• communicating means with each of said plurality of integrated shuffle validity proving devices which are assigned the order number from 1 to a maximum number which is equal to the number of said plurality of integrated shuffle validity proving devices;
• and
• a permutation proof commitment integrating device, upon receipt of a permutation proof commitment including permutation proof texts with the order number from 1 to κ from said integrated shuffle validity proving devices, for transmitting said permutation proof commitment as a permutation storage commitment to an integrated shuffle validity proving device having the order number of κ+1 for requesting a permutation proof text,
• wherein one or a plurality of said permutation proof commitment integrating are provided, said proof integrating device receives a public key for mixing, a public key for commitment, a pseudo-public key, a common reference base, and said mix net input cryptogram comprised of a plurality of cryptograms encrypted by said public key for mixing, said proof integrating device comprises:
• communicating means with an integrated shuffle validity verifying device for verifying a validity of a shuffle;
• a mixing device for generating an input cryptogram sequence assigned the order number κ from said mix net input cryptograms from 1 to the maximum number with respect to the order number κ of said plurality of integrated shuffle validity proving devices, for transmitting said input cryptogram sequence assigned the order number κ to said integrated shuffle validity proving device assigned the order number κ, and upon receipt of an output cryptogram sequence assigned the order number κ, for performing processing for recasting said output cryptogram sequence into an input cryptogram sequence assigned the order number κ+1, and for generating said mix net output cryptogram from an output cryptogram sequence received from said integrated shuffle validity proving device having the order number equal to the maximum number;
• a same conversion knowledge proof commitment integrating device for generating a same conversion commitment base assigned the order number κ from said common reference base from 1 to the maximum number with respect to the order number κ of said plurality of integrated shuffle validity proving devices, for transmitting said same conversion commitment base assigned the order number κ to said integrated shuffle validity proving device assigned the order number κ, and upon receipt of a same conversion knowledge proof commitment assigned the order number κ, for performing processing for recasting said same conversion knowledge proof commitment into a same conversion commitment base assigned the order number κ+1 to generate a same conversion knowledge proof commitment received from said integrated shuffle validity proving device having the order number equal to the maximum number as an integrated same conversion commitment;
• a commitment device for transmitting an integrated permutation proof commitment integrated with said permutation proof commitment and said integrated same conversion commitment to said integrated shuffle validity verifying device as an integrated commitment;
• a response integrating device, upon receipt of an integrated challenge value integrated with said challenge value from said integrated shuffle validity verifying device, for generating a challenge value assigned a number which is the maximum number plus one from said integrated challenge value, for transmitting a challenge value assigned the order number κ+1 to said integrated shuffle validity proving device assigned the order number κ from the number which the maximum number plus one to 1 with respect to the order number κ of said plurality of integrated shuffle validity proving devices, and upon receipt of a response assigned the order number κ, for performing processing for designating said response as a challenge value assigned the order number κ to generate an integrated response from a response assigned the order number 1;
• and
• an integrated permutation proof commitment decrypting device, upon receipt of said permutation proof commitment assigned the maximum number of the order number and said challenge value assigned the maximum number, for generating a cryptogram of an integrated permutation proof commitment integrated with said permutation proof commitment, for communicating with each of said plurality of integrated shuffle validity proving devices, and upon receipt of a distributed decryption result of said cryptogram of said integrated permutation proof commitment by a distributed secret key assigned the order number κ from each integrated shuffle validity proving device, for generating a result of decrypting a cryptogram of a integrated permutation proof commitment from said distributed decryption result, and for transmitting said result of decrypting a cryptogram to a corresponding integrated shuffle validity verifying device, and
• said one or plurality of permutation proof commitment integrating device generate a permutation storage commitment assigned the order number κ from 1 to the maximum number with respect to the order number κ of said plurality of integrated shuffle validity proving devices, transmit said permutation storage commitment assigned the order number κ to said integrated shuffle validity proving device assigned the order number κ, and upon receipt of a permutation proof commitment assigned the order number κ, perform processing for recasting said permutation proof commitment into a permutation storage commitment assigned the order number κ+1, and generate said integrated permutation proof commitment from a permutation proof commitment received from said integrated shuffle validity proving device having the order number equal to the maximum number.

A mix net system, comprising a plurality of integrated shuffle validity proving devices, each having a central processing unit for executing processing using a program stored within a memory of the central processing unit, forming part of a single shuffle validity proving device, provided in correspondence to an order number κ which is an integer indicating an order, upon receipt of a mix net input cryptogram, for supplying a mix net output cryptogram which is a result of shuffling said mix net input cryptogram, and a same conversion knowledge proof commitment and a permutation proof commitment for proving a validity of a shuffle in harmony with integrated shuffle validity proving devices whose order number are different from the order number of itself, subsequently upon receipt of a challenge value for authentication, for supplying a response corresponding to said challenge value, a proof integrating device for operating in harmony with said plurality of integrated shuffle validity proving devices, and an integrated shuffle validity verifying device having means for communicating with said proof integrating device, wherein:

• said integrated shuffle validity proving device comprises:
• a permutation proof commitment device, on a public key for commitment being applied and upon receipt of a permutation storage commitment including permutation proof texts by said integrated shuffle validity proving devices with the order number from 1 to κ−1 from outside, for adding a permutation proof text generated thereby to said permutation storage commitment to generate a permutation proof commitment, for encrypting said permutation proof commitment with said public key for commitment, and for transmitting encrypted permutation proof commitment outside,
• said proof integrating device comprises:
• communicating means with each of said plurality of integrated shuffle validity proving devices which are assigned the order number from 1 to a maximum number which is equal to the number of said plurality of integrated shuffle validity proving devices;
• and
• a permutation proof commitment integrating device, upon receipt of said permutation proof commitment including permutation proof texts with the order number from 1 to κ from said integrated shuffle validity proving devices, for transmitting said permutation proof commitment as a permutation storage commitment to an integrated shuffle validity proving device having the order number of κ+1 for requesting a permutation proof text, and
• said integrated shuffle validity verifying device receives a public key for mixing, a public key for commitment, a pseudo-public key, a common reference base, a random number, a mix net input cryptogram, and a mix net output cryptogram, and comprises:
• a commitment receiving device for receiving an integrated same conversion commitment and an integrated permutation proof commitment for proving a validity of a shuffle from said proof integrating device;
• a challenge value generating device for generating a challenge value which is a sequence of random values for transmission to said proof integrating device;
• a decrypted integrated permutation proof commitment receiving device, upon receipt of a permutation proof commitment assigned the maximum number which is the number of said plurality of integrated shuffle validity proving devices as the order number, and a challenge value assigned the maximum number, for generating a cryptogram of said integrated permutation proof commitment, and for verifying whether or not a decrypted integrated permutation proof commitment derived from a result of distributed decryption of said cryptogram of said integrated permutation proof commitment is correctly generated by communicating with said proof integrating device;
• a response receiving device for receiving an integrated response from said proof integrating device, and for receiving a decrypted integrated permutation proof commitment from said proof integrating device;
• and
• a verifying device for supplying a verification result indicating whether or not said mix net output cryptogram is correctly generated from said mix net input cryptogram by using said integrated same conversion commitment, said integrated permutation proof commitment, said challenge value, said integrated response, and said decrypted integrated permutation proof commitment.