A method for performing a proof of retrievability for data stored on a storage entity, 'SE' for a client, comprising the steps of: - Dividing, by said client, a file to be stored into a number of chunks, - Computing, by said client, a first secret key for each chunk of said file and a second secret key for encoding the chunks using different secure key generation functions - Computing, by said client, for each chunk a chunk identifier using said computed first secret key - Providing said computed chunk identifiers to said SE, - Checking, by said SE, if one or more of said chunks have already been stored based on said computed chunk identifiers, - In case one or more of said chunks have not already been stored: ∘ Encoding, by said client, the corresponding chunks with said second secret key, ∘ Storing, by said SE, said encoded chunks and chunk tags computed for each chunk using said first secret key, - Computing, by said client, a random challenge, said random challenge comprising a set of one or more coefficients and corresponding indices for said chunks, - Providing, by said client, said random challenge to said SE, - Computing, by said SE, a signature with the sum over said set of the product of said coefficients of said challenge and corresponding stored chunk identifiers on said SE, - Computing, by said SE, a file part with the sum over said set of the product of said coefficients of said challenge and corresponding stored chunks, - Checking, by said client, if said computed signature matches with the computed file part and local information of said client to be used for generation of a chunk identifier, and - Verifying, by said client, retrievability based on a result of said checking. - Dividing, by said client, a file to be stored into a number of chunks, - Computing, by said client, a first secret key for each chunk of said file and a second secret key for encoding the chunks using different secure key generation functions - Computing, by said client, for each chunk a chunk identifier using said computed first secret key - Providing said computed chunk identifiers to said SE, - Checking, by said SE, if one or more of said chunks have already been stored based on said computed chunk identifiers, - In case one or more of said chunks have not already been stored: ∘ Encoding, by said client, the corresponding chunks with said second secret key, ∘ Storing, by said SE, said encoded chunks and chunk tags computed for each chunk using said first secret key, ∘ Encoding, by said client, the corresponding chunks with said second secret key, ∘ Storing, by said SE, said encoded chunks and chunk tags computed for each chunk using said first secret key, - Computing, by said client, a random challenge, said random challenge comprising a set of one or more coefficients and corresponding indices for said chunks, - Providing, by said client, said random challenge to said SE, - Computing, by said SE, a signature with the sum over said set of the product of said coefficients of said challenge and corresponding stored chunk identifiers on said SE, - Computing, by said SE, a file part with the sum over said set of the product of said coefficients of said challenge and corresponding stored chunks, - Checking, by said client, if said computed signature matches with the computed file part and local information of said client to be used for generation of a chunk identifier, and - Verifying, by said client, retrievability based on a result of said checking.