Rebuttal of "Quantum Proof Encryption"
by Vecna
This is a response to an article by Alan Earl Swahn titled "Quantum Proof Encryption," which appeared in the Autumn 2023 (40:3) issue of 2600. The article describes "GEE" (GEE), which is also described on the author's website1 and patented in the USA2. My response refutes some of the core claims made in Swahn's article.
Summary of Swahn's Article
Swahn's basic idea for GEE is that we should partition our plaintext data into eight parts, such that part one consists of the first bit from each plaintext byte, part two consists of the second bit, and so on.
Then, each partition should be encrypted independently with a different key (and possibly a different cipher), resulting in effectively eight ciphertexts encrypted under eight keys (which can be decrypted and recombined to produce the original plaintext). Swahn claims that because this process uses a "SuperKey" consisting of eight separate keys, the effective key length (for the purpose of evaluating security) is the combined length of the eight keys, making it safe to use shorter keys for the individual ciphers, even against quantum computers.
Correction 1: 16,384-bit RSA is not secure against quantum computers (and neither is 32,768-, 65,536-, or 131,072-bit RSA)
Swahn seems to misunderstand the impact of quantum computers on asymmetric cryptography.
Grover's algorithm3 could be used by a quantum computer to reduce the complexity of the search for an n-bit key from: O(2n) to O(sqrt(2n)) = O(2(n/2))
And (importantly) this is currently the best known quantum attack against otherwise secure symmetric encryption algorithms such as AES.
The implication of this is that in order for a symmetric encryption algorithm to remain secure against quantum computers, we must double the key length used.
If we want 128-bits of security, then we need (2128)2 = 2256 possible keys (i.e., 256-bit keys).
Swahn correctly identifies this complexity reduction for breaking symmetric encryption but incorrectly extends this logic to asymmetric encryption, calculating the complexity of factoring an RSA modulus according to a classical algorithm and then simply dividing the number of bits by two. Specifically, Swahn claims that 16,384-bit RSA provides 269-bits of security against classical computers and is therefore secure against quantum computers (as 269/2 exceeds the target of 128-bits of security).
However, this does not reflect the best known quantum algorithm for breaking RSA. RSA is vulnerable to Shor's factoring algorithm4, which can run on a quantum computer in polynomial time. With a large enough quantum computer running Shor's algorithm, n-bit RSA keys can be factored in: O(n3) time.5
For 16,384-bit RSA, this means the adversary only needs to perform O(242) operations. In other words, 16,384-bit RSA provides only 42-bit security against quantum computers, not 134-bit.
Quantum-resistant asymmetric crypto is essential. We already have AES-256 (so it's not necessary to construct this GEE for symmetric encryption), but we need some quantum-resistant way to negotiate the symmetric key based on asymmetric crypto. Swahn's GEE construction does not provide this. Even if GEE's SuperKeys did provide the 8x-level of security Swahn claims (they don't; see below), using RSA-16384 for all eight ciphers would only provide log(8 * 16384)3 = 51 bits of security.
Correction 2: GEE does not offer the claimed level of security (even if only symmetric ciphers are used)
Swahn makes two more claims I want to challenge about the security of GEE.
Claim 1: If eight different ciphers are used, than GEE remains (partially) secure even if some positive number t < 8 of the ciphers are broken. The exact way this is phrased is "Using today's single cipher encryption paradigm, a cipher being cracked is a catastrophe, as all data encrypted by the cipher is at risk of exposure. Compare that to GEE where data remains secure even if 1, 2... 7 ciphers are cracked."
Technically, this could be true as it is phrased (if you read "data remains secure" as "there exist some bits that are still secure" rather than "the plaintext remains overall secure"). A cracked cipher can expose some of the bits without exposing other bits encrypted with a different cipher (...assuming those bits can't be guessed from the leaked information). If the extent of the claim is exactly that and no more, then the rest of this part may be disregarded, and readers should jump down to Claim 2 (which is a bigger problem anyway).
However, I believe there is an implicit claim here that GEE is more secure than just using one cipher because in some cases, some bits may be exposed without other bits being exposed. That's not how we evaluate the security of encryption schemes.
A common security notion is ciphertext indistinguishability.6 The idea here is that for any two different messages of equal length m1 and m2, an adversary who knows a ciphertext is an encryption of one of the two messages (but not which) cannot determine which of the two messages was encrypted with much better probability than randomly guessing. (As a practical example of why this matters, this means, for instance, that an eavesdropper cannot learn whether a voter submitted "yea" or "nay," even given the knowledge that their vote was one of the two.)
Compromise of any component cipher could enable an adversary to distinguish between candidate plaintexts for the whole GEE ciphertext.
As a quick sketch, if an adversary can (with non-negligible advantage) distinguish between messages m1 and m2 (where m1 is not equal to m2) under the ith-cipher used in the GEE scheme, then the adversary can construct messages m'1 and m'2 to be encrypted by the GEE scheme, such that the ith-bit in byte j of m'1 is the jth-bit of m1, and the ith-bit in byte j of m'2 is the jth-bit of m2.
The ith-ciphertext will be an encryption of either m1 or m2, and with the same non-negligible advantage, the adversary can distinguish which it was, then conclude that the GEE scheme encrypted the corresponding m' message.
In other words, using multiple different ciphers independently in this way actually weakens security by introducing more potential vulnerabilities. A vulnerability in any of the eight ciphers impacts the security of the whole GEE construction. (I will note here that GEE very explicitly opts not to use multiple encryption7, which could actually provide defense in depth against cipher compromise if that was a concern.)
Claim 2: If we use eight different keys (for simplicity, let's assume in this case that we use the same cipher for each partition, so each key is n-bits long and offers the same number of bits of security), then the effective GEE SuperKey length is 8n-bits, and security scales accordingly.
For example, if AES-128 is used, then the SuperKey has 128 * 8 = 1024 bits and offers 1024-bit security (or 512-bit security against quantum computers).
The second claim seems to assume that an adversary either guesses the entire correct SuperKey or fails to learn any information at all. This is not a reasonable assumption. Instead, the adversary (who surely knows how the scheme works, per Kerckhoffs's Principle8) can treat the whole ciphertext as what it is: eight independent ciphertexts encrypted under eight separate keys.
They don't need to break an 8n-bit key; they need to break eight n-bit keys. If it takes O(2n) work to break one ciphertext, then it takes 8 * O(2n) work to break eight of them, not O(28n).
One might argue that this requires the adversary to know which key is correct once they have found it. In many cases, they will. (Partitioning the plaintext in the way described does not change this.)
For example, if the cipher is RSA, then the adversary's goal is to factor the modulus (and they will, of course, know when they have succeeded). If the encryption scheme is authenticated9, the adversary performs a verification step during attempted decryption. (Even if the scheme is not key-committing and decryption succeeds for multiple keys, the adversary can narrow down the set of possible keys to those for which decryption succeeds.)
Regardless of the encryption scheme, if the plaintext follows some predictable format (such as text), the result of successful decryption will often be identifiable. The claim that eight independent ciphertexts encrypted with eight different keys offer equivalent security to one ciphertext encrypted with a key eight times the length is not reasonable to assume in general.
Conclusion
GEE does not offer the security Swahn thinks it does, and in particular, it does not address the risk that quantum computers pose to the crypto commonly in use today. It is not "quantum proof encryption" as advertised.
Sources