> If your encryption is deterministic, the second client can check with the server that Hash(Enc(chunk)) is the same on the client and server

but the chunk on the server was encrypted using a different public-key, so how can hash(pub-key-1(chunk)) == hash(pub-key-2(chunk)) ?

Isn't only the decryption keys encrypted to the public keys?

They use nacl cryptobox primitive.

This means that you are right. Alas, the decryption key (they symmetric key used to encrypt this particular message) is derived deterministically from the private key and nonce. The nonce they use is the hash of the chunk. Thus, the same chunk will always be encrypted with the same symmetric key.

> Isn't only the decryption keys encrypted to the public keys?

from the readme, it appears (to me at least), that chunks are encrypted using public-keys. concretely, the following lines :

"Every time rdedup saves a new chunk file, it's data is encrypted using public key so it can only be decrypted using the corresponding secret key. "