Public-key/asymmetric encryption where you can only leak the decrypted message by leaking your password

Question

A bunch of friends are using public-key encryption to send encrypted messages to each other using an open public forum. I.e. each friend has a public key (which you can use to encrypt messages for them) and a private key (which they use to decrypt messages for them).

Bob sends Alice the encrypted message $y$, which, when decrypted, yields the text $x=$"I'm going to murder you unless you send me \$1000". Alice, obviously angry, sends everyone the unencrypted message "Bob is a bad person. He said $x$ to me, which you can all verify by encrypting it with my public key to produce $y$, which he previously posted on our public forum." This is a full-proof method for Mary to expose Bob's message to everyone.

My question is, are there any public-key/asymmetric encryption schemes that would stop Mary from exposing Bob's encrypted message to everyone? For example, a scheme where the only way Mary could prove what Bob's decrypted message is would be to reveal her secret key (the password she uses to decrypt).

Edit: One idea I have is for an encryption scheme to allow for some kind of nonce, or secure randomization of what the message gets encrypted to. For example, if $x$ is the text Bob wants to encrypt, he can choose a random "nonce" $s$, and produce $y_s$. Then Mary can decrypt $y_s$ to get $x$, but she won't know $s$, so she can't just say that $x$ produces $y_s$ unless she reveals her secret key. I know this nonce concept exists in cryptography, but if anyone could give me an explicit example of how to implement it (perhaps with something simple like RSA), that would be hugely appreciated.

Answer 1

Your idea of an encryption method including a nonce, and in a way that Alice cannot recover the nonce is practical; however it doesn't solve your problem.

One possibility would be a variant of El Gamal; in this system, Alice's public key is a value $A= G^a \bmod p$, with $a$ being Alice's private key, and $G, p$ being public parameters (with $p$ being a safe-prime, and $G$ a Quadratic residue).

To encrypt a message $M < p/2$, Bob would select a random value $r$, and generate the ciphertext $G^r \bmod p, M^2 \cdot A^r \bmod p$.

To decrypt the pair $X, Y$, Alice would compute $M^2 = Y \cdot X^{-a} \bmod p$ (and then take the modular square root of $M^2$ to recover $M$).

If Alice gets the pair $X, Y$, she doesn't know the value $r$, and so, at first glance, showing that $G, A = G^a, X = G^r, Y \cdot M^{-2} = G^{ar}$ are a DH set is the Decisional Diffie-Hellman problem, which is hard in general; she could easily do so by exposing $a$, however for her, that would defeat the purpose.

However, what she could do is generate a zero-knowledge proof that $G^x = A$ and $X^x = Y \cdot M^{-2}$ have a common solution $x$ (which she can do, as she knows what that common solution is); this zero-knowledge proof would show that $M$ is the decryption, without exposing her private key.

This leads to the more general observation; if the decryption algorithm $D$ and the public key generation $Gen$ both run in polytime, then the statement that $D(a, C) = M \land (a, A) = Gen(seed)$ (for a public $C$ and the $M$ that Alice claims is the decryption is a statement in NP (with $a$ and $seed$ being the 'witnesses'), and for such a statement within NP, one can construct a zero-knowledge proof, showing that $M$ is a correct decryption.

So, unless Bob can claim he didn't actually send the ciphertext $C$ (and I assume that somehow it is assumed that somehow everyone knows he did), it doesn't sound like a solvable problem.

Answer 2

I think I found a solution to make this possible! The key concept is called Deniable Authentication, and the purpose is to know who's sending a message, but not being able to prove it to others. A practical and simple implementation can be found in Wei-Bin Lee, Chia-Chun Wu, Woei-Jiunn Tsaur (17 April 2006) (see section 3 "Our proposed protocol"). I'll outline the key points from it here.

If Sally the sender wants to send a message to Ryan the receiver, it's done like this.

1. Both Sally and Ryan each have public and secret keys.
2. Sally sends her message $M$, along with a randomly generated $(r , MAC)$, which uses a combination of $M$, as well as Sally's secret key and Ryan's public key.
3. Given $M$ and and $r$, Randy verifies that he can produce $MAC$ using his secret key and Sally's public key. If he does producing a matching $MAC$, it means that Sally did indeed send the message. Else, it's fake.

Why does a solution like this work? Because both Sally AND Ryan can produce $(r , MAC)$ along with $M$. So if Ryan goes to the police and says "Sally said $M$='I'm going to kill you', and this is the $(r, MAC)$ to prove it!!!". The police will just say "How do we know Sally produced those and not you?", and Sally can boast the same thing.

So because both sender and receiver are capable or producing the same thing, neither of them can prove to other parties which of them said it.

If, on top of that, you also want encryption of the message, it's easy for Sally and Ryan to make a shared secret (from diffie-hellman) that they use to encrypt their messages.

Anyways, case closed I think! Again, if you want the actual math that implements this protocol, it's quite short and simple. Just check the paper.

Answer 3

I believe what you are looking for is impossible. However, I will suggest you another way to tackle this issue that might be helpful which is based on plausible deniability.

First, I'll try to explain why I believe it is impossible to force Alice to leak her secret key when proving to others what message she has decrypted. Today, with the rise of general circuit Zero-Knowledge proofs (e.g. STARKS and SNARKS) almost any relation between a secret value and a public value can be proven to other parties. (Any relation that can be expressed by polynomial number of gates of $AND$ and $OR$)

Generally, a public key cryptosystem is defined by a tuple of $(Gen, Enc, Dec)$:

• $(pk, sk) \leftarrow Gen(\lambda, rnd)$: the key generation algorithm which generates public key $pk$ and secret key $sk$ according to a security parameter $\lambda$ and a random string $rnd$.

• $c \leftarrow Enc(m, pk, rnd)$: the encryption algorithm which encrypts message $m$ with public key $pk$ and creates the ciphertext $c$. This algorithm must be a probabilistic algorithm which means it should generate different ciphertext each time we run it. Otherwise, it does not have lowest level of public-key security (IND-CPA).

• $m \leftarrow Dec(c, sk)$ the decryption algorithm is deterministic.

If Alice can turn $Dec$ into a Zero-Knowledge circuit with a private value of $sk$ then she can prove that a known ciphertext $c$ decrypts into $m$ with the secret key $sk$ that corresponds to $pk$. No matter what is the public key cryptosystem.

However, there can be another way to solve the problem using off-the-record messaging (OTR) which makes a public-key based communication deniable.

In OTR, any recorded messaging transcript can be fabricated by any side of the communication. Accordingly, it is easy to deny everything.