Quantum Proof Encryption

by Alan Earl Swahn

The promise of quantum computing coupled with particular algorithms - Shor's, Grover's - is the latest motivation to upend the secure data ecosystem.

Higher key sizes will be mandatory for encryption algorithms to be salvaged and new algorithms introduced to replace long standing encryption algorithms no longer in favor.  Just read the laborious NIST¹ publications for the gory details.  And the cost to implement is huge, to use a Trumpism, considering all the data at rest that needs to be re-encrypted, protocols to be updated, and hardware to be redesigned just to be warm and safe in our new security blanket.

But it's necessary; just ask any cyber security pundit or even ChatGPT.

Of course, these security oracles are all trained from the same corpus and therefore concur on the course of action to secure data at risk.  And it will be necessary again, not just because of advances in computing power, but coupled with new attack vectors and better supporting algorithms like search and prime factorization.  But this insanity loop can be broken with a new fundamental idea on how to encrypt data.

Popular encryption algorithms that maintain our secure data ecosystem have these traits:

• Each algorithm is compliant to a known standard, e.g. FIPS 140-2,² or ISO/IEC 19790:2012.³
• Each algorithm uses one cipher to encrypt data.¹⁰

• Algorithms are key-based.
• Key size determines the data encryption security level,⁶ measured in bits.
• The equivalent⁴ symmetric data encryption security level achieved must be at least 112-bits now and 128-bits after 2030.
• Symmetric encrypted data length is the same as the input data length plus any padding.
• Maximum asymmetric encrypted data length depends on padding and key size employed.
• Encryption performance is fast.
• Authentication is supported.

But there's the rub.

If a cipher itself is cracked, all is lost.  Effective key sizes dwindle in the face of new attacks and are cut in half⁵ with the advent of non-universal quantum computing (purpose built).

As per Table 1 below, the AES algorithm with a 256-bit key is safe.  The RSA algorithm with a 16,384-bit key is safe, but isn't practical as the public/private key pair takes too long to generate.

Table 1

The new idea must not only have these traits, but exceed the security level by 2x to be quantum safe after 2030 and by a much larger factor to be safe for all time - quantum proof encryption.

O.K., the bar is high, but the idea is simple.  Data is organized in bytes, where a byte is eight bits.  Encryption parameters can include a key, nonce, padding, mode, and associated data.  They are provided to the encryption algorithm and data is fed to it in an orderly serial fashion.  The encrypted data and sometimes decryption parameters like an authentication tag are output as in Figure 1:

Figure 1

Asymmetric algorithms, such as RSA, limit the maximum message size ("M") depending on key size and padding employed.

As you can see in Table 2, RSA is limited to only encrypting very small amounts of data:

Table 2 - Maximum RSA Message Size (bytes)

To visualize the new idea, called General Encryption Enhancement (GEE), let's look at the data bytes vertically.  There is a point to this:

Figure 2

Let's collect like bits positions and create a new set of eight bytes:

Figure 3

Now independently encrypt all the bytes for each bit position, where each encryption has its own unique key.  The encryptions are performed in parallel:

Figure 4

Of course, the encrypted new bytes are then written/streamed out in order:

Figure 5

Since each encryption operates on 1/8 data length in parallel, the measured GEE performance is fast.  For GEE with AES-256, the median performance increase over OpenSSL AES-256⁷ for 14 files ranging from 182 kB to 16,384 MB was a little over 3x for both encryption and decryption.

Asymmetric encryption as noted in Table 2 is severely limited in message/data size.  Each encryption has this limitation, but by using GEE with RSA there are now eight encryptions that result in maximum message size that is 8M-1 times larger (-1 is a GEE implementation detail).

Each encryption cipher, its padding⁸ if any, and its mode of operation⁹ if any, can be different, provided all the ciphers in a GEE set of eight are asymmetric or symmetric.  Using todays' 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.

But these are nice side effects of GEE.  The big deal is that each encryption has its own key, therefore GEE employs a SuperKey that is the aggregation of eight different standard keys.  To decrypt encrypted data takes a SuperKey.  Each byte of input data (cleartext) has eight standard keys associated with it, one for each bit position in the byte.  The SuperKey effective key length is 8x the standard key length.  The associated security of the encrypted data is beyond astronomical (only 10²² to 10²⁴ stars in the universe according to NASA).

Let's revisit Table 1, but add in the effect of using GEE:

Table 3

Remember, quantum computing reduces the number of security level bits in half⁵ and, to be quantum safe, the security level must be at least 128-bits using today's classical computing.

Putting these together means that the security level must be at least 256 under quantum computing.  Per Table 3, GEE raises the security level to make small key sizes safe to use.

As an example, take AES-192.  Today's 192-bit key is 192 / 2 = 96 bits under quantum computing.  96 is less than the required 128-bits and therefore using AES with a 192-bit key isn't safe.

GEE raises the effective key length to 8 * 192 = 1536 bits.  Today's GEE SuperKey of 1536-bits is 1536 / 2 = 768 bits under quantum computing and much greater than the required 128-bits; it is quantum safe.

We use security level bits for comparison because it's easy.  But we are really talking about the number of symmetric key permutations.  So today's AES-128 bit key has 2128 permutations and, under quantum computing, has 264 = 1.84 * 10¹⁹ permutations, which is much less than the quantum safe requirement of 2128 = 3.40 * 10³⁸ permutations.

Compare that to a GEE SuperKey that has 21024 = 1.79 * 10³⁰⁸ permutations and under quantum computing has 2512 = 1.34 * 10¹⁵⁴ permutations.

For this case, GEE is 2384 = 3.94 * 10¹¹⁵ times more secure than the quantum safe requirement - a.k.a., quantum proof encryption!

Sources/Definitions

1. National Institute of Standards and Technology
2. Federal Information Processing Standard
3. ISO/IEC: International Organization for Standardization and the International Electrotechnical Commission; ISO/IEC 19790:2012 publication: Security requirements for cryptographic modules
4. NIST - Implementation Guidance for FIPS 140-2 and the Cryptographic Module Validation Program, Table 2, page 124
5. The Impact of Quantum Computing on Present Cryptography, March 31, 2018, Department of Informatics, University of Oslo, Norway
6. Equivalent symmetric key strength: (note: fractional bits truncated) - Implementation Guidance for FIPS 140-2 and the Cryptographic Module Validation Program, page 122
7. OpenSSL: www.openssl.org
8. Symmetric padding examples: ISO10126, ANSIX923, Zeros; Asymmetric padding examples: PKCS1, OAEP-SHA-1, OAEP-SHA-256, OAEP-SHA-384, OAEP-SHA-512
9. Symmetric mode examples: CCM: Counter with CBC-MAC, GCM: Galois/counter mode, CBC: Cipher Block Chaining, CFB: Cipher Feedback
10. The Triple DES algorithm uses the DES cipher three times