Method for storing data blocks from client devices (1, 4) to a cloud storage system, the method comprising the steps of: d) storing an encrypted first data block, a challenge and a hash of the first data block of a first client device on the cloud storage system, e) determining if a hash of a second data block of a second client device stored on the cloud storage system equals the hash of the first data block, f) if yes, transmitting the challenge of the first data block from the cloud storage system to the second client device, wherein the method is characterised by the steps of: g) extracting, at the second client device, bits at randomly chosen bit positions or ranges contained in the challenge, hashing the extracted bits, encrypting the hashed bits with a public key of the first client device or of the second client device and uploading the encrypted bits from the second client device to the cloud storage system, h) storing the encrypted bits from the second client device on the cloud storage system, i) sending the challenge and the encrypted bits from the cloud storage system to the first client device. j) extracting, at the first client device, the bits at the randomly chosen bit positions or the ranges contained in the challenge, hashing the extracted bits, encrypting the hashed bits with a public key of the first client device or a public key of the second client device depending on the key chosen in step g) and comparing the such wise encrypted bits with the encrypted bits received in step i), k) if the comparison results in equality, encrypting a randomly generated symmetric key used for encrypting the first data block with the public key of the second client device and sending the encrypted symmetric key together with a new challenge containing bits at randomly chosen bit positions or ranges of the first data block from the first client device to the cloud storage system, and l) storing the new challenge and the encrypted symmetric key on the cloud storage system. d) storing an encrypted first data block, a challenge and a hash of the first data block of a first client device on the cloud storage system, e) determining if a hash of a second data block of a second client device stored on the cloud storage system equals the hash of the first data block, f) if yes, transmitting the challenge of the first data block from the cloud storage system to the second client device, g) extracting, at the second client device, bits at randomly chosen bit positions or ranges contained in the challenge, hashing the extracted bits, encrypting the hashed bits with a public key of the first client device or of the second client device and uploading the encrypted bits from the second client device to the cloud storage system, h) storing the encrypted bits from the second client device on the cloud storage system, i) sending the challenge and the encrypted bits from the cloud storage system to the first client device. j) extracting, at the first client device, the bits at the randomly chosen bit positions or the ranges contained in the challenge, hashing the extracted bits, encrypting the hashed bits with a public key of the first client device or a public key of the second client device depending on the key chosen in step g) and comparing the such wise encrypted bits with the encrypted bits received in step i), k) if the comparison results in equality, encrypting a randomly generated symmetric key used for encrypting the first data block with the public key of the second client device and sending the encrypted symmetric key together with a new challenge containing bits at randomly chosen bit positions or ranges of the first data block from the first client device to the cloud storage system, and l) storing the new challenge and the encrypted symmetric key on the cloud storage system.