Falcon source files (reference implementation)


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