The present invention provides a certified shuffle-decrypting system, which does not require shuffled encrypted texts to be output, and in which the amounts of calculation and certificates are minimized to allow efficient processing, and the certified shuffle-decrypting system generates shuffle-decryption certificates certifying that multiple encrypted texts have been shuffle-decrypted correctly, and verifies, based on the shuffle-decryption certificates, whether or not the shuffle-decryption has taken place correctly. This system comprises: a certified shuffle-decryption device for shuffle-decrypting the multiple encrypted texts to generate the shuffle-decrypted texts, and for generating the shuffle-decryption certificates; and a shuffle-decryption verification device for verifying whether or not the shuffle-decryption has taken place correctly, by referring to the generated shuffle-decrypted texts and the shuffle-decryption certificates for the shuffle-decrypted texts.