A method for re-keying encrypted and deduplicated data, wherein a data file (f) is stored chunkwise on a cloud storage entity, 'SE', each of the data file chunks being encrypted with a dedicated global private key (k), and each of the data file chunks having a corresponding secret (x i) stored at a corresponding index in a key table, the key table being stored locally by an assist server, the method comprising a client performing a non-interactive Diffie-Hellman key exchange using a public key y = g x of an assist server, 'AS', and a hash value (h = H(f)) of a data file chunk to be re-keyed, thereby obtaining a chunk index y h; said client computing a blinded hash value ĥ = h*g 1 r for some random value r, wherein g 1 is a generator of a group of order p; said client sending a re-key request to said AS, comprising said chunk index y h and said blinded hash value ( ĥ); said AS, upon receiving said request, updating said key table at said chunk index with a new generated secret (x i) and a corresponding new public key y i =g 1 xi; said AS computing a signature ( ŝ) as the power of the blinded hash value to the new randomly generated secret (x i); said AS sending said signature ( ŝ) together with said new public key y i; said client, upon receiving said signature ( ŝ) together with said new public key y i, computing an unblinded signature (s) as the product of said received signature and the power of the received new public key to the opposite of the random value r; said client generating said dedicated global private key (k) as the hash of the unblended signature (s); said client re-encrypting said data file chunk based on the dedicated global private key and requesting said AS to store the re-encrypted chunk in said SE. wherein a data file (f) is stored chunkwise on a cloud storage entity, 'SE', each of the data file chunks being encrypted with a dedicated global private key (k), and each of the data file chunks having a corresponding secret (x i) stored at a corresponding index in a key table, the key table being stored locally by an assist server, the method comprising a client performing a non-interactive Diffie-Hellman key exchange using a public key y = g x of an assist server, 'AS', and a hash value (h = H(f)) of a data file chunk to be re-keyed, thereby obtaining a chunk index y h; said client computing a blinded hash value ĥ = h*g 1 r for some random value r, wherein g 1 is a generator of a group of order p; said client sending a re-key request to said AS, comprising said chunk index y h and said blinded hash value ( ĥ); said AS, upon receiving said request, updating said key table at said chunk index with a new generated secret (x i) and a corresponding new public key y i =g 1 xi; said AS computing a signature ( ŝ) as the power of the blinded hash value to the new randomly generated secret (x i); said AS sending said signature ( ŝ) together with said new public key y i; said client, upon receiving said signature ( ŝ) together with said new public key y i, computing an unblinded signature (s) as the product of said received signature and the power of the received new public key to the opposite of the random value r; said client generating said dedicated global private key (k) as the hash of the unblended signature (s); said client re-encrypting said data file chunk based on the dedicated global private key and requesting said AS to store the re-encrypted chunk in said SE.