An encryption server receives encrypted data which is encrypted by using a public key of a first user and which is added with auxiliary information calculated using a combination of a secret key and the public key of the first user and data to be encrypted. Then, the encryption server generates re-encrypted data obtained by re-encrypting the encrypted data using the auxiliary information added to the encrypted data, a public key of a second user, and encrypted information related to the secret key of the first user which is encrypted with the public key of the second user.