Bob's goal: Receive data E = E(D) (encryption of D) from Alice that he knows for sure is encrypted and that he can't possibly decrypt (without brute force). This gives his data backup company peace of mind - no need to worry about what sorts of data he stores (copyright issues, etc.). When Bob sends E back to Alice, she can decrypt it with a key known only to her to recover D.
- Alice has key A, known only to her.
- Bob has nonce N that he sends to Alice, so Alice knows A and N.
Is it possible for Alice to encrypt her data D with both keys A and N and send E(D) to Bob, such that Bob can verify that N (plus some other data, in this case A, unknown to him) was used for the encryption?
In this case the problem is solved (as far as I can see), because now he can simply destroy the nonce N, and now he knows for sure he only has encrypted data in his possession that only Alice could possibly decrypt.
Are there other ways? TLDR: The goal is zero-knowledge data storage with the added peace of mind of knowing you're only storing unrecoverable encrypted data. Is there a way around using a temporary nonce?