Related: [Kyber KEM][Kyber KEX][Dilithium Dig Sig Speed][Factoring signature (ECC)][Factoring signature (Logs)][Falcon Digital Signature][Rainbow Digital Signature][Dilithium Digital Signature][SPHINCS+][GeMSS]
FALCON - Digital Signature
[Lattice Home][Home]
Falcon is 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. 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.
Related: [Kyber KEM][Kyber KEX][Dilithium Dig Sig Speed][Factoring signature (ECC)][Factoring signature (Logs)][Falcon Digital Signature][Rainbow Digital Signature][Dilithium Digital Signature][SPHINCS+][GeMSS] |
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:
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
The following is an implementation of FALCON:
#include stdio.h #include stdint.h #include "rainbow_config.h" #include "utils.h" #include "rng.h" #include "api.h" #define MLEN 59 char *showhex(uint8_t a[], int size) ; char *showhex(uint8_t a[], int size) { char *s = malloc(size * 2 + 1); for (int i = 0; i < size; i++) sprintf(s + i * 2, "%02x", a[i]); return(s); } int main(void) { size_t i, j; int ret; size_t mlen, smlen; uint8_t b; uint8_t m[MLEN + CRYPTO_BYTES]; uint8_t m2[MLEN + CRYPTO_BYTES]; uint8_t sm[MLEN + CRYPTO_BYTES]; uint8_t pk[CRYPTO_PUBLICKEYBYTES]; uint8_t sk[CRYPTO_SECRETKEYBYTES]; randombytes(m, MLEN); crypto_sign_keypair(pk, sk); crypto_sign(sm, &smlen, m, MLEN, sk); ret = crypto_sign_open(m2, &mlen, sm, smlen, pk); if(ret) { fprintf(stderr, "Verification failed\n"); return -1; } if(smlen != MLEN + CRYPTO_BYTES) { fprintf(stderr, "Signed message lengths wrong\n"); return -1; } if(mlen != MLEN) { fprintf(stderr, "Message lengths wrong\n"); return -1; } for(j = 0; j < MLEN; ++j) { if(m2[j] != m[j]) { fprintf(stderr, "Messages don't match\n"); return -1; } } randombytes((uint8_t *)&j, sizeof(j)); do { randombytes(&b, 1); } while(!b); sm[j % (MLEN + CRYPTO_BYTES)] += b; ret = crypto_sign_open(m2, &mlen, sm, smlen, pk); if(!ret) { fprintf(stderr, "Trivial forgeries possible\n"); return -1; } printf("CRYPTO_PUBLICKEYBYTES = %d\n", CRYPTO_PUBLICKEYBYTES); printf("CRYPTO_SECRETKEYBYTES = %d\n", CRYPTO_SECRETKEYBYTES); printf("CRYPTO_BYTES = %d\n", CRYPTO_BYTES); printf("Signature Length = %d\n", smlen); printf("\nAlice Public key (only showing 1/512 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/512)); printf("Alice Secret key (only showing 1/512 of key): %s\n",showhex(pk,CRYPTO_SECRETKEYBYTES/512)); printf("\nMessage: %s\n",showhex(m,MLEN)); printf("Signature : %s\n",showhex(sm,smlen)); printf("Verfied : %d\n",r); return 0; }
A sample run of Rainbow Classic shows that the public key size is 161,600 bytes, the secret key is 103,648 bytes, and the digital signature of 66 bytes:
NAME: Falcon-512 CRYPTO_PUBLICKEYBYTES = 897 CRYPTO_SECRETKEYBYTES = 1281 CRYPTO_BYTES = 690 Signature Length = 716 Alice Public key (only showing 1/16 of key): 090001ae939954841bee5a90a116d2047d658861ec82175c6775875abfa982b4d8bb627a778d736617a5fa79751799f66102898c5d347f9a7129b61588ef90144ff9c2c59acbe0431e47c5c6ebdf664228e076d8fc020590cb2bada64ff126821f4ef50770ab87b9044fa83d068a82af Alice Secret key (only showing 1/16 of key): 090001ae939954841bee5a90a116d2047d658861ec82175c6775875abfa982b4d8bb627a778d736617a5fa79751799f66102898c5d347f9a7129b61588ef90144ff9c2c59acbe0431e47c5c6ebdf664228e076d8fc020590cb2bada64ff126821f4ef50770ab87b9044fa83d068a82af93679e87746aae9715b693a7948a1423b42341c76f7a664d07db58df2f780e1286ca969f10028c62095b5009854541d4 Message: 530f8afbc74536b9a963b4f1c4cb738bcea7403d4d606b6e074ec5d3baf39d18726003ca37a62a74d1a2f58e7506358edd4ab1284d4ae17b41e859 Signature : 02671c0ca58c64ac5783c02f388bfc85d9e8ac22e601e406b05ea047dab94e598d53c1643ede3c3e0c41530f8afbc74536b9a963b4f1c4cb738bcea7403d4d606b6e074ec5d3baf39d18726003ca37a62a74d1a2f58e7506358edd4ab1284d4ae17b41e85929c6db27522363aec5acf20b35639a86ce7be64d459c8cfff9cf47aabd0d0a588073f9985ff90a92c56fbfe4408419ccb5df6c52647d0b62838e420954408ce2f249e7ffaf2744cf343227e164a3c79cd523bce4b6d51b69a889b97dac716879b7cd1290cb8b14f1b7b742900a2cbdb2f5c23111ed2b73b7bf4a3df8112881cfd1373d65e5110b2d4db3bdce597964ceac934ce0057f2b24edc8f1e9ba86d11a020ad347090b295adb3f3b05ae2ad774d4828f0c57195619adb9220c7b72c4eed7c7cdac90742b0f4d29f781bc5beb971395e98df8708b1b67dc6f1468defb3bc454cb9da0802c32fcb214c6960dbdade2e96a55d6093c4eb86a972dbdbbe9a251a6db21319d91d6402fedc667179c6b15faaebb3d9a846850a269b879d5df3fbe83c8a159c4a50388f86fb1f62556d9dda0682fbda5c5412fbbbb7d0647ed2354941840f4c7d5cacee9687dfffce0d54fde4de65cf12faf3f5150e5bee81235bf45dd64d5ae8dea5ad9bbc447ee9028df7e97d72ef36fcecd6cc3a41781116cbe9b6345b383ba68e69fecc710cce669218c58b86e52af04766e11ffe4322ab27eabd6f8af66746bb5ef1a30e16b5c7f76db090451747f2856a1d4b375dc482089350db4692085a39ae8414f936246eb171545dd4a24f272f13fa2886b8d41aebe6c061a7cf15353c57a7275e464399bd93ff962f9fc9c3f1c6fb2bfcc8a7c97bd19121ade8ca742f0c7692e3f5de26511ef3278e648e4c705826fcde62193df6fdd0e5364d2e684015e89bc36e33dc99fa91de30cace92cbc63d3dcf67f109d512f6151568a1baf57717ed860b34f11ca772f15cb9cc7c5a272c091bf0e8c8c28116a62392680
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].