Tidecoin's signature algorithm

Tidecoin replace ECC with the signature scheme Falcon. The lib can be used to create keys, signature msg, verify signatures.

falcon.py

This repository implements the signature scheme Falcon (https://falcon-sign.info/). Falcon stands for FAst Fourier Lattice-based COmpact signatures over NTRU

Content

This repository contains the following files (roughly in order of dependency):

1. common.py contains shared functions and constants
2. rng.py implements a ChaCha20-based PRNG, useful for KATs (standalone)
3. samplerz.py implements a Gaussian sampler over the integers (standalone)
4. fft_constants.py contains precomputed constants used in the FFT
5. ntt_constants.py contains precomputed constants used in the NTT
6. fft.py implements the FFT over R[x] / (xⁿ + 1)
7. ntt.py implements the NTT over Z_q[x] / (xⁿ + 1)
8. ntrugen.py generate polynomials f,g,F,G in Z[x] / (xⁿ + 1) such that f G - g F = q
9. ffsampling.py implements the fast Fourier sampling algorithm
10. falcon.py implements Falcon
11. test.py implements tests to check that everything is properly implemented

How to use

1. Generate a secret key sk = SecretKey(n)
2. Generate the corresponding public key pk = PublicKey(sk)
3. Now we can sign messages:
   • To plainly sign a message m: sig = sk.sign(m)
   • To sign a message m with a pre-chosen 40-byte salt: sig = sk.sign(m, salt) Note that the message MUST be a byte array or byte string.
4. We can also verify signatures: pk.verify(m, sig)

Example in Python 3.6.9:

>>> import falcon
>>> sk = falcon.SecretKey(512)
>>> pk = falcon.PublicKey(sk)
>>> sk
Private key for n = 512:

f = [-1, 3, -2, -4, 5, -4, 4, -9, 5, 2, 6, 4, 4, 0, 1, -4, -4, -2, 2, -1, 7, -7, -2, -3, 7, -2, 6, -4, 2, -1, -1, 4, 0, -2, -1, -4, -1, -3, 1, 6, 4, -1, -3, 3, -6, 4, 3, -2, 2, 6, 0, -1, -3, 2, -5, -5, -4, 0, -4, 1, 3, -2, 10, 5, -5, -4, 1, 0, 0, 3, -1, 7, 5, -1, -2, 2, -3, -1, 4, 1, -2, -3, 6, 8, 2, 3, -7, 0, -1, -1, 3, 1, 10, -5, 5, -2, 2, -5, 4, -4, -8, 1, 3, 0, -5, 3, 6, 6, 3, 0, 2, 1, 3, 6, 1, 2, 0, 4, -3, 2, 7, 3, -1, -1, -6, 2, 3, 3, 0, 2, -5, -8, -1, 3, 1, -6, 0, 2, -4, 1, 1, 1, 1, 0, 0, 7, 11, 2, 3, 0, 1, 3, 5, -1, -4, 0, 3, -2, 3, 0, -3, 0, -2, -1, -2, -4, -3, 3, 4, 0, 0, -2, 4, -7, 5, -6, 3, -3, -2, -2, 2, 1, 3, 0, -6, -2, 5, 2, -1, -5, -3, 2, -2, 0, 3, -5, 1, -2, -5, 10, -3, 5, 3, 2, 1, -2, -1, 1, -6, -1, 0, -4, 7, 6, -1, -6, -2, -1, 6, -8, -2, 2, -3, 7, -3, 5, -3, -2, 1, -5, 3, 2, 9, -5, 4, 3, -2, 4, 7, 1, 1, 0, -4, 2, 0, 0, 3, 2, 4, 0, -3, 0, 5, 1, -1, -4, -7, 6, -3, -6, 8, -2, 7, -4, 2, 4, 0, -1, 7, 1, 3, -3, -7, 4, 8, 8, 1, 4, 4, 4, -1, -1, -12, 6, -2, 1, 0, 1, 3, 0, -3, -5, -6, -2, 3, 7, 0, -3, 1, 3, 2, -3, -1, 0, 1, -9, 0, 3, -3, -2, 4, 1, 6, -4, 6, -5, 0, -1, 1, 3, -3, 1, -2, 1, -3, -9, -1, -7, -5, -7, 6, -5, -1, 0, -1, -1, 1, 3, -1, -4, 6, 6, -3, 2, -8, 3, 2, -4, 0, -1, 1, -2, -3, -4, 2, 1, 9, 0, -1, 6, 1, -6, -1, 3, 0, -3, -6, 5, 0, 6, 7, 6, -9, 0, -5, 2, -1, 1, 2, 0, -5, 11, 0, -10, -5, -4, 3, 9, -1, -4, 4, 0, -4, -3, -2, -4, -3, -1, 0, -2, -2, 3, 0, 1, 7, -1, 1, -4, -5, 0, -7, 2, 3, 3, -3, -1, 0, 6, -8, 0, 3, 8, -1, 1, 4, 7, 1, 5, 0, 5, 1, 3, 2, -5, 2, -4, 5, -5, 3, -3, 5, 7, -9, 7, -5, 1, 3, 5, -5, 1, 7, -2, 1, -5, 7, -2, -4, -1, -2, -1, -3, -2, 1, -1, 0, 2, -3, -2, -3, 3, -9, -4, -5, 7, 1, -6, -1, -2, -4, -1, 2, 0, 1, 8, -1, 5, -11, -6, -1, -7, -4, -3, 1, 0, 9, -3, -9, 2, 2, -1, 6, 3, 9, -4, -1, -6, 3, -5, 1, 0, -4, -2]
g = [-1, -1, 1, 3, -1, -2, -1, 1, 0, -2, 4, -5, -1, 5, -2, -3, 0, 3, 2, 4, -1, -3, -6, -2, 1, -5, -8, 2, 4, 2, -2, -2, 6, 9, -2, -4, -4, 1, 0, 7, 0, 7, 6, 2, 1, 3, 2, 0, -1, -9, -5, -7, -1, -7, 8, 2, -4, -1, 8, 1, -2, 3, 2, 1, 3, 3, 5, 10, -4, -2, -4, -1, -6, -3, 10, -1, -1, -6, -5, 2, -1, 3, -4, 2, 6, -3, -1, 1, 2, 6, -4, -4, 3, -10, 7, 10, 4, -2, 0, 2, -1, -3, 4, 2, 0, 8, -5, 4, -3, 4, -2, 6, 6, -3, -2, 6, 2, 4, -3, -5, -2, -4, -3, 0, 2, 0, -3, 0, 1, 1, -3, 1, -3, 3, 2, 4, 2, -7, -2, -4, 0, -4, -2, -2, 2, 3, -5, 1, -1, -8, -3, 4, 9, -1, 3, 9, 2, 0, 5, -4, 3, 4, -2, 2, -1, -1, -1, -5, 2, -2, 1, 2, 0, 3, 9, 0, -7, 0, -4, 3, 2, -3, 1, 3, 0, 4, 1, 1, -2, 2, 1, 5, -6, -10, -1, -1, 1, -5, 3, 0, -3, -2, -2, 0, 2, 1, 3, 1, 7, 1, -10, -1, -3, 5, 0, 3, 4, -4, -4, -2, -6, 4, 5, -6, 2, -1, 2, 2, -9, -1, -3, -4, -1, -7, 5, 5, -4, -4, -8, -7, -2, -2, 2, 1, -11, -4, 6, 2, -3, -6, -1, -1, -4, 6, -4, -1, 1, 6, 2, 3, 3, -2, 1, 4, 7, -2, -5, 2, 1, -3, -1, 1, -3, -1, 6, 1, 6, -2, -1, 11, -1, -3, -3, 7, -1, -4, 4, 1, -2, 5, 2, -4, 3, -3, -9, -6, -1, -1, 1, 3, -3, 4, -4, -1, -6, -4, 4, -7, 1, 0, -1, -5, -6, 8, 0, 9, -7, -6, 0, -5, 5, 2, -5, -1, 3, 2, -3, 3, -2, 5, -4, 2, -1, 1, 0, 5, 0, -5, -8, -2, 0, -3, -6, 0, 0, -3, 6, -2, -2, -3, -4, -2, -2, 3, 4, 10, 1, 3, 1, -6, -3, -1, -3, 0, 2, 1, -1, 2, -1, 0, 2, 7, 3, -3, 0, 0, -3, -1, -5, 0, -2, 2, 3, 1, -3, -3, 5, -2, -4, -1, -2, 0, 1, 4, 4, -2, 1, 6, -3, 8, -8, 1, 1, -3, -3, -5, 0, 2, -2, -4, 2, -3, -4, 11, 1, -1, 4, -3, -3, -6, 6, -3, 7, 0, 6, -5, 3, -1, 3, 7, 10, -1, 5, 0, 1, 0, 6, 3, -8, 2, -3, 2, -7, -4, 0, -6, -4, -6, 0, -2, 3, -4, -3, -1, 5, -1, 6, -1, -4, -3, 0, -4, -4, -5, 5, 1, -1, 3, -1, -2, 10, 1, 1, 5, 2, -2, 1, 9, 9, -4, 0, 2, -10, 3, -2, -4, 1, 3, -3, 6, -7, -4, 3, -2, -1, 0, 1, -1, -8, 6, 2, 0, 1, -1, -6, 6, 2, 4, -2, 3, 7, 5]
F = [-43, 18, 14, 16, 0, -24, -5, 45, 55, -33, 27, 41, 7, 2, 28, -28, 13, 27, -19, 15, -9, 0, -6, 30, -64, 7, -25, -13, -7, 1, 6, -2, -11, -24, -11, -2, 3, -53, 14, 17, 17, 18, 41, 22, 5, -20, 10, 22, -19, -2, -16, -17, 37, -4, -3, -15, -26, 15, 32, -7, -10, 7, 17, -43, 47, -25, -79, -15, 3, -27, 4, -46, -8, 41, 18, 32, -28, 30, -3, 75, -18, 12, -10, 27, -18, -77, 20, 26, 27, -37, 30, -17, -3, 23, 38, 30, -14, 4, -21, 15, -20, -15, 16, -37, 4, 16, -3, -38, -11, 28, -18, -48, -25, 21, 15, 24, -20, 31, -37, 10, -18, 27, -46, 20, 78, -22, 32, -56, 69, -9, 22, 31, -22, -21, 19, 16, -66, -68, -1, -12, 39, -20, -21, -14, 42, -5, -50, -37, -21, -4, 14, -22, -8, 0, 25, 1, -3, -19, 23, 7, -7, 4, 11, 11, 7, 42, -1, 23, -46, 13, -6, 33, -30, -1, 20, 22, -20, -16, 8, -21, 6, -10, 31, -38, -20, 10, 31, -26, -5, -4, -26, -5, -42, -15, -12, 7, -1, 42, -2, -93, 7, -16, 10, 33, 5, 32, -2, 22, 12, -43, -20, 25, -6, -52, -2, -36, 16, -15, -24, 0, 12, -18, -8, -12, -43, 37, -33, -37, -11, -9, 33, -4, 26, 9, -28, -34, 40, 12, 22, 22, -48, 28, -5, 51, -5, 14, 1, 44, -12, -15, -28, 26, 38, -15, -44, 7, 16, -22, 1, 20, -25, -30, 27, -14, -3, 22, -14, -27, 11, 17, 36, -6, -14, -16, -7, -42, 3, 35, 11, -18, 8, 57, -24, -11, -18, -18, 13, -28, -19, -23, -8, 61, 2, -37, 25, -31, -43, -14, -39, 46, -36, -8, -20, -2, 9, -61, 19, -37, -42, -5, -5, -39, 6, 50, 14, 0, -15, 35, -12, -16, 11, -15, 0, 15, 9, 30, -15, -35, 22, -41, -20, -48, 5, -6, 3, -44, -8, -30, 0, 0, -29, 21, -15, 18, -47, 7, -3, 37, 21, 36, -18, -4, -47, -18, -33, 16, 1, 54, -40, 17, 4, 8, -52, -4, -24, -5, -44, 11, 11, -29, 50, -47, -17, -15, 9, 43, -14, 32, -43, -2, -35, 9, 12, 26, 27, -21, -1, -69, 6, -20, 55, -12, -31, 40, 5, 4, 0, 33, 7, -19, -14, 34, -51, 10, -6, 26, -49, -1, -1, 49, 27, -9, -2, -16, -26, 11, 22, -41, 17, 17, 36, 21, -23, -1, -25, -3, -49, 21, 5, 27, 32, 40, -1, 24, 4, 37, -31, 2, -41, -7, -4, 32, -15, -37, 1, -14, 33, -37, -2, -33, 3, 2, -6, 6, 54, 9, 21, -63, 16, -27, 37, -19, -27, -38, 19, 8, -6, -31, -23, 10, 31, -33, 13, -2, -28, 2, -30, -5, -85, 39, 4, 1, 4, 10, -19, 46, -42, 26, -27, -34, -52, 42, 20, 25, -16, -4, -61, -41, 2, 12, -60, 1, 44, 34, 1, -29, 45, -5, -35, -49, 29, 15]
G = [19, 23, 32, 25, -17, -41, -8, 5, 19, -2, -2, 9, -34, -9, -43, -20, -18, 53, 32, -12, -9, 11, -4, -2, 32, 14, 3, -19, 14, 12, 0, -7, -1, -19, -16, -28, -23, 24, -19, -6, -7, -40, 3, 23, -5, 15, 49, 26, -20, -6, -50, 11, 7, 2, 4, -51, -12, -10, -3, -25, -48, -1, -5, 12, 2, 15, 18, 15, 12, -12, 31, -20, -2, 18, 4, 35, -27, 10, -59, -7, 26, -16, -27, -14, 9, 3, -23, 13, -28, -32, 23, 30, 8, -44, -23, 4, 15, -13, 26, 9, 17, -15, 21, 10, -17, 27, 26, 29, 54, -16, -6, -29, -52, 7, -1, 19, 19, -21, 28, 21, -15, -23, -18, 13, -12, 21, -17, 7, 16, -30, -10, -28, -29, -5, -23, 7, 8, 12, -17, 8, 22, 18, 10, 15, 10, -35, -36, 31, 24, -10, -12, -50, -33, 5, 4, -1, -31, 27, -26, -26, -34, -19, 11, 43, 40, 1, 7, 2, -17, -24, 41, -52, -11, 1, -3, 0, 64, 27, 58, -6, -19, 6, -28, -28, -8, -19, 15, 10, -60, 33, -2, 11, -12, -26, -1, -19, -69, 43, 23, -12, -15, -37, -36, -25, 0, -11, -41, 14, 5, -8, -26, 54, 7, -7, 24, 21, -7, -19, -8, 37, 36, 11, -39, -17, 1, -7, -23, 28, 16, -52, 5, 2, -13, 5, 3, 85, -4, 64, -16, 8, 28, 0, 14, -41, -89, 26, 48, 19, 20, -29, 20, -43, -13, -36, 22, -26, 45, 13, 5, -43, -2, 49, -49, 4, -2, 20, -44, 13, 16, 2, -15, 22, -30, -26, -22, 15, 24, 3, 6, -15, -3, 16, -8, 17, -18, 62, 49, 25, 34, -6, 6, -26, 11, 1, -34, -35, 8, 16, 10, -37, -22, -54, -28, 16, 27, -4, -56, -9, -4, 24, -66, 4, -8, 8, -26, -26, 18, 25, 20, 17, -17, 27, -11, 7, 9, 29, 78, 13, 3, 4, -28, 20, 22, -47, 21, 18, -5, 46, -9, 16, 6, -29, 11, 2, -15, 18, -3, 23, -8, -21, 5, -23, 22, -31, 10, -10, -20, 36, 7, 40, -24, -32, -1, -51, -35, -9, 51, 21, -6, 9, -10, -34, -22, 21, 15, -44, 36, 35, 25, -15, 26, 16, 55, 5, -20, -49, -3, 45, 2, 24, -41, -24, 16, 13, -23, 20, -12, 10, 19, -8, -13, -23, 60, 7, -36, 28, -21, -9, 40, -17, -8, -18, 34, 10, -9, -34, 16, -38, -12, -49, -59, -26, -35, -4, 44, -1, 22, -37, 45, -21, 17, 2, 17, 45, -18, 9, 15, 52, 20, 6, -2, -42, -40, -6, 45, -13, 36, -62, -1, 42, 18, -44, -25, 40, 7, 41, -15, 16, 0, 21, 30, -48, -21, -30, -12, 30, -13, 2, 31, 24, 8, 2, -85, -30, -12, 4, 20, 9, 40, 32, -11, 29, -13, 23, 27, 23, 6, 0, 3, 16, 36, 21, -2, 26, 16, -3, 5, 44, -5, -29, -18, -6, -26, -57, -21, 20, 12, 14, -49, -10, -33, -33]

>>> pk
Public for n = 512:

h = [11258, 99, 3612, 4343, 4615, 3280, 9626, 5553, 6831, 9501, 7934, 1900, 4306, 6843, 3713, 3001, 9825, 1536, 4967, 6108, 9434, 7846, 1773, 7172, 2823, 7078, 215, 3008, 8899, 9242, 9662, 12076, 2734, 5012, 1759, 11331, 1851, 10068, 10187, 11363, 6803, 8462, 3920, 4702, 2237, 6995, 7948, 3700, 9427, 7590, 3588, 1096, 2770, 2121, 4949, 2043, 648, 4912, 7884, 7892, 4459, 7340, 1708, 4855, 9363, 1214, 2006, 2427, 11605, 228, 9744, 11736, 10757, 8643, 5430, 10002, 11884, 5626, 1993, 8256, 1091, 5809, 8750, 7028, 6181, 4334, 1252, 7461, 7356, 9514, 9788, 6370, 2830, 1172, 3250, 2610, 8698, 8651, 4249, 7356, 3481, 3248, 149, 6322, 415, 9786, 1925, 8416, 8619, 3086, 10294, 5697, 6601, 4526, 3563, 1352, 8155, 11121, 800, 4754, 8661, 7659, 8997, 1545, 11797, 4076, 8850, 1560, 12167, 10440, 839, 1367, 9813, 8093, 9563, 10580, 2131, 11100, 10058, 937, 3657, 5007, 9070, 8309, 8038, 270, 10028, 10351, 3204, 2371, 10735, 2807, 12058, 476, 5147, 7239, 6921, 8321, 12227, 8633, 11602, 8249, 7950, 8271, 8520, 7253, 5082, 3721, 6235, 9384, 3683, 9041, 6883, 3969, 8973, 9686, 7649, 7993, 5483, 8523, 5462, 11295, 4251, 10711, 8623, 877, 3964, 5962, 5459, 456, 10210, 10273, 4047, 5161, 2968, 10037, 7072, 10161, 7520, 3233, 2460, 7306, 1478, 646, 729, 447, 3461, 3245, 3187, 10248, 8679, 11078, 10318, 8186, 7124, 4743, 924, 8077, 10247, 1420, 2230, 4200, 4792, 4461, 2300, 6847, 2611, 1267, 3199, 1522, 10374, 5972, 3138, 8848, 3326, 4454, 7655, 2907, 8557, 1374, 2207, 8201, 5315, 12274, 6905, 7256, 8447, 6332, 5722, 2679, 4232, 2217, 11753, 11698, 11614, 2755, 8028, 7527, 11889, 7751, 3990, 3194, 222, 10262, 1406, 7239, 1933, 12050, 2053, 872, 10686, 10742, 8471, 8612, 12109, 9046, 2888, 4168, 10748, 6896, 4836, 1943, 3613, 7591, 4541, 9201, 1051, 11549, 6359, 5781, 2388, 1509, 10294, 7818, 551, 10476, 7727, 8851, 6147, 6095, 9743, 8700, 4665, 10745, 1952, 2805, 6061, 7853, 4705, 8595, 1592, 11445, 2590, 1650, 9961, 3737, 11051, 9887, 2772, 11871, 11319, 9401, 1864, 5714, 11982, 9738, 4580, 11265, 8081, 67, 4243, 10577, 3648, 7786, 6788, 2813, 11012, 9976, 12077, 1537, 3935, 11301, 2538, 215, 2733, 10539, 2763, 5294, 9568, 3485, 10441, 7602, 775, 2244, 11717, 1170, 104, 9203, 5808, 5258, 1146, 11534, 8510, 2003, 11878, 8545, 8198, 685, 8332, 8752, 4906, 2161, 2175, 1682, 9668, 1011, 4462, 3234, 5122, 1278, 4249, 3223, 664, 11909, 1209, 9220, 3807, 4837, 5755, 3983, 7586, 5626, 420, 12208, 11592, 5671, 4405, 3037, 10163, 4935, 3415, 3201, 216, 10983, 2983, 3616, 8690, 12141, 5822, 8661, 5107, 5321, 6412, 5504, 2712, 8636, 4084, 7866, 11042, 7286, 5051, 4779, 534, 7054, 8932, 3983, 7799, 9474, 11817, 6356, 5109, 9410, 241, 9274, 6930, 12070, 3064, 8381, 9603, 4256, 11911, 7747, 7515, 8671, 2193, 8670, 9500, 1367, 6482, 6189, 3910, 3029, 9258, 5464, 5524, 5478, 9161, 9644, 2343, 1831, 4510, 10859, 3527, 1213, 8282, 5793, 2328, 9176, 4137, 11772, 2886, 8185, 7817, 9541, 3531, 467, 11301, 207, 5633, 1084, 27, 8081, 11958, 9881, 10162, 5991, 11731, 10277, 11056, 844, 11277, 6358, 6460, 12143, 1394, 1016, 6089, 9789, 2980, 8148, 833, 2054, 12146, 1048, 6431, 6758, 9856, 7114, 9169, 6311, 1272, 3204]

>>> sig = sk.sign(b"Hello")
>>> sig
b'9\xe8%\xdf\xbb\xa2\x06TcH\xa6\x93\xb9q>\xe2\xec\x99\xf7\xc4\xe5>\xe8\x1dz\x9fX\x06\x14O\xdc\xd9\x97@\xe2\xee`\xc6\xf5j\x1a\xfb\xd02\xc8\x1d~\x12\xcao\xc8\x9e$\x85\xf7*N\x1dW\xbd\x01s\x12\x16r\x8c@5\xcd\x8f\xe3\xbf\x10\x1c\xd5\x14\xf2+T\xf9\x84P\xb4Vf_\x88*9\xda\xec\xa7K\x83e\x8b\x9cL\xd9\x1amz\xb4\x89:\x93\xfbZ\xbc;\'\xcf\x0f>B\xacY\xa2O\x90\xa6\xf3Yu1-\xc5\xa6W^6\xb9?\x86b\x13)*\x14\xc9\xbaW\xf71\xffea\x05\xc9\x9a\xfc\xa4\xe8\xf46\x1a\xec\xd2\x86\xdaM$!\xb6\x87\xaf\xe1\xc4\xc5/\xd3wm\x0blR;\xcd5\xd9C\x928\xa6\xcd\xf0\xcd\xe7\xf1\x15\xac\x85\x92\xe9\xe0\x83J\xe9\xd8\x8e?\x19\xac\xf4Z\xf6U\x8bRw\xd5N{L~W\xe569\xea\xdbE\x88\x98^<Y\x92#$\xdf\x93\x92\x9de":\x81&\x11W\xff\xa7\xa8A\xe4J\xa6\x19\x0e\xe8\xe9\xfeQ\xde\xee+\xac\xfe\xe1\xb8SJ\xd24\xa8\x89ZK,\xc1\xb1N\xac\xe2\xf9z\xc0\xe8"L\x16\xb5\x0b\x82 Q\xaeC\r\x9b\x94o\xe90#c\xc5\xe9\xb6\x0b\xe7\x11=.\xc5\x1d\x86\xe11\xa87\xcc\xf9\xa2\'\xf2B\xd2\xf1_\xe6;a\xbb\x0c\\W\x93\xc9ue\xd0\xe2\x0f\xb4i\x14[z\\\xdc\x9b8\xf0\xd3\x19\xc9\xae\xd6\xd0\xb0\xda\x92\xf9\x86\x16\xd1\xd0\xd2(v\x99XI\x1c\xf8A\x90`I\xd9:\xe6!\x9e\xeefn\x96c\xad\xd7\x1f6 \xb9\x14\xa6.\x89\xef\xcd\xa2\xe8U\xbaj\x9d\xcd\xa6\xf1\xf7[\x1a\xd2u\xe6\x88j\x1b\xd6\xc3\xfb\xacM\xae*\x9f\x1c &Lz\xa1\x1b\x95a\x15r\xa0\\\x16\x9b\x14\xc5sw\xef\x84X`\xcaT\x86\xc4\x9c\xffbjj\x9b\x06ap\x93(}wd\xa6\xe2\n\x86*wc\xcclI,\x13\xa9\x17\x9a\xbc\xca\x92g\xb3\x87r\xbc\xd2\xf6\xd9\x9f\xd9(\x9f%\x14\xcf\xc12\xc8e-\x8c\xf1ct\xf3\xdcj\xc3\xc0\xdb\x0e\tej\x90\x0e\x86\xe2\x85]\xa4\xf1\xec%\x03\x13\x00\x8e/\x17V\xe3\x1a\xd4\xac\x8b\xb7\xc2\xd7s>\x13L\xca\xbfC\xf1\xfb\x9f\x85\x1d\x9a\xdd\xf3]g_\xf96\xc1n\xd5"\x94\x8f\xf5\rXc(k\x84\x01\x8f q,\xd4\xa3c\xc7\x86(\xec\xf4\x00\xe7\xc7\t\x93\xaa\x86n\x04\xd3\t\xb1\xc0*\x16\x8c\xfa^n\x93T\xcc\xdd6\xb9=\x0b\x1f\x95l\xe2E\x08\x9b1\xb6$\xfc\x94\xf0u\xf2lt\x16\x86\xcc\xae\x1bI\xeb\x1a\x9f*kbY\x83\x851\xdb\xc17\x80?\xbe\t\xc6*\x0f)\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
>>> pk.verify(b"Hello", sig)
True

Upon first use, consider running make test to make sure that the code runs properly on your machine. You should obtain (the test battery for n = 1024 may take a few minutes):

python3 test.py
Test Sig KATs       : OK
Test SamplerZ KATs  : OK         (46.887 msec / execution)

Test battery for n = 64
Test FFT            : OK          (0.907 msec / execution)
Test NTT            : OK          (0.957 msec / execution)
Test NTRUGen        : OK        (260.644 msec / execution)
Test ffNP           : OK          (5.024 msec / execution)
Test Compress       : OK          (0.184 msec / execution)
Test Signature      : OK          (6.266 msec / execution)

Test battery for n = 128
Test FFT            : OK          (1.907 msec / execution)
Test NTT            : OK          (2.137 msec / execution)
Test NTRUGen        : OK        (679.113 msec / execution)
Test ffNP           : OK         (11.589 msec / execution)
Test Compress       : OK           (0.36 msec / execution)
Test Signature      : OK         (11.882 msec / execution)

Test battery for n = 256
Test FFT            : OK          (4.298 msec / execution)
Test NTT            : OK          (5.014 msec / execution)
Test NTRUGen        : OK        (778.603 msec / execution)
Test ffNP           : OK         (26.182 msec / execution)
Test Compress       : OK          (0.758 msec / execution)
Test Signature      : OK         (23.865 msec / execution)

Test battery for n = 512
Test FFT            : OK          (9.455 msec / execution)
Test NTT            : OK          (9.997 msec / execution)
Test NTRUGen        : OK       (3578.415 msec / execution)
Test ffNP           : OK         (59.863 msec / execution)
Test Compress       : OK          (1.486 msec / execution)
Test Signature      : OK         (51.545 msec / execution)

Test battery for n = 1024
Test FFT            : OK         (20.706 msec / execution)
Test NTT            : OK         (22.937 msec / execution)
Test NTRUGen        : OK      (17707.189 msec / execution)
Test ffNP           : OK         (135.42 msec / execution)
Test Compress       : OK          (3.292 msec / execution)
Test Signature      : OK        (102.022 msec / execution)

Profiling

I included a makefile target to performing profiling on the code. If you type make profile on a Linux machine, you should obtain something along these lines:

Make sure you have pyprof2calltree and kcachegrind installed on your machine, or it will not work.

Author

• Thomas Prest (thomas.prest@ens.fr)

Acknowledgements

Thank you to the following people for catching various bugs in the code:

• Dan Middleton
• Nadav Voloch
• Dekel Shiran
• Shlomi Dolev

Disclaimer

This is not reference code. The reference code of Falcon is on https://falcon-sign.info/. This is work in progress. It is not to be considered secure or suitable for production. Also, I do not guarantee portability on Python 2.x. However, this Python code is rather simple, so I hope that it will be helpful to people seeking to implement Falcon.

If you find errors or flaw, I will be very happy if you report them to me at the provided address.

License

MIT