SABER is a finalist for Public-Key Encryption/KEMs for Post Quantum Cryptography (PQC). It uses Learning with Rounding (LWR), and which is based on learning with errors (LWE) where random errors are replaced with deterministic rounding. It was created by Banerjee, Peikert and Rosen [1] at EUROCRYPT 2012 and is seen to be Indistinguishability under chosen-plaintext attack (IND-CPA). In this case the public key size is 672 bytes and the private key size is 1,568 bytes. Overall a KEM allows a symmetric key to be passed using public key methods [2]. In this case, Alice will generate her key pair of a public key (\(pk\)) and a private key (\(sk\)). She then passes her public key to Bob, and then Bob creates a cipher text (ct) with Alice's public key. He passes the ciphertext to Alice, and who decrypts with her private key. This will reveal the key that Bob wants Alice to use. LightSABER has a security level of AES-128, SABER maps to AES-192, and FireSABER to AES-256.
Saber PQC KEM using Bouncy Castle and C# |
Outline
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 Learning with errors (Lattice) Kyber738 1,184 2,400 1,088 Learning with errors (Lattice) Kyber1024 1,568 3,168 1,568 Learning with errors (Lattice) LightSABER 672 1,568 736 Learning with rounding (Lattice) SABER 992 2,304 1,088 Learning with rounding (Lattice) FireSABER 1,312 3,040 1,472 Learning with rounding (Lattice) McEliece348864 261,120 6,452 128 Code based McEliece460896 524,160 13,568 188 Code based McEliece6688128 1,044,992 13,892 240 Code based McEliece6960119 1,047,319 13,948 226 Code based McEliece8192128 1,357,824 14,120 240 Code based NTRUhps2048509 699 935 699 Lattice NTRUhps2048677 930 1,234 930 Lattice NTRUhps4096821 1,230 1,590 1,230 Lattice SIKEp434 330 44 346 Isogeny SIKEp503 378 56 402 Isogeny SIKEp751 564 80 596 Isogeny SIDH 564 48 596 Isogeny
Note: 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 encapulation and key decapsulation [3]:
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,681
Coding
Next some code:
namespace Saber { using Org.BouncyCastle.Pqc.Crypto.Saber; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var method="firesaberkem128r3"; if (args.Length >0) method=args[0]; var random = new SecureRandom(); var keyGenParameters = new SaberKeyGenerationParameters (random, SaberParameters.firesaberkem128r3); if (method=="firesaberkem192r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.firesaberkem192r3); else if (method=="firesaberkem256r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.firesaberkem256r3); else if (method=="firesaberkem90sr3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.firesaberkem90sr3); else if (method=="lightsaberkem128r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.lightsaberkem128r3); else if (method=="lightsaberkem192r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.lightsaberkem192r3); else if (method=="lightsaberkem256r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.lightsaberkem256r3); else if (method=="lightsaberkem256r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.lightsaberkem256r3); else if (method=="lightsaberkem90sr3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.lightsaberkem90sr3); else if (method=="saberkem128r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.saberkem128r3); else if (method=="saberkem192r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.saberkem192r3); else if (method=="saberkem256r3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.saberkem256r3); else if (method=="saberkem90sr3") keyGenParameters = new SaberKeyGenerationParameters(random, SaberParameters.saberkem90sr3); var SaberKeyPairGenerator = new SaberKeyPairGenerator(); SaberKeyPairGenerator.Init(keyGenParameters); var aKeyPair = SaberKeyPairGenerator.GenerateKeyPair(); var aPublic = (SaberPublicKeyParameters)aKeyPair.Public; var aPrivate = (SaberPrivateKeyParameters)aKeyPair.Private; var pubEncoded =aPublic.GetEncoded(); var privateEncoded = aPrivate.GetEncoded(); var bobSaberKemGenerator = new SaberKemGenerator(random); var encapsulatedSecret = bobSaberKemGenerator.GenerateEncapsulated(aPublic); var bobSecret = encapsulatedSecret.GetSecret(); var cipherText = encapsulatedSecret.GetEncapsulation(); var aliceSaberKemExtractor = new SaberKemExtractor(aPrivate); var aliceSecret = aliceSaberKemExtractor.ExtractSecret(cipherText); Console.WriteLine("Saber Engine:\t\t\t{0}",keyGenParameters.Parameters.Name); Console.WriteLine("Saber Key Size:\t\t\t{0}",keyGenParameters.Parameters.DefaultKeySize); Console.WriteLine("Saber L:\t\t\t{0}",keyGenParameters.Parameters.L); 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); } } } }
Firesaber 128r3 produces a 128-bit key size:
Saber Engine: firesaberkem128r3 Saber Key Size: 128 Saber L: 4 Private key length: 3040 bytes Public key length: 1312 bytes Ciphertext length: 1472 bytes Alice private (first 50 bytes): FE1F00F8FF0000000400000000FF1F000800FFFFFF01C0FF1700FF5F000000FF1F00044000F8FF000000048000D0FF03C0FF Alice public (first 50 bytes): C0BDA1A294BB3284CBA9545E4A15E7337F9A3BE757D412A029C33DE66AEC36F505C297C8207366ABECA2400B9ADAD13CA09D Cipher (first 50 bytes): 1C223102443451277C4B211846BBC2C23CEF5ECAE15608678741320F7E86724AAF8B341365D336A1ECDEBB9CB9B2703A442A Bob secret: 475CEC9D6E526C2ECCBA26619FE4B6C5 Alice secret: 475CEC9D6E526C2ECCBA26619FE4B6C5
and for Firesaber 192r3, we have a 192-bit key size:
Saber Engine: firesaberkem192r3 Saber Key Size: 192 Saber L: 4 Private key length: 3040 bytes Public key length: 1312 bytes Ciphertext length: 1472 bytes Alice private (first 50 bytes): 02E0FF038000F0FFFFFFFF1700FE1F00FC7F00000004C0FF0F00FE1F00040000000002C0FFFFFFFFDFFF070000100000C0FF Alice public (first 50 bytes): 05652506A50551E9D099F9F92BDD0649D06218267246DAD01EC4FE19BA1D34DC732AAF9967863103379EF3FBAD2CD0ACBAD4 Cipher (first 50 bytes): B1BD99B4A98758B5DD141EF48657B9C8AC2876654FEAB5EF49E195486A4FC9236A03552F84A8FDEA40E59E7B333D23F8FD45 Bob secret: 6A2E97A57407AFA383D4593B45CA1F61C43C2FD695C11617 Alice secret: 6A2E97A57407AFA383D4593B45CA1F61C43C2FD695C11617
and for Firesaber 256r3, we get a 256-bit key:
Saber Engine: firesaberkem256r3 Saber Key Size: 256 Saber L: 4 Private key length: 3040 bytes Public key length: 1312 bytes Ciphertext length: 1472 bytes Alice private (first 50 bytes): FEFFFF038000100000800000000020000C0001E0FFFF7F00000003C0FF0B00002000020000F8FF00C0FF0380000000FC3F00 Alice public (first 50 bytes): 2E39154793D4602D46701E3C4E7086C3FBE3D7BEBC52A5C42B159696B942281D4E3E8295DCEAD62F8E9E54A4407FB034A869 Cipher (first 50 bytes): 144D73C78C9EC466D3E806D4A8ECC9D3D0A2B96D7D76D1FC53673392CF66977ADDABFA94F7637E1B91D08928037A0610A176 Bob secret: C81553137C54B733E050DFEE8285D29C1991860BB4ABCD5FD32E71A564AB5E45 Alice secret: C81553137C54B733E050DFEE8285D29C1991860BB4ABCD5FD32E71A564AB5E45
For Saber 128:
Saber Engine: saberkem128r3 Saber Key Size: 128 Saber L: 3 Private key length: 2304 bytes Public key length: 992 bytes Ciphertext length: 1088 bytes Alice private (first 50 bytes): FFFFFF030000F0FF050000F8FFFE1F00000000F0FFFF7F00F8FF00E0FF0700001000FA3F000800FD3F000080FF0F0000C0FF Alice public (first 50 bytes): 1BC1DC2A2B9DB20F826C3FC29E7CC4BBEC276261582E12BDB5F1ABE7B2A34015C4E4F36A01B8F188AE27E1E89213FDE1D39A Cipher (first 50 bytes): 69CFD94E0F2C0BD3FB35701AD3CB61877469D3A7ADF318CDACA939E19E039B052ED56CE45D1CD1CC1E90C523BB1E6F3D82EB Bob secret: 7FC44D7E8078AADD9F0B98F17991C839 Alice secret: 7FC44D7E8078AADD9F0B98F17991C839
References
[1] Banerjee, A., Peikert, C., & Rosen, A. (2012, April). Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 719-737). Springer, Berlin, Heidelberg. [paper]
[2] D’Anvers, J. P., Karmakar, A., Roy, S. S., & Vercauteren, F. (2018, May). Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. In International Conference on Cryptology in Africa (pp. 282-305). Springer, Cham. [paper]
[3] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].