Frodo And The Magic Of The Post Quantum Ring
Frodo And The Magic Of The Post Quantum Ring
I know Frodo didn’t make it to NIST standardization for PQC KEM (Key Encapsulation Method), but it is still a valid method, so let’s investigate it. With this, we will see that Frodo 19888 produces 128-bit security, Frodo 31296 produces 192-bit security, and Frodo 43088 produces 256-bit security.
Introduction
Well, who knows when quantum computers will be built at scale, but one thing that is for sure, is that they will break the fundamental core of security on the Internet. With this, our existing public key encryption, digital signature and key exchange methods will be a severe risk. And so we must find alternatives, and one of these is FrodoKEM — and which is a NIST final round contender for key exchange (replacing ECDH) and public key encryption (replacing ECC and RSA). I like the Frodo method, as it’s a pure learning with errors method.
It is based on the learning with errors problem and has a number of levels: FrodoKEM-640 (Level 1, equivalent in security to AES-128), FrodoKEM-976 (Level 3, equivalent in security to AES-192), and FrodoKEM-1344 (Level 5, equivalent in security to AES-256). There are two main variants of these for FrodoKEM-X-AES and FrodoKEM-X-SHAKE. The -AES version has hardware acceleration for AES and can run faster on processors that support hardware acceleration for AES, while the -SHAKE version is faster on systems that do not support this.
With Frodo, the steps to generate a key, encrypt a message, and decrypt.
Key pair generation
To generate a key pair we create a public key of A,B, and then a private key of s, and where:
In this case, e is an error matrix, and A and B are randomly generated matrices.
Encryption
If Alice wants to send to Bob, she uses his public key, and generates two secret vectors (s_1, e_1) and (e_2)). She then computes:
Then she adds the message m to the most significant bit of v_1. The values of b_1 and v_1 are then sent back to Bob. This works as:
gives:
and where e_2 has a negligible effect on the message. The proof is:
Decryption
Bob computes the message from:
This is the basics of FrodoPKE (Public Key Encryption).
Key Encapsulation Mechanism (KEM)
With KEM, Bob and Alice need to generate a shared secret, and which they are likely to use to create a secure tunnel between them. Bob initially creates a key pair (pk,sk), and then generates a hash of the public key:
and where H() is the hashing method. Bob then selects a random value (s), and thus has a public key of pk and the private key sk_1 of (sk, s, pk, pkh). He then selects a random value (u), and hashes it with the public key (pkh) to give:
Next we encrypt as before to get the ciphertext (ct)
and then hash to get ss (secret share):
Bob sends the ciphertext (ct) and the shared secret (ss) to Alice. She has (sk, s, pk, pkh) and will receive (ct, ss). She can then discover the shared secret with:
Then:
Next Alice discovers the shared secret with:
This recovers the shared secret, and Bob and Alice have the same value.
Key sizes against other methods
The results for the fastest key gen (for cycles) is given below. Generally, the lattice-based methods do well (such as Kyber, Saber and NTRU), but McEliece, SIKE and SIDH do not do well in this test. We can see that FrodoKEM-640-KEM is around 100 times slower for key generation than Kyber512:
In terms of key sizes we get:
We can see that FrodoKEM has a much larger key size for the public and private key, and for the ciphertext than SIDH.
For our existing ECC methods, the key sizes are:
Type Public key size (B) Secret key size (B) Ciphertext size (B)
------------------------------------------------------------------------
P256_HKDF_SHA256 65 32 65
P384_HKDF_SHA384 97 48 97
P521_HKDF_SHA512 133 66 133
X25519_HKDF_SHA256 32 32 32
X448_HKDF_SHA512 56 56 56In this case, we see a 32-byte secret (private) key size for P256, and 64 bytes for the public key (as it has an x- and y-co-ordinate value) and then another byte added to identify the type of point. This gives a 65 byte public key. For X22519, we only require a single co-ordinate value, and thus only need 32 bytes for the public key (and which is the same size as the secret key). The following defines the key sizes for Kyber, SABER, NTRU and McEliece:
Type Public key size (B) Secret key size (B) Ciphertext size (B)
------------------------------------------------------------------------
Kyber512 800 1,632 768
Kyber738 1,184 2,400 1,088
Kyber1024 1,568 3,168 1,568
LightSABER 672 1,568 736
SABER 992 2,304 1,088
FireSABER 1,312 3,040 1,472
McEliece348864 261,120 6,452 128
McEliece460896 524,160 13,568 188
McEliece6688128 1,044,992 13,892 240
McEliece6960119 1,047,319 13,948 226
McEliece8192128 1,357,824 14,120 240
NTRUhps2048509 699 935 699
NTRUhps2048677 930 1,234 930
NTRUhps4096821 1,230 1,590 1,230
SIKEp434 330 44 346
SIKEp503 378 56 402
SIKEp751 564 80 596
Frodokem19888 9,616 19,888 9,720
Frodokem31296 15,632 31,296 15,744
Frodokem43088 21,520 43,088 21,632Note: LightSABER has a security level of AES-128, SABER maps to AES-192, and FireSABER to AES-256. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256. NTRUhps2048509 has a security level of AES-128, NTRUhps2048677 maps to AES-192, and NTRUhps4096821 to AES-256.
In terms of performance on an ARM Cortex-M4 (32-bit RISC processor), the following is the number of cycles taken for various operations for key generation, key encapsulation and key decapsulation:
scheme (implementation) level key generation encapsulation decapsulation
----------------------------------------------------------------------------
frodokem640aes (m4) 1 48,348,105 47,130 922 46,594,383
kyber512 (m4) 1 463,343 566,744 525,141
kyber768 (m4) 3 763,979 923,856 862,176
lightsaber (m4f) 1 361,687 513,581 498,590
saber (m4f) 3 654,407 862,856 835,122
ntruhps2048509 (m4f) 1 79,658,656 564,411 537,473
ntruhps2048677 (m4f) 3 143,734,184 821,524 815,516
sikep434 (m4) 1 48,264,129 78,911,465 84,276,911
sikep610 (m4) 3 119,480,622 219,632,058 221,029,700
mceliece348864f 1 1,430,811,294 582,199 2,706,681
mceliece348864 1 2,146,932,033 582,199 2,706,681Coding
Next some code [here]:
namespace Frodo
{
using Org.BouncyCastle.Pqc.Crypto.Frodo;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var method="frodokem19888r3";
if (args.Length >0) method=args[0];
var random = new SecureRandom();
var keyGenParameters = new FrodoKeyGenerationParameters (random, FrodoParameters.frodokem19888r3);
if (method=="frodokem19888r3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem19888r3);
else if (method=="frodokem31296r3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem31296r3);
else if (method=="frodokem43088r3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem43088r3);
else if (method=="frodokem19888shaker3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem19888shaker3);
else if (method=="frodokem31296shaker3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem31296shaker3);
else if (method=="frodokem43088shaker3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem43088shaker3);
var FrodoKeyPairGenerator = new FrodoKeyPairGenerator();
FrodoKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = FrodoKeyPairGenerator.GenerateKeyPair();
var aPublic = (FrodoPublicKeyParameters)aKeyPair.Public;
var aPrivate = (FrodoPrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobFrodoKemGenerator = new FrodoKEMGenerator(random);
var encapsulatedSecret = bobFrodoKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceFrodoKemExtractor = new FrodoKEMExtractor(aPrivate);
var aliceSecret = aliceFrodoKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Frodo Engine:\t\t\t{0}",keyGenParameters.Parameters.Name);
Console.WriteLine("Frodo Key Size:\t\t\t{0}",keyGenParameters.Parameters.DefaultKeySize);
Console.WriteLine("Frodo N:\t\t\t{0}",keyGenParameters.Parameters.N);
Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length);
Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length);
Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length);
Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]);
Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]);
Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]);
Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret));
Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret));
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}Frodo 19888 produces a 128-bit key size [here]:
Frodo Engine: frodokem19888
Frodo Key Size: 128
Frodo N: 640
Private key length: 19888 bytes
Public key length: 9616 bytes
Ciphertext length: 9720 bytes
Alice private (first 50 bytes): 60E94F807790F80CC887AAD61DEC343CAAF5A20D3A76A4B348B7C73EB815DD9DFC84DED0961681EDA8B134056AE03D22CEB7
Alice public (first 50 bytes): AAF5A20D3A76A4B348B7C73EB815DD9DFC84DED0961681EDA8B134056AE03D22CEB7AAC9DF2EC4C45220F1D11FAF6B7DE887
Cipher (first 50 bytes): 9F9CB943AFBC9CE6CB94C5CC9037C1274366604E853291F821660513BB913C54FE336680E965859B2A47E40786ECD16CC649
Bob secret: AD2CBB2E9755D3E7EB3DF780EF86DA9F
Alice secret: AD2CBB2E9755D3E7EB3DF780EF86DA9Fand for Frodo 31296, we have a 192-bit key size [here]:
Frodo Engine: frodokem31296
Frodo Key Size: 192
Frodo N: 976
Private key length: 31296 bytes
Public key length: 15632 bytes
Ciphertext length: 15744 bytes
Alice private (first 50 bytes): CBAE417B2E3182770219415A474CFE1F68CE1F9168A3CC2716B4FB19C038F235145E3487F50B6AC199F6313A0F45887830E8
Alice public (first 50 bytes): 16B4FB19C038F235145E3487F50B6AC199F6313A0F45887830E87949D6D2EF19381201FAD76F20668D8EAED014076ACDAF0A
Cipher (first 50 bytes): 72C7942F0C78C3DC4BF12116DB8CACABC4D9D55C5AF2D4F16AD616ABFC5555BA9D8771C14C22F1051AC38E7384E09938220F
Bob secret: FECD0AB21291E4027DE53D5D37A64C3E2BA40A606B37FD8Band for Frodo 43088, we get a 256-bit key [here]:
Frodo Engine: frodokem43088
Frodo Key Size: 256
Frodo N: 1344
Private key length: 43088 bytes
Public key length: 21520 bytes
Ciphertext length: 21632 bytes
Alice private (first 50 bytes): CEC1D8A812454DFABCD95DEA297F791AD542EF49E6552324F20A09D4F9D9E52278D4009BD9A2A5299D22C78BFB5B69015E97
Alice public (first 50 bytes): 78D4009BD9A2A5299D22C78BFB5B69015E9717124EF893467ADB0B17CA548C5AEC358786C22A0641D0B62F1D356FB58DBC75
Cipher (first 50 bytes): 71C933B3C066C4BA854D218E96C9EB78C7BE5606D1CED587EFF7E6E12C00FE2E8C189922CAAC66007D6EFAD94773E1512A15
Bob secret: 5056F91CB1FEFAFC56593E1C9F9FE9E5D549F1B34CD56743543847E9C18EAF6A
Alice secret: 5056F91CB1FEFAFC56593E1C9F9FE9E5D549F1B34CD56743543847E9C18EAF6AConclusions
Frodo made it to the final of the NIST PQC competition, but Kyber won. But just because a method wins in the NIST competition, doesn’t mean it will not be developed. BLAKE is a good example of this and now used in many applications as an alternative to SHA-2 (Keccak).