The present invention describes a verification method which allows to ensure that the decryption process has been done honestly by the entity in charge of that.The method described in this invention is characterized by basing the verification of the correctness of the decryption of a set of encrypted messages in a proof demonstrating that the result of the operation with an operator φ of blocks of encrypted messages is equal to the encryption of the result of operating with the operator Θ blocks composed by the same messages, decrypted. In order to do that, a first input integrity proof is generated for each block of encrypted messages based on the operation φ of the encrypted messages, and the link with the output integrity proofs generated with the operation Θ of the decrypted messages composing each block is verified.