Meet Frodo … And The Magic of the Post Quantum Ring
Meet Frodo … And The Magic of the Post Quantum Ring
Towards Post Quantum Public Key Encryption and Key Exchange
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 are:
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 negliable affect 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.
Coding
Now let’s code using the Cloudflare CIRCL library [here]:
This gives:
FrodoKEM-640-SHAKE
Alice pk (len=9616) = 34AC5BCBF3D001C209B20F7D95DBE74281B1CB8EA5979727FE1F0ADBEB7D78731CDEBB6866A1700FF246068D00DE9E205D1647E4C914A578E5FCC8A206E5E35CD9523A325F2AF613A6CA653F81835B57420ACB6DDF3D617F4AC0E59BEA8C03C6D426C8AD3C28ED049F5A6A18277AC5E191834498434A97BA765D2515AAE33F69
Alice sk (len=19888) = C84EBE8A5EE12DEEE3B652E392AAF3BB34AC5BCBF3D001C209B20F7D95DBE74281B1CB8EA5979727FE1F0ADBEB7D78731CDEBB6866A1700FF246068D00DE9E205D1647E4C914A578E5FCC8A206E5E35CD9523A325F2AF613A6CA653F81835B57420ACB6DDF3D617F4AC0E59BEA8C03C6D426C8AD3C28ED049F5A6A18277AC5E1
Bob seed = 82F37B5D410F48EDBE5B6D9DA9CB33E14D1A4C96357E38919A403B2576064C6C4576B20022924B8558E76415038EAF73
Bob creates ct (len=9720) = CCB5039E9738CFE8362651F72197F5FB3AC60088B05D9F2FE1C2DBAB12AA4F086E628EFD5020E5EDA64907F8C546EC2E1DAB87A0735597ECA34704A4EC46A828AF883A9DBCE54B8C13394A889C7EF546C02F8BD418231D2992BC4B3F5CE5810568DA5CEE84AE21C583078D69141C00CA74139740BCC2601139B7512A99D90937
Bob's ss (len=16) = 4BED89134F187E171CDC1F2ADC531087
Alice's ss (len=16) = 4BED89134F187E171CDC1F2ADC531087
For FrodoKEM-640-SHAKE, we can see that the size of Alice’s public key is 9,616 bytes long, and her private key is 19,888 bytes long. The ciphertext passed is 9,270 bytes long. You can test this here. In this case the shared secret is 729780FC51657E21357F03A338116569.
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 generaito 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.
Code
The full code is here:
https://asecuritysite.com/circl/go_frodo
If you want to learn the basics of Learning With Errors (LWE), try here: