1
$\begingroup$

I'm trying to create a message-transfer system where

  1. The encrypted messages are stored in a public database.
  2. It is possible to verify who is the sender of this message.
  3. The sender cannot prove to anyone else the content of the message. I mean, he/she cannot re-encrypt the plaintext message and match with the ciphertext on the public database to prove the content of the message to someone else.

Is there any existing encryption protocol that can get the job done? This encryption protocol can be interactive/non-interactive, symmetric/asymmetric or anything else. It just needs to get the job done.

I'm new to cryptography. Please pardon me if my question is too dumb or has been answered already. I tried to look for solutions online but failed to find any practical solution. While searching I came to know a little bit about deniable encryption and zero-knowledge proofs. Can they help with my matter in any way?

Thanks in advance.

Improve this question
$\endgroup$
4
  • $\begingroup$ "he/she cannot re-encrypt the plaintext message and match with the ciphertext on the public database to prove the content of the message to someone else" How would you expect this to be the case if the encrypter can simply store all the information locally, including keys, any random vectors and the plaintext / ciphertext? You need third party support, and in that case you can simple also perform the encryption at that third party. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 20, 2020 at 2:41
  • $\begingroup$ @MaartenBodewes Isn't it possible to create some sort of interactive protocol where the sender does a portion of the calculation and the rest of the calculation is done at the server before being saved to the database? I don't have any problem with using a third party. But I don't want the whole calculation to be done there or expose the sender's private key to the server. $\endgroup$
    – Tanmoy Krishna Das
    Commented Jan 20, 2020 at 4:41
  • 1
    $\begingroup$ I suppose you are looking for a scheme where Alice does some stages of the encryption process $C_1 = Enc_A(m)$, and, after that, send that to Bob. Bob finishes the process $C = C_2 = Enc_B(C1)$. But, in the end, Alice can prove she knows m without revealing it. Is it? $\endgroup$
    – Crypto Learner
    Commented Jan 20, 2020 at 12:34
  • $\begingroup$ @McFly Yes, this is exactly what I want. $\endgroup$
    – Tanmoy Krishna Das
    Commented Jan 20, 2020 at 13:26

1 Answer 1

Reset to default
2
$\begingroup$

Deniable encryption should provide what you want. In a deniable encryption scheme, in addition to the usual $(\mathsf{KeyGen},\mathsf{Encrypt},\mathsf{Decrypt})$ algorithm, you have an algorithm $\mathsf{Explain}$ that takes as input a ciphertext $c$ (which can be any ciphertext) and a message $m$, and outputs a random coin $r$ such that the triple $(m,r,c)$ is indistinguishable from the distribution obtained, given $m$, by sampling a uniformly random coin $r$ and constructing $c$ as $\mathsf{Encrypt}(m;r)$. That is, even though a ciphertext can be correctly decrypted given the secret key, for any plaintext you can find a random coin which "explains" the ciphertext as an encryption of this plaintext.

Given a deniable encryption scheme, a proof that you correctly encrypted a message can never be convincing, because you can always, for any ciphertext $c$ and plaintext $m$, find coins $r$ such that $c = \mathsf{Encrypt}(m;r)$ - and that does not mean that $c$ will necessarily decrypt to $m$. Hence, in such a scheme, if you only know the public key, it is fundamentally infeasible to prove that you encrypted a given message (if you know the secret key, it's a different matter, but that does not seem to be the case in your question).

Note that your requirement 2 can be achieved using any standard authentication mechanism on top of deniable encryption.

Deniable encryption was first constructed in this paper, but this is only of theoretical interest, and does not lead to any efficient instantiation in practice. There exists alternative constructions (see also the many follow ups) that only achieve an inverse-polynomial "deniability", in the sense that it is possible to distinguish "true random coins" from those obtained through $\mathsf{Explain}$ with inverse polynomial probability.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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