Patent ID: 7240195

Claim:
A certified shuffle-decryption device for shuffle-decrypting multiple encrypted texts to generate shuffle-decrypted texts and for generating shuffle-decryption certificates for certifying that the shuffle-decryption has correctly taken place, comprising: a shuffling unit into which the multiple encrypted texts and the public keys are input and which shuffles the order of the multiple encrypted texts and encrypts them with the public keys, thereby generating multiple shuffled encrypted texts; a decrypting unit into which the multiple shuffled encrypted texts and secret keys are input and which decrypts the shuffled encrypted texts with the secret keys, thereby generating multiple shuffle-decrypted texts; an identical conversion certifying unit which generates a certificate certifying that it knows the ordering relationship among the encrypted texts before and after the shuffling as well as random numbers used for encryption, and when each of the input encrypted texts consists of multiple integer elements, that it knows that the elements of each encrypted text have been shuffled in the same order and converted with the same random numbers; a substitution certifying unit which generates a certificate certifying that the input encrypted texts have been correctly shuffled; a response generating unit which generates responses for the identical conversion certifying unit and the substitution certifying unit; and a decryption certifying unit which generates, based on the responses, a certificate certifying that the shuffle-decrypted texts are obtained through correct decryption of the shuffled encrypted texts using the secret keys, and wherein the identical conversion certificates, the substitution certificates and the responses are output as a shuffling certificate, and the certificates generated by the identical conversion certifying unit, the substitution certifying unit and the decryption certifying unit us well as the responses generated by the response generating unit are output as the shuffle-decryption certificates.