In a decryption apparatus according to an embodiment, a holding device pre-holds a verification formula. A determination device performs a calculation based on the verification formula read from the holding device by substituting, into the verification formula, the part of the re-encrypted data received from a re-encryption apparatus and the public key of a re-encryption key generation apparatus and the private key of the decryption apparatus, to determine whether or not the verification formula holds true. An output device outputs verification success when a result of the determination indicates that the verification formula holds true.