# Multiple (RSA) public key encryption how to verify others received the same information? Non-deterministic encryption

I have an RSA system between multiple parties. Alice takes the targets (Bob and Oliver) public keys and encrypts a message using them and sends it to them. All parties know each other's public keys and the ciphertexts received.

I wanted to verify that all the targets are receiving the same message, so I thought Bob could take Oliver's public key and encrypt the received message(after decrypting with his own private key) and compare it but I'm using non-deterministic encryption, therefore, the ciphers produced are different for the same message and public key.

I know using deterministic encryption prone to attacks so I was wondering if there are any other solutions out there or do I have to risk using deterministic. For reference, I'm using JavaScript and AES for encryption.

How do I verify that Oliver and Bob receive the same message without them having to send it to each other?

• This is not a homework question, it's for a project and it doesn't have to be restricted to RSA if it there is another solution involving Public Key Cryptography. – James Crash Jan 3 '20 at 8:41
• Yes it is beneficial to Alice for Bob and Oliver not to receive the same message. – James Crash Jan 3 '20 at 8:43
• Why not just add a NIZK to prove equivalence of ciphertexts? For any perfectly complete encryption scheme that should be sufficient. – Maeher Jan 3 '20 at 11:05
• @fgrieu: using AES-GCM doesn't "almost work", because it is practical to generate a ciphertext that will decrypt successfully to two different plaintexts using two different keys. – poncho Jan 3 '20 at 16:09
• @fgrieu: actually, you can do it by solving two linear equations in two variables... – poncho Jan 3 '20 at 16:49

As long as you are not wedded to RSA, here's a way that completely solves the problem (and scales to more than two targets).

The general idea is that we do EC-ElGamal in a pairing friendly curve (that is, an elliptic curve that has a computable function $$e(X, Y)$$ that satisfies the identity $$e(aG, bG) = e(G, G)^{ab}$$, for any integers $$a, b$$ (and $$G$$ is the generator point), and for which $$e(G, G) \ne 1$$. The power on the right is typically a multiplicative group of a finite field (which would depend on the curve you're using), that's not important at this point.

In any case, Bob and Oliver would select private keys $$b$$ and $$c$$ (I'll use c rather than o for Oliver, because o is too easily confused with 0), and their public keys are $$B = bG$$ and $$C = cG$$.

The encrypt, Alice takes the message $$m$$, and maps it in a way that is both invertable and nondeterministic to a point $$M$$ (it has to be nondeterministic, otherwise a third party with a guess of $$m$$ can verify his guess using the $$e$$ function). Then, she selects a random value $$r$$, and generates the two ciphertexts:

$$rG, rB + M$$

$$rG, rC + M$$

(note: each ciphertext can use the same $$rG$$ value, or use different ones; both varieties work).

Bob and Oliver first check whether all the points in the ciphertexts are actually points in the curve (I'm not sure what can go wrong if they're not, but it's an easy check to do).

Then, Bob can decrypt his received ciphertext $$X, Y$$ by computing $$M = Y - bX$$ and then mapping $$M$$ back to the original $$m$$.

Bob can then verify that Oliver got the same message by reconstructing $$rC$$ (using the value $$M$$ he got during decryption), and then verifying that $$e( G, rC ) = e( rG, C )$$ (where $$rG$$ is the value from Oliver's ciphertext); if they received the same message, then both values are $$e( G, G )^{rc}$$

• How would it look like for 3 targets? – mentallurg Jan 3 '20 at 17:04
• @mentallurg: if you have 3 (or 100) targets, then each target would verify 2 (or 99) pairs of pairing operations (with each of the other target's ciphertext and public key) – poncho Jan 3 '20 at 17:54
• I presume you can combine this with authenticated symmetric encryption with a single symmetric key specific to the message that then gets converted to (or derived from a random) $M$? – Maarten Bodewes Jan 3 '20 at 21:18
• How about performance and resources needed? The OP doesn't say how many targets can there be. For 2 targets it's OK. But for a big number of targets this can be a problem. To verify all other messages every target has to obtain messages sent to every other target. For $N$ targets there will be $N^2$ messages obtained / delivered. If the message is a document of 100MB and there are let say 10 000 targets (like subscribers to some info channel), there will be traffic of $10 000^2 * 100MB = 10 000 000 000MB = 10 000 000GB = 10 000TB$. – mentallurg Jan 3 '20 at 21:22
• @Maarten-reinstateMonica: yes, I believe you can. In fact, it would become a bit cleaner; instead of having a nondeterministic invertible mapping m -> M (doable but nonstandard), Alice would just pick a random point M, and then use Hash(M) as the symmetric encryption key... – poncho Jan 3 '20 at 21:23

It depends on the what are you protecting from. If the scenario is that each party does not trust to other one, then there is no solution.

Alice can be in agreement with Bob against Oliver.

Scenario 1: Alice can send message X1 to Oliver and message X2 to Bob, and the message X2 means "pretend you received message X1". If Oliver wants to verify what Bob received (e.g. via hash or similar signature algorithm), Bob will just generate everything needed for X1.

Scenario 2: Alice can generate a random password, encrypt the message with a symmetric algorithm and send it to both Bob and Oliver, or just make this encrypted message publicly available, so that each party sees there is only one message. She sends this password to Bob and Oliver separately encrypting it with their RAS public keys. But again there is no guarantee for Oliver that Alice has not sent some other messages to Bob.

• Problems often have no solutions until Poncho provides one none-the-less, although not for RSA :) – Maarten Bodewes Jan 3 '20 at 21:16
• @Maarten-reinstateMonica: It looks like that :) I thought about homomorphic properties of Paillier, but didn't find any good solution. Where as Poncho found good approach. – mentallurg Jan 3 '20 at 21:30