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, and a signature size of 666 bytes, while FALCON-1024 gives a public key of 1,793 bytes and a signature size of 1,280 bytes.
Falcon - Post-quantum robust digital signatures |
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\)
import falcon import sys import binascii N=128 M="hello" if (len(sys.argv)>1): M=str(sys.argv[1]) if (len(sys.argv)>2): N=int(sys.argv[2]) print ("Message: ",M) M=M.encode() sk = falcon.SecretKey(N) pk = falcon.PublicKey(sk) print ("Private key:",sk) print ("Public key: ",pk) sig = sk.sign(M) print ("\nSignature: ",binascii.hexlify(sig)) rtn=pk.verify(M, sig) print ("\nSignature verification: ",rtn)
A sample run of using an \(N\) value of 32 is:
Message: Hello Params: {'n': 32, 'sigma': 154.6747794602761, 'sigmin': 1.1925466358390344, 'sig_bound': 1852696, 'sig_bytelen': 82} Private key (f): [7, 21, -21, 13, 0, 5, 4, -4, -11, 16, 4, -10, 32, 29, -10, 16, -27, 8, 20, 2, 2, 45, 20, 7, -11, 8, 0, -11, 9, 31, 15, 6] Private key (g): [-7, 14, 10, -3, 23, -1, 21, 7, -11, 9, -3, -3, -18, 6, 6, 2, -9, 4, -25, 15, 9, 4, 16, -15, 4, 34, 0, 2, 14, 10, 36, 0] Private key (F): [0, -42, 52, 42, 5, 20, 20, 1, 10, -57, -39, 9, -25, 29, 32, -28, -2, -10, -12, -27, -34, -19, 25, -47, 17, 12, 2, -19, -19, -22, 40, 15] Private key (G): [-8, -13, 23, -4, -17, 28, -11, 0, -5, -8, -12, -73, 32, 5, -14, 10, 32, -40, 52, -84, -37, 14, -5, 14, -28, 12, -10, -17, 43, -13, -7, -35] Public key (n): 32 Public key (h): [1963, 3496, 10854, 2667, 9364, 5962, 4641, 5262, 11809, 6207, 2827, 5191, 7644, 11634, 1835, 6, 9389, 854, 772, 11621, 3926, 401, 5324, 9751, 12110, 11105, 10216, 8785, 7072, 4246, 544, 7710] Signature: b'35b0406dbdd40dd178e5ad43f695b850d63241f79265697bbd4838927f9b2007e82220c7b0b38d3805d5cc782839b577c7a97cdefd8aebc4f5bed90fb5a5a4983ea96d2ec762738d59f7a5bc548f94000000'
and for \(N=128\):
Message: Hello Params: {'n': 128, 'sigma': 160.30114421975344, 'sigmin': 1.235926056771981, 'sig_bound': 7959734, 'sig_bytelen': 200} Private key (f): [3, 9, 6, 17, 5, 9, 10, -2, 3, 0, -1, -6, -10, 3, -4, 2, 13, 2, -2, -14, 3, -16, 1, 3, -6, -14, 3, 1, 11, -10, 6, 0, 1, -3, -5, 4, -1, 2, -5, 9, -5, -3, 4, 12, -2, 13, 11, 3, -5, 8, -22, -3, 2, 11, 9, -3, 5, 7, -11, -3, 15, 4, -1, 0, 12, -4, 11, -4, -8, 3, 19, 5, 10, 2, 3, 2, 7, -13, -2, 6, -4, 2, 1, -5, -4, 2, 2, -9, 13, -7, 10, 0, 5, 6, -1, 10, 2, -10, 14, 2, -8, -8, 6, -1, -2, -3, 7, -5, 0, 2, -4, 11, -11, 2, 11, 3, 0, -3, 20, -9, 11, 2, 2, -9, -1, 0, 5, 2] Private key (g): [-12, -3, -9, 9, 10, 4, 10, 4, 4, -7, 0, 11, 7, 7, 2, -3, -3, 3, -2, -9, 3, 15, -1, -4, 0, -10, 8, -4, 15, 3, 9, 5, 2, 0, 5, 2, 0, -4, 14, -7, 7, 3, -6, 6, 9, 5, -11, -12, 5, -1, -6, 14, -4, 10, 11, 4, -14, -4, 8, -3, -6, -5, 6, 12, -1, 0, 2, -15, 6, -4, 2, -18, 15, 17, -4, 14, -3, 2, -2, -5, -10, 3, 7, -4, -2, -7, -4, 6, -6, -3, -15, 14, 12, -4, 7, 9, -2, 13, 1, -9, 3, 2, 1, 11, 28, 16, -11, 3, 5, -9, 21, 11, 10, 6, -2, 11, -11, 3, 1, 6, -1, 4, 6, 1, -12, 14, 15, -10] Private key (F): [-9, -36, -6, -3, 2, -9, 10, 25, 13, 26, 1, 46, -20, -17, -13, 15, 0, -16, 73, -10, 8, -21, -34, 7, 24, 34, -18, -12, -54, -17, -42, 47, -27, 46, 22, 9, 4, 18, 9, -46, -13, -7, 10, 23, 9, 26, 9, 54, -36, 14, 40, 21, -53, 35, 2, 1, 26, 28, 7, 6, 12, -1, -14, 21, 0, 16, -11, 12, -26, 21, 8, 13, 0, 0, 18, 60, 20, 49, 5, 25, -27, -12, -24, 2, -5, 26, -22, 6, -17, 2, -18, -10, 5, 2, 1, 15, -25, -7, -23, 17, 32, 48, 71, -3, 17, -39, 22, 37, -5, -27, -12, 12, -12, -27, 12, 4, 63, -26, 27, -23, 22, -5, 23, 4, 9, 17, 23, -37] Private key (G): [-5, 18, 9, 19, 6, -28, -14, -19, -5, 14, -7, 39, 2, -8, -5, 26, -5, 39, -1, -6, 61, 14, -27, -38, 11, -28, -5, 26, 14, -27, -38, 14, -34, -3, 27, 52, -10, -3, -63, 14, -35, 5, 56, -14, 32, -11, 6, -68, -14, 15, -3, -15, 0, 21, -22, -10, -2, -26, 46, 32, 12, -26, 4, -5, -12, -7, 66, 5, -6, -3, -13, -26, 3, 41, -13, 12, 48, 27, 10, -36, 49, 2, 45, 5, 67, -25, -33, -13, -47, 9, 37, 51, -1, 17, 16, 15, -26, -18, 26, 11, 39, 4, 5, -5, 32, 52, 42, 24, 8, 43, -26, -36, 20, 44, 44, 50, 9, -27, 12, 41, -46, -76, 52, -4, 5, -39, -22, 3] Public key (n): 128 Public key (h): [1047, 4241, 11165, 10837, 1104, 6040, 2557, 10153, 5381, 6397, 9897, 5710, 2548, 5678, 11564, 4408, 2092, 10727, 337, 3253, 8390, 2944, 9337, 6943, 6370, 5782, 2721, 508, 3184, 9157, 12085, 2137, 10040, 978, 1052, 1658, 12018, 5832, 11191, 11022, 11674, 2286, 5559, 4138, 3113, 6198, 6700, 7863, 11052, 12286, 1002, 2786, 11385, 1384, 11477, 1240, 3835, 10122, 5671, 3242, 5387, 5701, 5866, 11823, 3903, 8336, 12051, 4013, 5772, 3500, 8756, 7402, 11361, 9301, 10169, 1527, 1315, 2712, 3873, 11584, 10823, 10545, 2009, 7368, 6375, 7578, 9572, 680, 1884, 3431, 4487, 11278, 11528, 10541, 2160, 1369, 3675, 6503, 11041, 10722, 8242, 4443, 5879, 10109, 8454, 1337, 8173, 8268, 4579, 5576, 9876, 6048, 9151, 1452, 12287, 10079, 7905, 1891, 805, 7106, 3141, 7108, 5461, 11325, 818, 8777, 6685, 8670] Signature: b'37e81845f909070a0637361d63653dd6a50277d496402c31f43107203b60e663e59fce86dda6be967a2d72a049b635af4f7b4efad522edd292b35ce95890c89e676ecce9a73016d620d1e7dd1f2927a365c5053daed75aad139ab0495c3884b8fbd26e9139713c9769db76f6434ae8523e3d948e1fcb9627bad793519667b7ce6898cbc8bc61d1bae5345025f972f3ea66d5586493db4270f17bc9c5bcc823bb2d231eaef1ceea531b3b982ad4a1178d3331dd84fd57357124ba3d295c5a46c8bd40000000000000' Signature verification: True