| Abstract: |
Oblivious data processing rises in popularity, especially in the wake of public ledger technologies. Coincidentally, compute is becoming affordable enough to allow for practical use of homomorphic cryptosystems that allow to perform meaningful operations over encrypted data. An example of a homomorphic cryptosystem is unpadded RSA: assume two numbers m1 and m2 are encrypted with classic RSA (public key e, private key d, public parameter n): c1 = m1^e mod n, c2 = m2^e mod n. Now, without knowing the decryption key d, someone can produce c' = c1 * c2 mod n = m1^e * m_2^e mod n = (m1 * m2)^e mod n, which is a valid encryption of a product of m1 and m2.
Yet, the offering of practical homomorphic data processing is scarce. As part of a project aimed at developing a practical homomorphic data platform, we conducted an extensive performance study of the following five cryptosystems: fully homomorphic HElib (IBM) and SEAL (Microsoft), somewhat fully homomorphic PyAono, and partially homomorphic Paillier and ElGamal (the latter two were developed by us).
Results clearly suggest that partially homomorphic (PHE) cryptosystems are significantly faster at homomorphic operations and relatively on par in en-/decryption times with fully homomorphic (FHE) HElib and SEAL. Paillier and ElGamal are consistently about 20–30k times slower than plaintext. At the same time, HElib is 500k times slower for subtraction, 1.6M times slower for addition, and almost 19M times slower for multiplication. SEAL shows relatively acceptable performance on addition and subtraction: 60–100k times slower than plaintext; but 15M times slower for multiplication (not to forget that it doesn't support division). PyAono takes the middle ground performing around 235k times slower than plaintext addition/subtraction; however, it absolutely breaks records in all other measurements: 2.2B (sic!) times slower in multiplication, 4.5 seconds for en-/decryption and over 700 seconds (sic!) for key generation.
It is important to notice that in more complex computations these numbers will be significantly corrected in favor of PHE due to bootstrapping in FHE, which is a very expensive operation (~600 ms bootstrapping a single ciphertext in HElib as compared to 1–20 ms for a homomorphic operation).
We suggest that partially homomorphic cryptosystems could be used today in certain practical applications, whereas time has not yet come for the fully homomorphic ones. |