logoalt Hacker News

Veservyesterday at 7:31 PM1 replyview on HN

You are objectively wrong. The math is straightforward to show that you can operate on a ciphertext securely in some cryptosystems.

Consider two integers M1 and M2.

Consider RSA with private key (E), public key (D), and public modulus (N).

Encrypt(M, E, N) = mod(pow(M, E), N).

Decrypt(C, D, N) = mod(pow(C, D), N).

mod(Encrypt(M1, E, N) * Encrypt(M2, E, N), N) = mod(Encrypt(M1 * M2, E, N), N).

So, for all RSA encryption, multiplying the ciphertexts results in a ciphertext that is the multiple of the plaintexts. However, unless you can break RSA, you can not determine what numbers you multiplied or what the final multiplied number is.

This is not a fully homomorphic system as it only allows multiplication, but it is a existence proof that you can do operations on ciphertext that apply to the plaintext without being able to recover the plaintext unless you can break the encryption directly.


Replies

mswphdtoday at 4:04 AM

conceptually your example is fine/good, but it's worth clarifying that the scheme you describe is insecure, as unpadded RSA fails to be IND-CPA secure. this is because Enc(m)Enc(m') = Enc(mm') is a predicate a passive observer can check, to gain information about Enc(m*m').

that being said, you can construct IND-CPA secure homomorphic encryption schemes from factoring-based assumptions iirc, so this isn't a fundamental obstacle.