I want to provide a service that encrypts and decrypts documents and I want to provide the users with proof that I haven't stolen their secret key and read their documents.

I know I can prove when a document was last modified with cryptographic timestamping. Is it possible to prove a document was or was not encrypted/decrypted in a given time period?

Off the top of my head, I'm thinking maybe there's some way to arrange that some kind of proof-of-work would be needed to encrypt/decrypt a document, but I'm not comfortable with inventing my own crypto.

  • $\begingroup$ Your solution sounds good. Of course it's not iron-clad (anyone with sufficient computing power may forge a POW, depending on the scheme) but it will do for most practical purposes. You're not rolling your own crypto. Other than that, I dont understand the question, do you mean you want a system that tells you when a document was decrypted? $\endgroup$ – rath Jun 13 '13 at 15:42
  • $\begingroup$ Clarification: When I say the adversary can forge a POW, I assume he can also alter the contents of the document, and the MAC (if present) applies to both the document and the proof-of-work. $\endgroup$ – rath Jun 13 '13 at 15:45
  • 1
    $\begingroup$ Given that you can make multiple copies of the same document I don't really see how you can be assure that a document wasn't encrypted/decrypted. $\endgroup$ – Alexandre Yamajako Jun 13 '13 at 16:36
  • 1
    $\begingroup$ Can you control access to the ciphertext? (That is, can you log when people downloaded it, for example?) If so, then you could use write-once memory to log who downloaded it and when, and if your authentication includes knowledge of the key, then you can assume it was decrypted when downloaded. That seems a fairly safe assumption. After all, once the ciphertext leaves your system, your options become much more limited. $\endgroup$ – Reid Jun 13 '13 at 17:06

Updated answer:

No, this is not possible with cryptography. You have the ciphertext and you have the key. For all anyone knows, you could have made a copy of those to some other computer and decrypted the ciphertext without telling anyone. There's no way (with cryptography) to prove you haven't done that.

One approach would be to implement a secure service and hire an independent auditor to audit your code and architecture and certify that you appear to have set things up in a way that protects your customers' data. You could hire an independent security pro to review your system and write a public report that customers can view. I don't know if this would give potential customers a better sense of comfort or if it would be worth the money.

The only approach I can think of, to solve this through technical means, would be to use trusted computing. Trusted computing relies upon trusted hardware (TPMs), and its support for remote attestation would allow you to prove to others what code you are running. You could publish the source to your software to allow anyone to verify that your software doesn't make a copy of their keys or their data, and use remote attestation to prove that you're using that good software.

However, using trusted computing in this way is extremely complicated. Trusted computing is bleeding-edge stuff; it's an engineering and management hassle of major proportions. Moreover, most customers probably won't have the patience, skills, or desire to undertake all of the tasks that would be required to verify that your system works properly.

So, I think there's no technical solution for your problem. You'll have to rely upon your customer's trust, your reputation, contractual guarantees, and other social/legal means, instead of technical solutions.

A comment: your problem is more an information security problem than a cryptography problem. Are you familiar with IT Security?

Original answer:

I think you need to define the problem better, to identify who are the principals/participants and what is the threat model.

If the decryptor knows the ciphertext and decryption key and wants to subvert the protocol, you cannot prove that the decryptor didn't decrypt the ciphertext.

The decryptor can prove that he did decrypt the ciphertext (using a zero-knowledge proof of knowledge, possibly with some timestamping). However, he cannot prove that he read the decrypted message or paid attention to it or acted on it, so I suspect this will be basically useless in practice.

If you can limit access to the ciphertext or the decryption key, then you can prove some partial statements. For instance, if you don't release the ciphertext to anyone until time $t$, you can prove that no one could possibly have decrypted it before time $t$. If you know the key, though, you won't be able to prove that you didn't release it before time $t$ (except possibly through use of TPMs / trusted computing), so you'll probably need to be trusted for this to be meaningful.

There are many other possible scenarios -- to propose a specific solution, we'll probably need to know the threat model and requirements in a bit more detail.

  • $\begingroup$ The scenario is this - I want to provide a service that encrypts and decrypts documents and I want to provide the users with proof that I haven't stolen their secret key and read their documents. $\endgroup$ – Michael Jun 14 '13 at 9:44
  • 1
    $\begingroup$ @Michael That should be impossible. Basically you are trying to prove that you do NOT know something. Whatever protocol you use for that, you can always just pretend to not know. $\endgroup$ – Maeher Jun 14 '13 at 17:06
  • $\begingroup$ Right, great answer, thanks for that. I'll just publish the source and hope that's enough for the users. $\endgroup$ – Michael Jun 14 '13 at 17:12
  • 1
    $\begingroup$ @Maeher That's not quite true: you can generate the key elsewhere (e.g. on the client's machine). But that doesn't work in Michael's scenario since it doesn't let him decrypt ever. $\endgroup$ – Gilles 'SO- stop being evil' Jun 14 '13 at 17:27
  • $\begingroup$ That's really not the point. Even if the service provider does not know the key, they have no way to prove it. $\endgroup$ – Maeher Jun 14 '13 at 22:11

It is possible for Bob and Alice to store many files on some host file server using a host-proof protocol -- i.e., in such a way that even the sysadmins of that server cannot decrypt and read the plaintext of those files. You may be interested in browsing the questions with the tag.

As far as I know, there is only one way to prove that those sysadmins definitely have not read the plaintext of those files:

  1. Never send the plaintext of those files directly to the host. Bob always encrypts each file before he sends it to the host.

  2. Never send the file decryption key to the host. (Except perhaps in encrypted form, encrypted by some other key that is never sent in plaintext to the host server).

One way to do that is for Bob to generate encrypted files in OpenPGP format, and send those encrypted files to the host server. (At the time of encryption, Bob uses his own public key and Alice's public key, in order to generate a file that can only be decrypted using either his own corresponding private key, or Alice's corresponding private key). OpenPGP includes a message authentication code that can be used to prove that the sysadmins definitely have not modified the files, or replaced them entirely with files they created.

I hear that many people use other techniques that have some advantages and some disadvantages compared to standard OpenPGP. Those techniques include , gzip --rsyncable, rsync, rsyncrypto, and various combinations.

(There are many interesting ways of proving that a document was decrypted, but it sounds like that's not particularly useful in your application).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.