Fast, Quantum Safe Additively Homomorphic Encryption
Introduction
This article presents a means for executing private computation of addition operations on an untrusted server whilst protecting from a harvest-then-decrypt post-quantum attack.
It builds on the security of the ElGamal cryptosystem which lacks quantum safety, however an approach for achieving quantum security by converting it to a symmetric encryption scheme is discussed.
No new cryptographic techniques are presented in this article. It simply fine-tunes parameter selection for ElGamal to enable efficient additive homomorphic encryption.
This article assumes prior knowledge of discrete logarithm based public key cryptography, and some familiarity with ElGamal.
The ElGamal Encryption Scheme
ElGamal operates over a cyclic group G with order q and generator g.
All operations are implied modulo G unless otherwise indicated.
Key Generation
Secret key s= random number between { 1, …, q — 1 }
Public key p= g^s
Encryption
j = random number between { 1, …, q — 1 }
Ciphertext (x, y) = E(m) = (g^j, m * p^j)
Decryption
Plaintext m = D(x, y) = modInv(x^s, G) * y
Homomorphic Properties
The ElGamal encryption scheme is homomorphically multiplicative:
E(m) * E(n) = ((g^j) * (g^k), (m * p^j) * (n * p^k))
E(m) * E(n) = (g^(j + k), m * n * p^(j + k))
E(m) * E(n) = E(m * n)
For a more in-depth view into the mathematical basis for ElGamal, please consult the wikipedia article.
Naive Approach to Addition
The typical approach to enabling additively homomorphic encryption in ElGamal is to exploit the Product Exponent Rule.
Encoding
e = g^m
Encryption
(x, y) = E(e) = (g^j, e * p^j)
Decryption
e = D(x, y) = modInv(x^s, G) * y
Decoding
e = g^m
Homomorphic Properties
E(m) * E(n) = ((g^j) * (g^k), (g^m * p^j) * (g^n * p^k))
E(m) * E(n) = (g^(j + k), g^(m + n) * p^(j + k))
E(m) * E(n) = E(m + n)
The decoding step requires solving the discrete logarithm problem by brute force, with operations in the order of O(m).
This works, and certainly achieves the desired quantum safety (see below), but it is infeasible for large values of m.
A Better Approach
This uses an identical encoding method, however more efficient decoding is realised by careful selection of the public group G such that:
G = qr + 1
where:
- r has many small prime factors (less than 20 bits), a subset of which possess a product that exceeds or approaches the largest value of m to be encrypted
- q is a very large prime, close to G in bit length
Condition 1 allows efficient solving of discrete logarithms for small exponents via Chinese Remaineder Theorem, but without reducing the practical security level for general members of the group G.
Condition 2 protects the scheme against a birthday (collision) attack by ensuring the order of the group is sufficiently large, and limits the effect Condition 1 has on large exponents.
An example group G is as follows:
G = 2^3094–135017 = q * r + 1
r = 2 * 7 * 23 * 191 * 359 * 7717 * 15791 * 4411409
In the above group, q is a 3021 bit prime.
Encoding
e = g^m
Encryption
(x, y) = E(e) = (g^j, e * p^j)
Decryption
e = D(x, y) = modInv(x^s, G) * y
Decoding
For each small factor f of r:
c[i] = e^(Φ(G) / f[i])
c[i] = (g^m)^(Φ(G) / f[i])
c[i] = (g^(Φ(G) / f[i]))^m’[i]
The next step is to solve for m’[i] via brute force, where m’[i] is a value between 0 and f[i] — 1.
Once the value of m’[i] has been found for each f[i], the value of m can be found by application of the Chinese Remainder Theorem:
m = m’[0] mod f[0] = m’[1] mod f[1] = … = m’[n — 1] mod f[n — 1]
Solving for all the above congruences will yield the original value of m.
The value of m can be tested for correctness by re-encoding it and ensuring it matches the value e.
This technique was inspired by a similar approach employed in the decryption algorithm of the Naccache-Stern cryptosystem.
How does this work?
The key is in this equation:
c = (g^(Φ(G) / f[i]))^m’[i]
The generator (g^(Φ(G) / f[i])) has an order (and therefore brute force search space) of f[i].
Providing that m is less than (or not much larger than) the product of the factors being used, this makes the number of operations in the order of O(F), where F is the sum of the factors being used.
The example group allows numbers up to 11,869,137,094,642,789,887,814 (the product of the factors) to be decoded with a maximum of 24,088 brute force attempts (the sum of the factors).
Performance can be further boosted by performing the decoding step in multiple phases with progressively larger factors — and only proceeding to the next phase if it fails to find the correct value of m.
Security Implications
This approach most certainly weakens the ElGamal cryptosystem: it allows easier calculation of the discrete logarithm for small exponents, however this effect diminishes linearly for exponents larger than the product of the factors of r.
If s is chosen to have a bit length close to q (and random selection all but guarantees this), brute-forcing s from p remains outside the realm of possibility.
Quantum Safety
A popular scheme for additive homomorphic encryption is the Paillier cryptosystem, however performing untrusted additions requires knowledge of the public key (the modulus pq^2), making it completely vulnerable to a harvest-then-decrypt quantum factorization attack.
In ElGamal, untrusted operations only require knowledge of the public group G. If this encryption scheme is effectively converted to a symmetric encryption scheme (where the public key is not disclosed, and therefore not public), perfect quantum security is achieved.
In order to decrypt the message, the quantum adversary must effectively solve for m where:
(x, y) = (g^j, e * p^j)
If p and j are unknown, this problem has q equally likely solutions (q being a 3021 bit number with our example group), providing information-theoretic security.
