falcon.h
1 /*
2 * External Falcon API.
3 *
4 * ==========================(LICENSE BEGIN)============================
5 *
6 * Copyright (c) 2017-2019 Falcon Project
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining
9 * a copy of this software and associated documentation files (the
10 * "Software"), to deal in the Software without restriction, including
11 * without limitation the rights to use, copy, modify, merge, publish,
12 * distribute, sublicense, and/or sell copies of the Software, and to
13 * permit persons to whom the Software is furnished to do so, subject to
14 * the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
23 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 *
27 * ===========================(LICENSE END)=============================
28 *
29 * @author Thomas Pornin <thomas.pornin@nccgroup.com>
30 */
31
32 #ifndef FALCON_H__
33 #define FALCON_H__
34
35 #include <stddef.h>
36 #include <stdint.h>
37
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41
42 /* ==================================================================== */
43 /*
44 * Falcon API Notes
45 * ----------------
46 *
47 *
48 * FALCON DEGREE
49 *
50 * Falcon is parameterized by a degree, which is a power of two. Formally,
51 * two values are possible: 512 and 1024 (for Falcon-512 and Falcon-1024,
52 * respectively). This implementation also supports lower degrees, from
53 * 2 to 256; these reduced variants do not provide adequate security and
54 * should be used for research purposes only.
55 *
56 * In all functions and macros defined below, the degree is provided
57 * logarithmically as the 'logn' parameter: logn ranges from 1 to 10,
58 * and represents the degree 2^logn.
59 *
60 *
61 * ERROR REPORTING
62 *
63 * All functions that may fail for some reason return an 'int' value. A
64 * returned value of zero is a success; all error conditions are
65 * reported as an error code. Error codes are negative. Macros are
66 * defined for some error codes; in the interest of forward
67 * compatiblity, applications that use this implementation should be
68 * prepared to receive other error codes not listed in the macros below.
69 *
70 *
71 * TEMPORARY BUFFERS
72 *
73 * Many functions expect temporary areas, provided as the parameter
74 * 'tmp'. The caller is responsible for allocating these areas with the
75 * proper size; the FALCON_TMPSIZE_* macros evaluate to constant
76 * expressions that yield the proper size (in bytes) and can be used to
77 * allocate the temporaries on the stack or elsewhere. There are no
78 * alignment requirements on temporaries (the functions handle alignment
79 * internally).
80 *
81 * The caller is responsible for clearing temporary buffer contents,
82 * if such memory scrubbing is deemed relevant in the context where this
83 * implementation is used.
84 *
85 * The same temporary buffer can be reused for several operations,
86 * possibly distinct from each other. For all degrees from 8 to 1024
87 * (logn = 3 to 10), the following sizes are in ascending order:
88 *
89 * FALCON_TMPSIZE_MAKEPUB
90 * FALCON_TMPSIZE_VERIFY
91 * FALCON_TMPSIZE_KEYGEN
92 * FALCON_TMPSIZE_SIGNTREE
93 * FALCON_TMPSIZE_EXPANDPRIV
94 * FALCON_TMPSIZE_SIGNDYN
95 *
96 * i.e. a temporary buffer large enough for computing signatures with
97 * an expanded key ("SIGNTREE") will also be large enough for a
98 * key pair generation ("KEYGEN"). For logn = 1 or 2, the same order
99 * holds, except that the KEYGEN buffer is larger.
100 *
101 * Here are the actual values for the temporary buffer sizes (in bytes):
102 *
103 * degree mkpub verify keygen signtree expkey signdyn
104 * 2 13 17 285 107 111 163
105 * 4 25 33 291 207 215 319
106 * 8 49 65 303 407 423 631
107 * 16 97 129 503 807 839 1255
108 * 32 193 257 999 1607 1671 2503
109 * 64 385 513 1991 3207 3335 4999
110 * 128 769 1025 3975 6407 6663 9991
111 * 256 1537 2049 7943 12807 13319 19975
112 * 512 3073 4097 15879 25607 26631 39943
113 * 1024 6145 8193 31751 51207 53255 79879
114 *
115 * Take care that the "expkey" column here qualifies the temporary buffer
116 * for the key expansion process, but NOT the expanded key itself (which
117 * has size FALCON_EXPANDEDKEY_SIZE(logn) and is larger than that).
118 *
119 *
120 * FORMATS
121 *
122 * Public and private keys are exchanged as serialized sequences of
123 * bytes. Their respective sizes are fixed (for a given degree) and the
124 * FALCON_PRIVKEY_SIZE and FALCON_PUBKEY_SIZE macros return that value
125 * as constant expressions.
126 *
127 * There are three formats for signatures:
128 *
129 * - COMPRESSED: this is the default format, which yields the shortest
130 * signatures on average. However, the size is variable (see below)
131 * though within a limited range.
132 *
133 * - PADDED: this is the compressed format, but with extra padding bytes
134 * to obtain a fixed size known at compile-time. The size depends only
135 * on the degree; the FALCON_SIG_PADDED_SIZE macro computes it. The
136 * signature process enforces that size by restarting the process
137 * until an appropriate size is obtained (such restarts are uncommon
138 * enough that the computational overhead is negligible).
139 *
140 * - CT: this is a fixed-size format, which furthermore allows
141 * constant-time processing with regard to the signature value and
142 * message data. This is meant for uncommon situations in which
143 * the signed data is secret but of low entropy, and the public key
144 * is not actually public. The CT format is larger than the
145 * COMPRESSED and PADDED formats.
146 *
147 * The signature format is selected by the 'sig_type' parameter to
148 * the signature generation and verification functions.
149 *
150 * Actual signature size has been measured over 10000 signatures for each
151 * degree (100 random keys, 100 signatures per key):
152 *
153 * degree ct padded compressed (with std. dev) comp_max
154 * 2 44 44 44.00 (+/- 0.00) 44
155 * 4 47 47 46.03 (+/- 0.17) 47
156 * 8 52 52 50.97 (+/- 0.26) 52
157 * 16 65 63 60.45 (+/- 0.52) 64
158 * 32 89 82 79.53 (+/- 0.68) 86
159 * 64 137 122 117.69 (+/- 0.94) 130
160 * 128 233 200 193.96 (+/- 1.30) 219
161 * 256 425 356 346.53 (+/- 1.84) 397
162 * 512 809 666 651.59 (+/- 2.55) 752
163 * 1024 1577 1280 1261.06 (+/- 3.57) 1462
164 *
165 * with:
166 * degree = Falcon degree = 2^logn
167 * ct = FALCON_SIG_CT_SIZE(logn) (size of a CT signature)
168 * padded = FALCON_SIG_PADDED_SIZE(logn) (size of a PADDED signature)
169 * compressed = measured average length of a COMPRESSED signature
170 * v_max = FALCON_SIG_COMPRESSED_MAXSIZE(logn) (maximum theoretical
171 * size of a COMPRESSED signature)
172 * All lengths are in bytes.
173 *
174 * A private key, in its encoded format, can be used as parameter to
175 * falcon_sign_dyn(). An "expanded private key" is computed with
176 * falcon_expand_privkey(), to be used with falcon_sign_tree(). The
177 * expanded private key is much larger than the encoded private key, and
178 * its format is not portable. Its size (in bytes) is provided by
179 * FALCON_EXPANDEDKEY_SIZE. There are no specific alignment requirements
180 * on expanded keys, except that the alignment of a given expanded key
181 * must not change (i.e. if an expanded key is moved from address addr1
182 * to address addr2, then it must hold that addr1 = addr2 mod 8).
183 * Expanded private keys are meant to be used when several signatures are
184 * to be computed with the same private key: amortized cost per signature
185 * is about halved when using expanded private keys (for short messages,
186 * and depending on underlying architecture and implementation choices).
187 *
188 *
189 * USE OF SHAKE256
190 *
191 * SHAKE256 is used in two places:
192 *
193 * - As a PRNG: all functions that require randomness (key pair
194 * generation, signature generation) receive as parameter a SHAKE256
195 * object, in output mode, from which pseudorandom data is obtained.
196 *
197 * A SHAKE256 instance, to be used as a RNG, can be initialized
198 * from an explicit 48-byte seed, or from an OS-provided RNG. Using
199 * an explicit seed is meant for reproducibility of test vectors,
200 * or to be used in cases where no OS-provided RNG is available and
201 * supported.
202 *
203 * - As the hashing mechanism for the message which should be signed.
204 * The streamed signature API exposes that SHAKE256 object, since
205 * the caller then performs the hashing externally.
206 */
207
208 /* ==================================================================== */
209 /*
210 * Error codes.
211 *
212 * Most functions in this API that may fail for some reason return an
213 * 'int' value which will be 0 on success, or a negative error code.
214 * The macros below define the error codes. In the interest of forward
215 * compatibility, callers should be prepared to receive additional error
216 * codes not included in the list below.
217 */
218
219 /*
220 * FALCON_ERR_RANDOM is returned when the library tries to use an
221 * OS-provided RNG, but either none is supported, or that RNG fails.
222 */
223 #define FALCON_ERR_RANDOM -1
224
225 /*
226 * FALCON_ERR_SIZE is returned when a buffer has been provided to
227 * the library but is too small to receive the intended value.
228 */
229 #define FALCON_ERR_SIZE -2
230
231 /*
232 * FALCON_ERR_FORMAT is returned when decoding of an external object
233 * (public key, private key, signature) fails.
234 */
235 #define FALCON_ERR_FORMAT -3
236
237 /*
238 * FALCON_ERR_BADSIG is returned when verifying a signature, the signature
239 * is validly encoded, but its value does not match the provided message
240 * and public key.
241 */
242 #define FALCON_ERR_BADSIG -4
243
244 /*
245 * FALCON_ERR_BADARG is returned when a provided parameter is not in
246 * a valid range.
247 */
248 #define FALCON_ERR_BADARG -5
249
250 /*
251 * FALCON_ERR_INTERNAL is returned when some internal computation failed.
252 */
253 #define FALCON_ERR_INTERNAL -6
254
255 /* ==================================================================== */
256 /*
257 * Signature formats.
258 */
259
260 /*
261 * Variable-size signature. This format produces the most compact
262 * signatures on average, but the signature size may vary depending
263 * on private key, signed data, and random seed.
264 */
265 #define FALCON_SIG_COMPRESSED 1
266
267 /*
268 * Fixed-size signature. This format produces is equivalent to the
269 * "compressed" format, but includes padding to a known fixed size
270 * (specified by FALCON_SIG_PADDED_SIZE). With this format, the
271 * signature generation loops until an appropriate signature size is
272 * achieved (such looping is uncommon) and adds the padding bytes;
273 * the verification functions check the presence and contents of the
274 * padding bytes.
275 */
276 #define FALCON_SIG_PADDED 2
277
278 /*
279 * Fixed-size format amenable to constant-time implementation. All formats
280 * allow constant-time code with regard to the private key; the 'CT'
281 * format of signature also prevents information about the signature value
282 * and the signed data hash to leak through timing-based side channels
283 * (this feature is rarely needed).
284 */
285 #define FALCON_SIG_CT 3
286
287 /* ==================================================================== */
288 /*
289 * Sizes.
290 *
291 * The sizes are expressed in bytes. Each size depends on the Falcon
292 * degree, which is provided logarithmically: use logn=9 for Falcon-512,
293 * logn=10 for Falcon-1024. Valid values for logn range from 1 to 10
294 * (values 1 to 8 correspond to reduced variants of Falcon that do not
295 * provided adequate security and are meant for research purposes only).
296 *
297 * The sizes are provided as macros that evaluate to constant
298 * expressions, as long as the 'logn' parameter is itself a constant
299 * expression. Moreover, all sizes are monotonic (for each size category,
300 * increasing logn cannot result in a shorter length).
301 *
302 * Note: each macro may evaluate its argument 'logn' several times.
303 */
304
305 /*
306 * Private key size (in bytes). The size is exact.
307 */
308 #define FALCON_PRIVKEY_SIZE(logn) \
309 (((logn) <= 3 \
310 ? (3u << (logn)) \
311 : ((10u - ((logn) >> 1)) << ((logn) - 2)) + (1 << (logn))) \
312 + 1)
313
314 /*
315 * Public key size (in bytes). The size is exact.
316 */
317 #define FALCON_PUBKEY_SIZE(logn) \
318 (((logn) <= 1 \
319 ? 4u \
320 : (7u << ((logn) - 2))) \
321 + 1)
322
323 /*
324 * Maximum signature size (in bytes) when using the COMPRESSED format.
325 * In practice, the signature will be shorter.
326 */
327 #define FALCON_SIG_COMPRESSED_MAXSIZE(logn) \
328 (((((11u << (logn)) + (101u >> (10 - (logn)))) \
329 + 7) >> 3) + 41)
330
331 /*
332 * Signature size (in bytes) when using the PADDED format. The size
333 * is exact.
334 */
335 #define FALCON_SIG_PADDED_SIZE(logn) \
336 (44u + 3 * (256u >> (10 - (logn))) + 2 * (128u >> (10 - (logn))) \
337 + 3 * (64u >> (10 - (logn))) + 2 * (16u >> (10 - (logn))) \
338 - 2 * (2u >> (10 - (logn))) - 8 * (1u >> (10 - (logn))))
339
340 /*
341 * Signature size (in bytes) when using the CT format. The size is exact.
342 */
343 #define FALCON_SIG_CT_SIZE(logn) \
344 ((3u << ((logn) - 1)) - ((logn) == 3) + 41)
345
346 /*
347 * Temporary buffer size for key pair generation.
348 */
349 #define FALCON_TMPSIZE_KEYGEN(logn) \
350 (((logn) <= 3 ? 272u : (28u << (logn))) + (3u << (logn)) + 7)
351
352 /*
353 * Temporary buffer size for computing the pubic key from the private key.
354 */
355 #define FALCON_TMPSIZE_MAKEPUB(logn) \
356 ((6u << (logn)) + 1)
357
358 /*
359 * Temporary buffer size for generating a signature ("dynamic" variant).
360 */
361 #define FALCON_TMPSIZE_SIGNDYN(logn) \
362 ((78u << (logn)) + 7)
363
364 /*
365 * Temporary buffer size for generating a signature ("tree" variant, with
366 * an expanded key).
367 */
368 #define FALCON_TMPSIZE_SIGNTREE(logn) \
369 ((50u << (logn)) + 7)
370
371 /*
372 * Temporary buffer size for expanding a private key.
373 */
374 #define FALCON_TMPSIZE_EXPANDPRIV(logn) \
375 ((52u << (logn)) + 7)
376
377 /*
378 * Size of an expanded private key.
379 */
380 #define FALCON_EXPANDEDKEY_SIZE(logn) \
381 (((8u * (logn) + 40) << (logn)) + 8)
382
383 /*
384 * Temporary buffer size for verifying a signature.
385 */
386 #define FALCON_TMPSIZE_VERIFY(logn) \
387 ((8u << (logn)) + 1)
388
389 /* ==================================================================== */
390 /*
391 * SHAKE256.
392 */
393
394 /*
395 * Context for a SHAKE256 computation. Contents are opaque.
396 * Contents are pure data with no pointer; they need not be released
397 * explicitly and don't reference any other allocated resource. The
398 * caller is responsible for allocating the context structure itself,
399 * typically on the stack.
400 */
401 typedef struct {
402 uint64_t opaque_contents[26];
403 } shake256_context;
404
405 /*
406 * Initialize a SHAKE256 context to its initial state. The state is
407 * then ready to receive data (with shake256_inject()).
408 */
409 void shake256_init(shake256_context *sc);
410
411 /*
412 * Inject some data bytes into the SHAKE256 context ("absorb" operation).
413 * This function can be called several times, to inject several chunks
414 * of data of arbitrary length.
415 */
416 void shake256_inject(shake256_context *sc, const void *data, size_t len);
417
418 /*
419 * Flip the SHAKE256 state to output mode. After this call, shake256_inject()
420 * can no longer be called on the context, but shake256_extract() can be
421 * called.
422 *
423 * Flipping is one-way; a given context can be converted back to input
424 * mode only by initializing it again, which forgets all previously
425 * injected data.
426 */
427 void shake256_flip(shake256_context *sc);
428
429 /*
430 * Extract bytes from the SHAKE256 context ("squeeze" operation). The
431 * context must have been flipped to output mode (with shake256_flip()).
432 * Arbitrary amounts of data can be extracted, in one or several calls
433 * to this function.
434 */
435 void shake256_extract(shake256_context *sc, void *out, size_t len);
436
437 /*
438 * Initialize a SHAKE256 context as a PRNG from the provided seed.
439 * This initializes the context, injects the seed, then flips the context
440 * to output mode to make it ready to produce bytes.
441 */
442 void shake256_init_prng_from_seed(shake256_context *sc,
443 const void *seed, size_t seed_len);
444
445 /*
446 * Initialize a SHAKE256 context as a PRNG, using an initial seed from
447 * the OS-provided RNG. If there is no known/supported OS-provided RNG,
448 * or if that RNG fails, then the context is not properly initialized
449 * and FALCON_ERR_RANDOM is returned.
450 *
451 * Returned value: 0 on success, or a negative error code.
452 */
453 int shake256_init_prng_from_system(shake256_context *sc);
454
455 /* ==================================================================== */
456 /*
457 * Key pair generation.
458 */
459
460 /*
461 * Generate a new keypair.
462 *
463 * The logarithm of the Falcon degree (logn) must be in the 1 to 10
464 * range; values 1 to 8 correspond to reduced versions of Falcon that do
465 * not provide adequate security and are meant for research purposes
466 * only.
467 *
468 * The source of randomness is the provided SHAKE256 context *rng, which
469 * must have been already initialized, seeded, and set to output mode (see
470 * shake256_init_prng_from_seed() and shake256_init_prng_from_system()).
471 *
472 * The new private key is written in the buffer pointed to by privkey.
473 * The size of that buffer must be specified in privkey_len; if that
474 * size is too low, then this function fails with FALCON_ERR_SIZE. The
475 * actual private key length can be obtained from the FALCON_PRIVKEY_SIZE()
476 * macro.
477 *
478 * If pubkey is not NULL, then the new public key is written in the buffer
479 * pointed to by pubkey. The size of that buffer must be specified in
480 * pubkey_len; if that size is too low, then this function fails with
481 * FALCON_ERR_SIZE. The actual public key length can be obtained from the
482 * FALCON_PUBKEY_SIZE() macro.
483 *
484 * If pubkey is NULL then pubkey_len is ignored; the private key will
485 * still be generated and written to privkey[], but the public key
486 * won't be written anywhere. The public key can be later on recomputed
487 * from the private key with falcon_make_public().
488 *
489 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
490 * MUST be at least FALCON_TMPSIZE_KEYGEN(logn) bytes.
491 *
492 * Returned value: 0 on success, or a negative error code.
493 */
494 int falcon_keygen_make(
495 shake256_context *rng,
496 unsigned logn,
497 void *privkey, size_t privkey_len,
498 void *pubkey, size_t pubkey_len,
499 void *tmp, size_t tmp_len);
500
501 /*
502 * Recompute the public key from the private key.
503 *
504 * The private key is provided encoded. This function decodes the
505 * private key and verifies that its length (in bytes) is exactly
506 * the provided value privkey_len (trailing extra bytes are not
507 * tolerated).
508 *
509 * The public key is written in the buffer pointed to by pubkey. The
510 * size (in bytes) of the pubkey buffer must be provided in pubkey_len;
511 * if it is too short for the public key, then FALCON_ERR_SIZE is
512 * returned. The actual public key size can be obtained from the
513 * FALCON_PUBKEY_SIZE() macro.
514 *
515 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
516 * MUST be at least FALCON_TMPSIZE_MAKEPUB(logn) bytes.
517 *
518 * Returned value: 0 on success, or a negative error code.
519 */
520 int falcon_make_public(
521 void *pubkey, size_t pubkey_len,
522 const void *privkey, size_t privkey_len,
523 void *tmp, size_t tmp_len);
524
525 /*
526 * Get the Falcon degree from an encoded private key, public key or
527 * signature. Returned value is the logarithm of the degree (1 to 10),
528 * or a negative error code.
529 */
530 int falcon_get_logn(void *obj, size_t len);
531
532 /* ==================================================================== */
533 /*
534 * Signature generation.
535 */
536
537 /*
538 * Sign the data provided in buffer data[] (of length data_len bytes),
539 * using the private key held in privkey[] (of length privkey_len bytes).
540 *
541 * The source of randomness is the provided SHAKE256 context *rng, which
542 * must have been already initialized, seeded, and set to output mode (see
543 * shake256_init_prng_from_seed() and shake256_init_prng_from_system()).
544 *
545 * The signature is written in sig[]. The caller must set *sig_len to
546 * the maximum size of sig[]; if the signature computation is
547 * successful, then *sig_len will be set to the actual length of the
548 * signature. The signature length depends on the signature type,
549 * which is specified with the sig_type parameter to one of the three
550 * defined values FALCON_SIG_COMPRESSED, FALCON_SIG_PADDED or
551 * FALCON_SIG_CT; for the last two of these, the signature length is
552 * fixed (for a given Falcon degree).
553 *
554 * Regardless of the signature type, the process is constant-time with
555 * regard to the private key. When sig_type is FALCON_SIG_CT, it is also
556 * constant-time with regard to the signature value and the message data,
557 * i.e. no information on the signature and the message may be inferred
558 * from timing-related side channels.
559 *
560 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
561 * MUST be at least FALCON_TMPSIZE_SIGNDYN(logn) bytes.
562 *
563 * Returned value: 0 on success, or a negative error code.
564 */
565 int falcon_sign_dyn(shake256_context *rng,
566 void *sig, size_t *sig_len, int sig_type,
567 const void *privkey, size_t privkey_len,
568 const void *data, size_t data_len,
569 void *tmp, size_t tmp_len);
570
571 /*
572 * Expand a private key. The provided Falcon private key (privkey, of
573 * size privkey_len bytes) is decoded and expanded into expanded_key[].
574 *
575 * The expanded_key[] buffer has size expanded_key_len, which MUST be at
576 * least FALCON_EXPANDEDKEY_SIZE(logn) bytes (where 'logn' qualifies the
577 * Falcon degree encoded in the private key and can be obtained with
578 * falcon_get_logn()). Expanded key contents have an internal,
579 * implementation-specific format. Expanded keys may be moved in RAM
580 * only if their 8-byte alignment remains unchanged.
581 *
582 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
583 * MUST be at least FALCON_TMPSIZE_EXPANDPRIV(logn) bytes.
584 *
585 * Returned value: 0 on success, or a negative error code.
586 */
587 int falcon_expand_privkey(void *expanded_key, size_t expanded_key_len,
588 const void *privkey, size_t privkey_len,
589 void *tmp, size_t tmp_len);
590
591 /*
592 * Sign the data provided in buffer data[] (of length data_len bytes),
593 * using the expanded private key held in expanded_key[], as generated
594 * by falcon_expand_privkey().
595 *
596 * The source of randomness is the provided SHAKE256 context *rng, which
597 * must have been already initialized, seeded, and set to output mode (see
598 * shake256_init_prng_from_seed() and shake256_init_prng_from_system()).
599 *
600 * The signature is written in sig[]. The caller must set *sig_len to
601 * the maximum size of sig[]; if the signature computation is
602 * successful, then *sig_len will be set to the actual length of the
603 * signature. The signature length depends on the signature type,
604 * which is specified with the sig_type parameter to one of the three
605 * defined values FALCON_SIG_COMPRESSED, FALCON_SIG_PADDED or
606 * FALCON_SIG_CT; for the last two of these, the signature length is
607 * fixed (for a given Falcon degree).
608 *
609 * Regardless of the signature type, the process is constant-time with
610 * regard to the private key. When sig_type is FALCON_SIG_CT, it is also
611 * constant-time with regard to the signature value and the message data,
612 * i.e. no information on the signature and the message may be inferred
613 * from timing-related side channels.
614 *
615 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
616 * MUST be at least FALCON_TMPSIZE_SIGNTREE(logn) bytes.
617 *
618 * Returned value: 0 on success, or a negative error code.
619 */
620 int falcon_sign_tree(shake256_context *rng,
621 void *sig, size_t *sig_len, int sig_type,
622 const void *expanded_key,
623 const void *data, size_t data_len,
624 void *tmp, size_t tmp_len);
625
626 /* ==================================================================== */
627 /*
628 * Signature generation, streamed API.
629 *
630 * In the streamed API, the caller performs the data hashing externally.
631 * An initialization function (falcon_sign_start()) is first called; it
632 * generates and returns a random 40-byte nonce value; it also initializes
633 * a SHAKE256 context and injects the nonce value in that context. The
634 * caller must then inject the data to sign in the SHAKE256 context, and
635 * finally call falcon_sign_dyn_finish() or falcon_sign_tree_finish() to
636 * finalize the signature generation.
637 */
638
639 /*
640 * Start a signature generation context.
641 *
642 * A 40-byte nonce is generated and written in nonce[]. The *hash_data
643 * context is also initialized, and the nonce is injected in that context.
644 *
645 * The source of randomness is the provided SHAKE256 context *rng, which
646 * must have been already initialized, seeded, and set to output mode (see
647 * shake256_init_prng_from_seed() and shake256_init_prng_from_system()).
648 *
649 * Returned value: 0 on success, or a negative error code.
650 */
651 int falcon_sign_start(shake256_context *rng,
652 void *nonce,
653 shake256_context *hash_data);
654
655 /*
656 * Finish a signature generation operation, using the private key held
657 * in privkey[] (of length privkey_len bytes). The hashed nonce + message
658 * is provided as the SHAKE256 context *hash_data, which must still be
659 * in input mode (i.e. not yet flipped to output mode). That context is
660 * modified in the process.
661 *
662 * The nonce value (which was used at the start of the hashing process,
663 * usually as part of a falcon_sign_start() call) must be provided again,
664 * because it is encoded into the signature. The nonce length is 40 bytes.
665 *
666 * The source of randomness is the provided SHAKE256 context *rng, which
667 * must have been already initialized, seeded, and set to output mode (see
668 * shake256_init_prng_from_seed() and shake256_init_prng_from_system()).
669 *
670 * The signature is written in sig[]. The caller must set *sig_len to
671 * the maximum size of sig[]; if the signature computation is
672 * successful, then *sig_len will be set to the actual length of the
673 * signature. The signature length depends on the signature type,
674 * which is specified with the sig_type parameter to one of the three
675 * defined values FALCON_SIG_COMPRESSED, FALCON_SIG_PADDED or
676 * FALCON_SIG_CT; for the last two of these, the signature length is
677 * fixed (for a given Falcon degree).
678 *
679 * Regardless of the signature type, the process is constant-time with
680 * regard to the private key. When sig_type is FALCON_SIG_CT, it is also
681 * constant-time with regard to the signature value and the message data,
682 * i.e. no information on the signature and the message may be inferred
683 * from timing-related side channels.
684 *
685 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
686 * MUST be at least FALCON_TMPSIZE_SIGNDYN(logn) bytes.
687 *
688 * Returned value: 0 on success, or a negative error code.
689 */
690 int falcon_sign_dyn_finish(shake256_context *rng,
691 void *sig, size_t *sig_len, int sig_type,
692 const void *privkey, size_t privkey_len,
693 shake256_context *hash_data, const void *nonce,
694 void *tmp, size_t tmp_len);
695
696 /*
697 * Finish a signature generation operation, using the expanded private
698 * key held in expanded_key[] (as obtained from
699 * falcon_expand_privkey()). The hashed nonce + message is provided as
700 * the SHAKE256 context *hash_data, which must still be in input mode
701 * (i.e. not yet flipped to output mode). That context is modified in
702 * the process.
703 *
704 * The nonce value (which was used at the start of the hashing process,
705 * usually as part of a falcon_sign_start() call) must be provided again,
706 * because it is encoded into the signature. The nonce length is 40 bytes.
707 *
708 * The source of randomness is the provided SHAKE256 context *rng, which
709 * must have been already initialized, seeded, and set to output mode (see
710 * shake256_init_prng_from_seed() and shake256_init_prng_from_system()).
711 *
712 * The signature is written in sig[]. The caller must set *sig_len to
713 * the maximum size of sig[]; if the signature computation is
714 * successful, then *sig_len will be set to the actual length of the
715 * signature. The signature length depends on the signature type,
716 * which is specified with the sig_type parameter to one of the three
717 * defined values FALCON_SIG_COMPRESSED, FALCON_SIG_PADDED or
718 * FALCON_SIG_CT; for the last two of these, the signature length is
719 * fixed (for a given Falcon degree).
720 *
721 * Regardless of the signature type, the process is constant-time with
722 * regard to the private key. When sig_type is FALCON_SIG_CT, it is also
723 * constant-time with regard to the signature value and the message data,
724 * i.e. no information on the signature and the message may be inferred
725 * from timing-related side channels.
726 *
727 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
728 * MUST be at least FALCON_TMPSIZE_SIGNTREE(logn) bytes.
729 *
730 * Returned value: 0 on success, or a negative error code.
731 */
732 int falcon_sign_tree_finish(shake256_context *rng,
733 void *sig, size_t *sig_len, int sig_type,
734 const void *expanded_key,
735 shake256_context *hash_data, const void *nonce,
736 void *tmp, size_t tmp_len);
737
738 /* ==================================================================== */
739 /*
740 * Signature verification.
741 */
742
743 /*
744 * Verify the signature sig[] (of length sig_len bytes) with regards to
745 * the provided public key pubkey[] (of length pubkey_len bytes) and the
746 * message data[] (of length data_len bytes).
747 *
748 * The sig_type parameter must be zero, or one of FALCON_SIG_COMPRESSED,
749 * FALCON_SIG_PADDED or FALCON_SIG_CT. The function verifies that
750 * the provided signature has the correct format. If sig_type is zero,
751 * then the signature format is inferred from the signature header byte;
752 * note that in that case, the signature is malleable (since a signature
753 * value can be transcoded to other formats).
754 *
755 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
756 * MUST be at least FALCON_TMPSIZE_VERIFY(logn) bytes.
757 *
758 * Returned value: 0 on success, or a negative error code.
759 */
760 int falcon_verify(const void *sig, size_t sig_len, int sig_type,
761 const void *pubkey, size_t pubkey_len,
762 const void *data, size_t data_len,
763 void *tmp, size_t tmp_len);
764
765 /*
766 * Start a streamed signature verification. The provided SHAKE256 context
767 * *hash_data is initialized, and the nonce value (extracted from the
768 * signature) is injected into it. The caller shall then inject the
769 * message data into the SHAKE256 context, and finally call
770 * falcon_verify_finish().
771 *
772 * Returned value: 0 on success, or a negative error code.
773 */
774 int falcon_verify_start(shake256_context *hash_data,
775 const void *sig, size_t sig_len);
776
777 /*
778 * Finish a streamed signature verification. The signature sig[] (of
779 * length sig_len bytes) is verified against the provided public key
780 * pubkey[] (of length pubkey_len bytes) and the hashed message. The
781 * hashed message is provided as a SHAKE256 context *hash_data;
782 * that context must have received the nonce and the message itself
783 * (usually, the context is initialized and the nonce injected as
784 * part of a falcon_verify_start() call), and still be in input
785 * mode (not yet flipped to output mode). *hash_data is modified by
786 * the verification process.
787 *
788 * The sig_type parameter must be zero, or one of FALCON_SIG_COMPRESSED,
789 * FALCON_SIG_PADDED or FALCON_SIG_CT. The function verifies that
790 * the provided signature has the correct format. If sig_type is zero,
791 * then the signature format is inferred from the signature header byte;
792 * note that in that case, the signature is malleable (since a signature
793 * value can be transcoded to other formats).
794 *
795 * The tmp[] buffer is used to hold temporary values. Its size tmp_len
796 * MUST be at least FALCON_TMPSIZE_VERIFY(logn) bytes.
797 *
798 * Returned value: 0 on success, or a negative error code.
799 */
800 int falcon_verify_finish(const void *sig, size_t sig_len, int sig_type,
801 const void *pubkey, size_t pubkey_len,
802 shake256_context *hash_data,
803 void *tmp, size_t tmp_len);
804
805 /* ==================================================================== */
806
807 #ifdef __cplusplus
808 }
809 #endif
810
811 #endif