RSA is partially cryptographically homomorphic

Homomorphic cryptography [1], should it ever become available as a product, will have an intriguing property: computers will be able to operate on encrypted data without either having to- or being able to decrypt it. Competitive or regulatory pressure leads many organisations to distrust public (or private) clouds with their data and algorithms, so they operate instead their own data centres. Homomorphic cryptography would allow these organisations to securely use public clouds which would operate only on encrypted data, never revealing the unencrypted data to anyone else.

input data → encrypt → process encrypted data → decrypt → output data
The mathematical underpinning of homomorphic cryptography is diverse as not all cryptographic algorithms heave equally suitable homomorphic properties. Generally speaking, a cryptographic algorithm S is homomorphic under operation F if:
Y=F(X) → S(Y)=F(S(X))
In order for a “homomorphic computer” to work, the employed cryptographic system would have to be homomorphic under all Turing computable functions [2] – up to my knowledge, there is currently none. The popular RSA [3] algorithm, for example, is homomorphic under multiplication (but not, e.g. addition):
A*B = C → RSA(A)*RSA(B) = RSA(A*B)
… as a simple programme [4] demonstrates convincingly.
At least for RSA there are two catches:
1) The product of encrypted numbers can not exceed RSA’s m otherwise the computed results are just plainly wrong [5]
2) Continued operation on encrypted data introduces “noise”, making it necessary to periodically decrypt and re-encrypt the data if, e.g., working with floating point arithmetic.

Resources

[1] Homomorphic encryption, Wikipedia
[2] Computable function, Wikipedia
[3] RSA cryptosystem, Wikipedia
[4] RSA homomorphic property demonstration
[5] Example of diverging computation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s