0
$\begingroup$

As far as I know, RSA is not used for encrypting large files. Instead some symmetric key algorithm like AES or DES is being used for encryption with a random key and that random key is then encrypted with a public key. So, all operations in cloud will be performed on data that is encrypted using the symmetric key algorithms.

Then why would someone want RSA to be fully homomorphic? Are there any specific application for that? in cloud computing?

$\endgroup$
  • $\begingroup$ I fail to see what the common use of RSA for encryption has to do with the application of RSA for homomorphic encryption. $\endgroup$ – Maarten Bodewes Mar 26 '17 at 10:14
5
$\begingroup$

The question's observation is perfectly right: RSA as practiced uses padding or/and is used to encipher a symmetric key, which makes it not homomorphic at all.

Further, textbook RSA (without padding) is homomorphic, but is deterministic (the same plaintext always produces the same cypertext). This is most often a devastating weakness, because it lets anyone (with the public key) test an hypothesis on the plaintext.

For this reason, use of RSA as an homomorphic asymmetric encryption algorithm is questionable, and accordingly is now almost entirely absent in cryptographic publications with a peer-review system that I trust.

Update: A related question asks if it is possible to devise safe RSA padding while preserving homomorphy; I tentatively answered in the affirmative, but that does not seem practical at all.

I do not know any way to make RSA fully homomorphic, in the usual sense that it allows both addition and multiplication of plaintext from ciphertext.


The Pailler cryptosystem is a randomized asymmetric encryption algorithm (safe from plaintext guessing); is homomorphic (for addition of plaintext, rather than multiplication for RSA); is based on the same mathematical problem as RSA; and is not much more difficult to grasp. It might be a proper substitute for RSA when a homomorphic asymmetric encryption algorithm is thought. Also, there seems to be more applications of additive homomorphic encryption than of the multiplicative breed.

Among applications of the Pailler cryptosystem (and homomorphic encryption in general) are some electronic voting protocols (an interesting theoretical subject; still, count me among the strong opponents of their actual use for political elections).

$\endgroup$
  • $\begingroup$ I'm just curious; why are you specifically a strong opponent of evoting? I can think of a couple potential reasons (can they be practically secure, would they be sufficiently transparent to the 99% of the electoric who doesn't know crypto), I'm just wondering what your specific reasons are... $\endgroup$ – poncho Mar 26 '17 at 15:38
  • 2
    $\begingroup$ @poncho: Democratic elections aspire to resolve leadership selection without civil war; it is critical that voters trust the result; that 99% of them do not understand how the system works is thus a serious issue. Another is that traditional voting systems are highly resistant to centralized fraud (observers stand fair odds to detect fraud at the polling station level; printing local results in newspapers insures integrity upwards); while electronic voting systems tend to be vulnerable to gross fraud by a handful of insiders; the issue is not the crypto, but its concrete implementation. $\endgroup$ – fgrieu Mar 26 '17 at 20:30
1
$\begingroup$

So it works in the following way:
Public key algorithms are expensive compared to shared key algorithms. So we will not encrypt large files using public key algorithms hence secret key algorithms are used. But secret key algorithms needs a shared key(known as session key) which is known only to the 2 users. In real life they need to meet each other to agree upon a shared key which is practically not possible so they use public key algorithms to generate secret key(session key) which later used to encrypt the files. So the public key algorithms are to be secure to keep the session key secure and moreover they are also used in Digital Signatures.

As an example you can look in to Diffie Hellman key exchange protocol which is a public key algorithm used to derive a shared secret key.

Note: Session key varies from session to session and is valid only in that particular session, but the Longterm key doesn't change from session to session.

$\endgroup$
  • $\begingroup$ Thats nice explanation, thanks, but I am also interested in finding the applications of fully homomorphic RSA, because there are some recent research papers that claim to provide solutions to make RSA fully homomorophic. $\endgroup$ – Dinesh Raj Mar 26 '17 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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