Encrypted deduplication: who can test a file guess?

18 October 2026 / Source review

Ask where duplicate detection happens and who can obtain a matching identifier. "Encrypted and deduplicated" alone does not describe a confidentiality guarantee.

Start with the matching layer

Restic identifies blobs by a hash of their plaintext, while newly encrypted data uses random nonces and repository master keys. Its index lets a trusted client reuse stored blobs. Duplicate detection need not compare independently produced ciphertexts. Repository access belongs to the trust model: sharing repository credentials with an adversary is explicitly excluded. [5]

That differs from Farsite's convergent encryption: derive a content key from the file, encrypt the content deterministically, and wrap the content key separately for authorized readers. Matching content has matching data ciphertext even when reader metadata differs. Equality is deliberately exposed. [1, section 3]

Different matching layers, not a ranking of product security
Design	Where reuse is recognized	Boundary to inspect
Trusted-client repository	Client's plaintext blob index [5]	Repository credentials and client integrity
Convergent encryption	Matching content ciphertext [1]	What an observer already knows about the message
DupLESS	Content ciphertext within a key-server domain [3]	Key-service access, secret isolation and rate limits
Cross-user upload suppression	Service reports or exposes a duplicate [4]	Whether the response reveals another user's data presence

A strong hash cannot make predictable content secret

Message-locked encryption formalizes encryption whose key comes from the message. Its security treatment distinguishes privacy from tag consistency: recognizing a duplicate and protecting its contents are different requirements. [2]

Convergent encryption permits offline testing of candidate messages against an observed ciphertext. A short list of plausible files can therefore matter more than nominal cipher key length. DupLESS addresses that boundary with a separate authenticated key service: an oblivious PRF contributes server-held secret material. A compromised client must make rate-limited online queries; disclosure of the server secret restores the ordinary message-predictability limitation. Equality remains visible. [3, sections 3 and 8]

An oblivious PRF lets the client obtain the function output without revealing its input to the server or learning the server key. RFC 9497 describes prime-order-group protocols; it is an Informational IRTF document, not an IETF standard or the RSA-based protocol used in the 2013 DupLESS prototype. The primitive alone is not a storage access policy. [6]

Upload suppression creates a separate observation

Harnik and colleagues examine source-side, cross-user deduplication: a client can observe that a proposed upload was already present. This does not inherently reveal which user stored it. The issue is distinct from inspecting a stolen ciphertext; the service response itself supplies evidence. Always uploading before server-side deduplication removes that particular upload-suppression signal, at the cost of bandwidth savings, not all possible side channels. [4, sections 2 and 3.2]

Their tests describe historical service versions. They do not establish the behavior of today's providers. Likewise, encryption does not promise invisible lengths or access patterns: Restic's threat model explicitly discusses observable repository metadata. [5]

Who proves possession to whom?

A matching identifier should not silently become permission to retrieve a file. Halevi and colleagues describe a historical deduplication design that made this mistake. Their proof of ownership makes the client demonstrate possession beyond a short digest. Here, ownership means holding data, not legal title or an access-policy decision. The author slides explicitly reverse the prover/verifier roles relative to remote storage auditing. [7, slides 10-13 and 25-31]

Read the security statement, not just the word proof
Mechanism	Prover / verifier	Question addressed
PoW	Client / storage service	Does this claimant hold the content beyond short leaked information? [7]
PDP	Storage service / client or auditor	Can the service answer the specified possession challenges? [8]
PoR	Storage service / client or auditor	Does sufficient audit success imply file extraction under the model? [9]

The original PDP work samples blocks and combines authentication information into compact responses. Its S-PDP and E-PDP variants make different claims; a family name alone does not identify the guarantee. [8, sections 2 and 4.3]

Version caveat: the authors' revision record reports an October 2007 correction to the public-verifiability proof, with a restriction on block size. Check the exact revision and its block-size conditions before relying on this property; neither this comparison nor our sampling calculation validates an implementation. [10]

PoR adds an extraction requirement. In Shacham and Waters' model, an extractor must recover the file from a prover with sufficient challenge-success probability; this is not a logical consequence of one accepted response. Suitable erasure coding connects recovery of enough encoded blocks to the entire file. Public verification and public extraction are separate properties. [9, section 2 and Appendix A]

These mechanisms can be combined, but are not interchangeable. The PoW slides assume bounded leakage and remaining uncertainty about the file; they do not promise security for arbitrary prior knowledge. We reviewed that author presentation and publication record, not the inaccessible full PoW manuscript or its complete proofs. [7, slides 26-31 and 41-46]

What a 460-block sample can miss

For N blocks, M fixed missing blocks and C distinct uniformly sampled positions, the probability of hitting at least one missing block is 1 - choose(N-M, C) / choose(N, C). This is the finite-population calculation behind the PDP paper's sampling discussion. [8, section 5.1]

Hesela calculation: N = 10,000 blocks, C = 460 distinct positions
Missing blocks M	Missing fraction	Chance of a hit
0	0.00%	0.00%
1	0.01%	4.60%
10	0.10%	37.57%
100	1.00%	99.12%

The familiar result above 99% assumes 100 missing blocks here. With only one missing block, the same challenge hits it with probability 4.6%. This assumes a fixed missing set, unpredictable uniform selection and perfect recognition of any sampled missing block. It is sampling arithmetic, not a cryptographic security analysis or a measured failure rate.

A passing challenge does not give a 99% posterior probability that the file is intact. That inference needs a prior model of missing data and the actual protocol. Nor does a high sampling hit rate reconstruct a file. The calculation module and generated JSON expose the inputs, formula, assumptions and source hash.

Repeating an audit is not a complete sweep

Under the same missing-block model, R fresh independent rounds have hit probability 1 - (choose(N-M, C) / choose(N, C)) ** R. This is Hesela's extension: multiply the per-round miss probabilities, then subtract from one. Blocks are distinct within each round but can recur between rounds.

With one missing block out of 10,000, 97 independent rounds of 460 positions still fall below 99% detection. At 98 rounds, the chance is 99.01%, after 45,080 sampled positions, including repeats. By contrast, checking every block once necessarily encounters that missing block in this idealized model. These counts are not measured physical reads, transfer volumes or protocol execution costs.

The object version and missing set must stay fixed throughout those rounds. Reusing the same 460 positions leaves the hit probability at 4.6%; it does not earn the independent-round improvement. Changing data, predictable challenges or an adaptive responder require a different analysis.

Operational consequence, drawn by Hesela: even a sound PoR for a ciphertext object does not test whether the operator still has the decryption key, selects the required backup version, or can start the restored application within its recovery-time target. Define the protected object and retain a separate restore test. A proof of a logical object's retrievability also makes no standalone claim about independent physical replica placement.

Review the trust boundary before the savings ratio

For an architecture review, Hesela recommends writing down five answers:

Is matching limited to one repository, one organization or unrelated tenants?
Does the observer see plaintext identifiers, ciphertext equality, upload outcomes or only stored packs?
Can that observer obtain candidate keys, and does compromising a client differ from compromising the key service?
Which party proves possession, which object/version is covered, and where is full recovery actually tested?
Which leakage is accepted, and what protects credentials, key recovery and sensitive files excluded from deduplication?

DupLESS evaluated file operations and a VM-image corpus, not every backup workload. Its design falls back to randomized encryption when the key service is unavailable. That preserves a write path while sacrificing deduplication for those writes. We have not reproduced its benchmarks; historical overheads are not a current sizing guide. [3, sections 3, 6 and 7]

Capacity, recovery and confidentiality need separate evidence. Continue with restore locality and encryption and integrity. Corpus entries: convergent encryption, deduplication side channel and data deduplication.

Primary sources

Architecture review, not a cryptographic proof or implementation audit. No provider was probed and no cryptographic system was implemented.