# Proving the right encrypted message was sent

Total amateur to crypto here but I've searched and searched and am at the extent of my knowledge. I've gone down several avenues to satisfy what I'm looking for but I'm just going to describe what I'd like to achieve and see what comes back.

I am creating a transactional peer to peer pub/sub network and I need the following:

A publisher, Alice, broadcasts to the network an encrypted message. She will then make money by selling the key to decrypt that message to subscribers (say Bob). I need an encryption scheme such that anyone on the network (say Charles) can look at the broadcast from Alice (which can include other items separate from the ciphertext, if needed) and the transaction between Alice and Bob and verify that Alice gave the correct key to Bob without having the key himself.

• Sounds like a zero knowledge proof might help? en.m.wikipedia.org/wiki/Zero-knowledge_proof Commented Jan 12, 2020 at 10:49
• your description is not clear to me. Alice broadcast an encrypted message (ciphertext). Then Alice wants to sell a key. Ok, then what's the transaction between Alice and Bob, and how it's related to ciphertext and key? Commented Jan 31, 2020 at 15:57

You can try to construct a simple scheme based on a one-time-pad, although it may be difficult to adapt it in a practical environment.

1. Let $$H(..)$$ be a hash function.
2. Let $$\langle .., .. \rangle$$ be a data structure.

Assuming Alice and Bob key pairs: $$a \times G \mapsto A$$ and $$b \times G \mapsto B$$.

1. Alice publishes a message $$m$$ using the encryption $$k$$ key via $$\langle k + m, K, M \rangle$$, where $$k \times G \mapsto K$$ and $$m \times G \mapsto M$$ are elliptic curve points.

2. The transaction of the key starts with a Diffie-Hellman key exchange where $$H(a \cdot b \times G) = H(b \cdot a \times G)= x$$, where $$x \times G \mapsto X$$ is a commitment from both parties, negotiated in the open.

3. Bob pays to Alice and Alice sends $$k + x = r$$. Bob gets the key via $$r - x = k$$.

4. Charles is able to verify that $$k$$ is the key for $$(k + m) \times G \stackrel{?}{=} (K + M)$$ and that $$(k + x) \times G \stackrel{?}{=} (K + X)$$ constains the same key.

This works fine for small message, by following the requirements of one-time-pad. But you should be careful when expanding to bigger messages. Note that, for this purpose, the message is also encrypted via $$m - x$$ or $$x - m$$. The key $$k$$ is reused, so it's not a correct one-time-pad; the $$k$$ key can be replaced with the $$x$$ key in this situation. The scheme breaks in the weakest key.

You need to expand the scheme so that it not suffers from the same problems as the AES-ECB. Moreover, I would advise to construct a formal proof of security before using such a scheme.

• What is $H$, $\langle \ldots \rangle$ and $+$? Where is the one-time pad? I think the standard notation for elliptic curve scalar multiplication is $[k]G = K$ not $k \times G \mapsto K$. Commented Feb 11, 2020 at 15:39
• If $m$ has low entropy, you can easily brute-force values of M at a rate of tens of thousands per second on a modern CPU, or much faster on a GPU. However, if you are using this scheme to communicate a symmetric key with sufficient entropy, then your scheme looks good to me. Commented Mar 2, 2022 at 21:42

A simple way to achieve this is with asymmetric cryptography, by letting both Alice and then Bob broadcast a message to the network with the shared private key. This message should be a digital signature, proving that both Alice and Bob have knowledge of that private key.

• This requires Bob to cooperate. If Bob doesn't cooperate then Alice cannot prove that the key that Bob got, is really a suitable key. Commented Jan 12, 2020 at 0:57