A re-encrypted data verification program used in a system comprising an encryption apparatus executing an encryption process on plain data using a public key corresponding to a private key of a re-encryption key generation apparatus and transmitting resultant encrypted data to a re-encryption apparatus, the re-encryption apparatus then executing a re-encryption process on the encrypted data using a re-encryption key without decrypting the encrypted data and transmitting resultant re-encrypted data to a decryption apparatus, the decryption apparatus executing a verification process on the re-encrypted data using a public key of the re-encryption apparatus, and executing a decryption process on the re-encrypted data using a private key corresponding to a public key of the decryption apparatus 50 to obtain the plain data, the re-encrypted data verification program being executed by a processor in the decryption apparatus comprising a storage means storing the public key of the re-encryption key generation apparatus and the private key of the decryption apparatus, the re-encrypted data verification program being stored in a non-transitory computer-readable storage medium, the re-encrypted data verification program characterized by comprising: a first program code allowing the processor to execute a process of holding a program code with a verification formula pre-described therein, the verification formula holding true when being calculated by substituting into the verification formula, a part of the re-encrypted data used for the re-encryption system and the public key used for the encryption process executed on the encrypted data before the re-encryption process is executed on the re-encrypted data; a second program code allowing the processor to execute a process of performing a calculation based on the verification formula by substituting into the verification formula, the part of the re-encrypted data received from the re-encryption apparatus and the public key of the re-encryption key generation apparatus read from the storage means, to determine whether or not the verification formula holds true; and a third program code allowing the processor to execute a process of outputting detection success indicating that the public key used for the encryption process executed on the plain data is the public key of the re-encryption key generation apparatus when a result of the determination indicates that the verification formula holds true. a first program code allowing the processor to execute a process of holding a program code with a verification formula pre-described therein, the verification formula holding true when being calculated by substituting into the verification formula, a part of the re-encrypted data used for the re-encryption system and the public key used for the encryption process executed on the encrypted data before the re-encryption process is executed on the re-encrypted data; a second program code allowing the processor to execute a process of performing a calculation based on the verification formula by substituting into the verification formula, the part of the re-encrypted data received from the re-encryption apparatus and the public key of the re-encryption key generation apparatus read from the storage means, to determine whether or not the verification formula holds true; and a third program code allowing the processor to execute a process of outputting detection success indicating that the public key used for the encryption process executed on the plain data is the public key of the re-encryption key generation apparatus when a result of the determination indicates that the verification formula holds true.