Falcon was one of the finalists for the NIST standard for PQC (Post Quantum Cryptography), along with NTRU (Nth degree‐truncated polynomial ring units) and CRYSTALS-DILITHIUM, and is now approved by NIST as a standard for digital signatures (alongside Kyber and SPHINCS+). It is derived from NTRU and is a lattice-based methods for quantum robust digital signing. Falcon is based on the Gentry, Peikert and Vaikuntanathan method for generating lattice-based signature schemes, along with a trapdoor sampler - Fast Fourier sampling. We select three parameters: \(N\), \(p\) and \(q\). To generate the key pair, we select two polynomials: \(\textbf{f}\) and \(\textbf{g}\). From these we compute: \(F=\textbf{f}_q=\textbf{f}^{-1} \pmod q\) and where \(\textbf{f}\) and \(\textbf{f}_q\) are the private keys. The public key is \(\textbf{h} = p \cdot \textbf{f}_q . \textbf{f} \pmod q\). With Falcon-512 (which has an equivalent security to RSA-2048), we generate a public key of 897 bytes, a private key size of 1,281 bytes and a signature size of 690 bytes, while FALCON-1024 gives a public key of 1,793 bytes and a signature size of 1,280 bytes.
FALCON using Bouncy Castle and C# |
Outline
Falcon uses NTRU as a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. NTRU is the public key method which is not based on the factorization (RSA), discrete logs, or elliptic curve methods.
Bob and Alice agree to share \(N\) (and which limits largest polynomial power), \(p\) and \(q\), and then Bob generates two short polynomials (\(\textbf{f}\) and \(\textbf{g}\)), and generates his key pair from this. These polynomials have the co-efficients of -1, 0 and 1. For example, with \(N=11\), \(p=3\) and \(q=32\). If Bob picks values of:
\(\textbf{f}= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]\)
Then as a polynomial representation:
\(\textbf{f}=-1 + x + x^2 - x^4 + x^6 + x^9 - x^{10}\)
And then picks \(\textbf{g}\):
\(\textbf{g} = -1 + x^2 + x^3 + x^5 - x^8 - x^{10}\)
We then should be able to calculate the inverse of \(\textbf{f}\) for \(\pmod p\) and \( \pmod q\). Thus:
\(\textbf{f} \cdot \textbf{f}_p \pmod p = 1\)
\(\textbf{f} \cdot \textbf{f}_q \pmod q = 1\)
Using an inverse function we get [here]:
\(\textbf{f}_p= [9, 5, 16, 3, 15, 15, 22, 19, 18, 29, 5]\)
\(\textbf{f}_p = 9x^{10} + 5x^9 + 16 x^8 +3 x^7 + 15 x^6 + 15 x^5 + 22 x^4 + 19 x^3 + 18 x^2 + 29x +5\)
The public key then becomes:
\(\textbf{h} = p \cdot \textbf{f}_q . \textbf{f} \pmod q\)
In this case we get:
\(\textbf{f}_q \cdot \textbf{g} = [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30]\)
In order to create a ring, we then divide by \(x^N -1\) and get:
H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]
And the private key is \(\textbf{f}\) and \(\textbf{f}_q\).
To encrypt we take Bob's public key (\(h\)), a random polynomial (\(\textbf{r}\)) and a message (\(\textbf{M}\)), and then compute:
\(Enc = \textbf{r} \cdot \textbf{h} + \textbf{M}\)
To decrypt, first we multiply by Bob's private key \(\textbf{f}_q\) and take \(\pmod q\):
\(Dec= (\textbf{r} \cdot \textbf{h} + \textbf{M}) . \textbf{f} \pmod q\)
and which gives:
\(Dec= (p \cdot \textbf{r} \cdot \textbf{f}_q \cdot \textbf{g}+ \textbf{M}) . \textbf{f} \pmod q\)
and since \((\textbf{f}_q . \textbf{f}) \pmod q\) is 1, we get:
\(Dec= (p \cdot \textbf{r} \cdot \textbf{g}+ \textbf{M} \cdot \textbf{f}) \)
Finally we multiply by \(\textbf{f}_p \pmod p\):
\(Dec= (p \cdot \textbf{r} \cdot \textbf{g}+ \textbf{M} \cdot \textbf{f}) . \textbf{f}_p \pmod p\)
This will be:
\(Dec= p \cdot \textbf{r} \cdot \textbf{f} \cdot \textbf{f}_p+ \textbf{M} \cdot \textbf{f} \cdot \textbf{f}_p \pmod p\)
And since we have a multipler of \(p\), we will get a zero value for the first term as we have \(\pmod p\) operation:
\(Dec= 0+ \textbf{M} \cdot \textbf{f} \cdot \textbf{f}_p \pmod p\)
And since \(\textbf{f} \cdot \textbf{f}_p \pmod p\) will be 1, we get:
\(Dec= \textbf{M}\)
Example values of the parameters are:
- Minimal security: \(N=167, p=3, q=128\)
- Good security: \(N=251, p=3, q=128\)
- Strong security: \(N=347, p=3, q=128\)
- Excellent security: \(N=503, p=3, q=256\)
Performance evaluation
For ECDSA, RSA, Ed25519 and Ed448 we have:
Method Public key size (B) Private key size (B) Signature size (B) Security level ------------------------------------------------------------------------------------------------------ Ed25519 32 32 64 1 (128-bit) EdDSA Ed448 57 57 112 3 (192-bit) EdDSA ECDSA 64 32 48 1 (128-bit) ECDSA RSA-2048 256 256 256 1 (128-bit) RSA
The following provides an analysis of the PCQ methods for digital signing:
Method Public key size Private key size Signature size Security level ------------------------------------------------------------------------------------------------------ Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice Rainbow Level Ia (Oil-and-Vineger) 161,600 103,648 66 1 (128-bit) Multivariate (UOV) Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) Multivariate (UOV) Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) Multivariate (UOV) Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based Picnic 3 Full 49 73 71,179 3 (192-bit) Symmetric GeMSS 128 352,188 16 33 1 (128-bit) Multivariate (HFEv-) GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate (HFEv-)
For performance on M4 (ARM Cortex-M4 dev) [1] and measured in CPU operations per second. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Key generation Sign Verify ---------------------------------------------------------------- Crystals Dilithium 2 (Lattice) 36,424 61,312 40,664 Crystals Dilithium 3 50,752 81,792 55,000 Crystals Dilithium 5 67,136 104,408 71,472 Falcon 512 (Lattice) 1,680 2,484 512 Falcon 1024 1,680 2,452 512 Rainbow Level Ia (Oil-and-Vineger) 2,969 4,720 2,732 Rainbow Level IIIa 3,216 3,224 1,440 Rainbow Level Vc 3,736 6,896 4,928 Sphincs SHA256-128f Simple 2,192 2,248 2,544 Sphincs SHA256-192f Simple 3,512 3,640 3,872 Sphincs SHA256-256f Simple 5,600 5,560 5,184
For stack memory size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Memory (Bytes) ------------------------------------------------- Crystals Dilithium 2 (Lattice) 13,948 Crystals Dilithium 3 13,756 Crystals Dilithium 5 13,852 Falcon 512 (Lattice) 117,271 Falcon 1024 157,207 Rainbow Level Ia (Oil-and-Vineger) 404,920 Rainbow Level IIIa 405,412 Rainbow Level Vc 405,730 Sphincs SHA256-128f Simple 4,668 Sphincs SHA256-192f Simple 4,676 Sphincs SHA256-256f Simple 5,084
Code
We can create a Dotnet console project for .NET 8.0 with:
dotnet new console
First we install the Bouncy Castle library:
dotnet add package BouncyCastle.Cryptography
Next some code:
namespace Falcon { using Org.BouncyCastle.Pqc.Crypto.Falcon; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var msg="Hello"; var method="Falcon2"; if (args.Length >0) msg=args[0]; if (args.Length >1) method=args[1]; var random = new SecureRandom(); var keyGenParameters = new FalconKeyGenerationParameters(random, FalconParameters.falcon_512); if (method=="Falcon1024") keyGenParameters = new FalconKeyGenerationParameters(random, FalconParameters.falcon_1024); var keyPairGen = new FalconKeyPairGenerator(); keyPairGen.Init(keyGenParameters); var keyPair = keyPairGen.GenerateKeyPair(); var pubKey = (FalconPublicKeyParameters)keyPair.Public; var privKey = (FalconPrivateKeyParameters)keyPair.Private; // Signing var aliceSign = new FalconSigner(); aliceSign.Init(true, privKey); var signature = aliceSign.GenerateSignature(System.Text.Encoding.UTF8.GetBytes(msg)); // verify signature var bobVerify = new FalconSigner(); bobVerify.Init(false, pubKey); var rtn = bobVerify.VerifySignature(System.Text.Encoding.UTF8.GetBytes(msg), signature); Console.WriteLine("Message:\t{0}",msg); Console.WriteLine("Method:\t\t{0}",method); Console.WriteLine("\nPublic key (length):\t{0} bytes",pubKey.GetEncoded().Length); Console.WriteLine("Alice Public key (first 50 bytes)):\t{0}",Convert.ToHexString(pubKey.GetEncoded())[..100]); Console.WriteLine("\nPrivate key (length):\t{0} bytes",privKey.GetEncoded().Length); Console.WriteLine("Alice Private key (first 50 bytes)):\t{0}",Convert.ToHexString(privKey.GetEncoded())[..100]); Console.WriteLine("\nSignature (length):\t{0} bytes",signature.Length); Console.WriteLine("Signature (first 50 bytes):\t\t{0}",Convert.ToHexString(signature)[..100]); Console.WriteLine("\nVerified:\t{0}",rtn); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
A sample run with Falcon1024 gives:
Message: Post Quantum Crypto Method: Falcon1024 Public key (length): 896 bytes Alice Public key (first 50 bytes)): 821C14108E9BE25C5124A11647AC9FDA2774045F299D8185F57EA9BA907A6D145FC57B7BA0C6232C6FCE5E0C5C53C90F2D6A Private key (length): 1280 bytes Alice Private key (first 50 bytes)): 0BFFC1E85182F3E0FC0BC0B9F8228117FF7AE82F8504517FFC10FE03FF810C210407FF7EFFCE81FFFE84F81E4503B03EFC60 Signature (length): 658 bytes Signature (first 50 bytes): 39A16AA40E28D8893B19CFFF6BC451C42F55222BCE828D2BB37A7C7FB1801F7B74607DBCCCCCAD01545FBC29EA743B8597EF Verified: True
References
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].