For PQC, We Need The Vision of a Falcon
For PQC, We Need The Vision of a Falcon
As you may know, most of our public key methods are at threat from quantum computers. This includes ECC, RSA and discrete log methods. And so, over the next decade, we are likely to see a migration of these methods to ones which are quantum robust — and see the rise of PQC (Post Quantum Cryptography).
And so NIST announced that Falcon is one of the standards that are progressing for standardization for PQC within digital signatures. The method is derived from NTRU (Nth degree‐truncated polynomial ring units) and is a lattice-based method for quantum robust digital signing.
Performance and key sizes
With Falcon-512 (which has an equivalent security to RSA-2048), we generate a public key of 897 bytes a private key of 1,281 bytes, and a signature size of 690 bytes, while FALCON-1024 gives a public key of 1,793 bytes, a private key of 2,305 bytes, and a signature size of 1,313 bytes [here]:
Falcon uses NTRU as an asymmetric encryption method 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. Overall, it is relatively slow compared with Dilithium for key generation, but is closer in performance when it comes to key signing and verification:
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) RSAThe 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,184For 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,084Method
So, let’s take a simple example for how NTRU works. Overall, Falcon is based on the Gentry, Peikert and Vaikuntanathan method for generating lattice-based signature schemes, along with a trapdoor sampler — Fast Fourier sampling. Initially, we select three parameters: N, p and q. To generate the key pair, we select two polynomials: f and g. From these we compute:
and where f and fq are the private keys. The public key is:
Bob and Alice agree to share N (and which limits the largest polynomial power), p and q, and then Bob generates two short polynomials (f and g), and generates his key pair from this. These polynomials have the coefficients of -1, 0 and 1. For example, with N=11, p=3 and q=32. If Bob picks values of:
f=[−1,1,1,0,−1,0,1,0,0,1,−1]
Then as a polynomial representation:
f=−1+x+x²−x⁴+x⁶+x⁹−x¹⁰
And then picks g:
g=−1+x²+x³+x⁵−x⁸−x¹⁰
We then should be able to calculate the inverse of f for (mod p) and (mod q). Thus:
f⋅fp (mod p)=1
f⋅fq (mod q)=1
Using an inverse function we get [here]:
fp=[9,5,16,3,15,15,22,19,18,29,5]
fp=9x¹⁰+5x⁹+16x⁸+3x⁷+15x⁶+15x⁵+22x⁴+19x³+18x²+29x+5
The public key then becomes:
h=p⋅fq.f (mod q)
In this case we get:
fq⋅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 f and fq.
To encrypt we take Bob’s public key (h), a random polynomial (r) and a message (M), and then compute:
Enc=r⋅h+M
To decrypt, first we multiply by Bob’s private key fq and take (mod q):
Dec=(r⋅h+M).f (mod q)
and which gives:
Dec=(p⋅r⋅fq⋅g+M).f(mod q)
and since (fq.f)(mod q) is 1, we get:
Dec=(p⋅r⋅g+M⋅f)
Finally we multiply by fp (mod p):
Dec=(p⋅r⋅g+M⋅f).fp (mod p)
This will be:
Dec=p⋅r⋅f⋅fp+M⋅f⋅fp (mod p)
And since we have a multiplier of p, we will get a zero value for the first term as we have (mod p) operation:
Dec=0+M⋅f⋅fp (mod p)
And since f⋅fp (mod p) will be 1, we get:
Dec=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.
Coding
The coding is [here]:
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 [here]:
Message: Post Quantum Crypto
Method: Falcon512
Public key (length): 896 bytes
Alice Public key (first 50 bytes)): 33AE8162CE525CAB957E55B247E155844595285D1D48593FA4242BD4193CFADAF1E988737026D133DF875FB63EC652AE325E
Private key (length): 1280 bytes
Alice Private key (first 50 bytes)): FBFFC1E3FF02F811840B9141FFE0C3043079EBCEFBEC10040402BDFC0FC30FEF0310210307B27E17F03C009EC1F821C007D1
Signature (length): 654 bytes
Signature (first 50 bytes): 3924784F35D2A8ACF72AF51448B40ACE2E8B32AFC162DAB81AE34466C74501E0BCA0A101587310FED69BEE910E072F2F40A1
Verified: TrueConclusions
Falcon is slower in performance than Dilithium, but the key sizes and ciphertext are much smaller:
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
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) LatticeReferences
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4