3
$\begingroup$

I am a long time scroller, first time poster in the crypto stack. I've recently been finding myself leaving the realm of mainstream/standard crypto (imo that consists of symmetric/asymmetric encryption, some ciphers and one way hash functions ect). I am currently faced with a problem regarding using the RSA algorithm through multiparty computation. I am using RSA to conduct multiplicative homomorphic encryption using multiple keys. I am able to provably generate the encryption keys along with the final cipher text after multiplying all the values together. However I am not able to generate the correct decryption keys.

Process for encryption using RSA MPC

\begin{align} C_1 &= a^{e_1} \pmod n \\ C_2 &= a^{e_2} \pmod n \\ C_{final}&= C_1 \cdot C_2 = a^{e} \pmod n,\ \text{where} \ e=e_1 + e_2 \end{align}

The issue is that this only I can only really do this with a single encryption key (so if you consider $e_1=e_2$), whereas I would like to use multiple encryption keys ($e = e_1 + e_2$ or something equivalent), encrypt a value do some operation on that encrypted value then be able to decrypt it and receive some meaningful output.

Can someone help me with the problem of where to find details on using multiple encryption keys in RSA and working with the encrypted values directly ?

Research I based my working from: https://www.researchgate.net/publication/335743662_Enhanced_Homomorphic_Encryption_technique_using_RSA_ALGORITHM_with_multiple_keys

Improve this question
$\endgroup$
3
  • $\begingroup$ yeaaah that was stupid on my part... for sure !!! Thanks I'll fix that $\endgroup$
    – Dimitree
    Commented Jun 26, 2020 at 22:37
  • $\begingroup$ The thing is I can't just add e together right because its probably not going to be prime in that case... whereas multiplication would retain that structure $\endgroup$
    – Dimitree
    Commented Jun 26, 2020 at 22:40
  • $\begingroup$ You might want to have a look at the Paillier cryptosystem. It is based on integer factorization like RSA, uses reminiscent math, incorporates randomization of plaintext to make it CPA-secure, and allows addition of plaintexts (small enough, or modular addition) directly on ciphertext. $\endgroup$
    – fgrieu ♦
    Commented Jun 29, 2020 at 2:40

2 Answers 2

Reset to default
1
$\begingroup$

Besides the answer Dimitree gave to himself, I' like to add something even if I am not sure whether I understand the original problem he wanted to solve.

You used the same message a and encrypted it with different values for e, but used the same modulus N. And you added the different exponents e.

As far as I know, the homomorphic multiplicative feature of RSA is defined in a way, that the same e and N are used, and you either want to get a multiple of m by just manipulating c or you want to multiply two c values.

Simple encryption and decryption of numbers in RSA is straightforward: To encrypt a number m, one computes c = m^e mod N. To decrypt a ciphertext c, one only needs to compute m' = c^d mod N = m^(e*d) mod N = m.

To see that RSA is partially homomorphic, consider two numbers m1 and m2 and their respective ciphertexts c1 and c2. To compute the product m1 * m2 homomorphically, one computes the product of the ciphertexts, c1 * c2. This then decrypts to m1 * m2: (c1 * c2)^d mod N = (c1^d) * (c2^d) mod N = (m1^(e * d)) * (m2^(e * d)) mod N = m1 * m2.

The RSA scheme is only partially homomorphic because one is only able to perform multiplications.

In a similar way you may build an attack modifying c to c' such that the receiver gets m' = k*m.

However, I might not have understand the problem and you are talking of another kind of multiparty communication. If so could you explain the scenario a bit more detailled.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice answer, In fact the multiplicative homomorphic property can be used in blinding of signatures. Note that RSA is normally used with padding (as opposed to so called textbook RSA), to obtain other security advantages and prevent leakage of information, thus even this property can be tricky to make use of. $\endgroup$
    – kodlu
    Commented Jun 29, 2020 at 0:07
0
$\begingroup$

Note that in RSA, someone knowing the "decryption key" for any "encryption key" for a given modulus N can compute the "decryption key" for any "encryption key" for the same modulus. In other words, be careful when having $e₁$ and $e₂$ using the same modulus, if someone knows $d₁$ such as $1 = e₁ \times d₁ (\bmod \phi(N))$, he can learn some "$d_i$" for any other "$e_i$", including $e₂$. You may want to define how shares of the key are build to avoid raising flags in your readers mind.

There is usually some setup in a multi-party computation scheme, with well defined actors such as a trusted dealer, honest but curious participants, and a defined goal such as "I want n different people to execute a protocol to compute something with the private key without anyone learning about the private key". You may want to define the setup and context to better highlight the goals of the cryptosystem, for example this answer.

Note that the paper you linked is also kind of smelly, but I'll say that Elgamal is often preferred when you need homomorphism, because for example RSA is not semantically secure against some attacks when no padding (such as OAEP) is used.

I'm no insider to these topics, but you may want to read "Efficient Cryptographic Protocol Design Based on Distributed El Gamal Encryption" on doing MPC around Elgamal and "Twenty Years of Attacks on the RSA Cryptosystem" on why paddings are a thing in RSA.

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.