Falcon source files (reference implementation)


README.txt

    1 FALCON IMPLEMENTATION
    2 =====================
    3 
    4 Version: 2019-09-18
    5 
    6 Falcon is a post-quantum signature algorithm, submitted to NIST's
    7 Post-Quantum Cryptography project:
    8 
    9    https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
   10 
   11 Falcon is based on NTRU lattices, used with a hash-and-sign structure
   12 and a Fourier-based sampling method that allows efficient signature
   13 generation and verification, while producing and using relatively
   14 compact signatures and public keys. The official Falcon Web site is:
   15 
   16    https://falcon-sign.info/
   17 
   18 
   19 This implementation is written in C and is configurable at compile-time
   20 through macros which are documented in config.h; each macro is a boolean
   21 option and can be enabled or disabled in config.h and/or as a
   22 command-line parameter to the compiler. Several implementation strategies
   23 are available; however, in all cases, the same API is implemented.
   24 
   25 Main options are the following:
   26 
   27   - FALCON_FPNATIVE and FALCON_FPEMU
   28 
   29     If using FALCON_FPNATIVE, then the C 'double' type is used for all
   30     floating-point operations. This is the default. This requires the
   31     'double' type to implement IEEE-754 semantics, in particular
   32     rounding to the exact precision of the 'binary64' type (i.e. "53
   33     bits"). The Falcon implementation takes special steps to ensure
   34     these properties on most common architectures. When using this
   35     engine, the code _may_ need to call the standard library function
   36     sqrt() (depending on the local architecture), which may in turn
   37     require linking with a specific library (e.g. adding '-lm' to the
   38     link command on Unix-like systems).
   39 
   40     FALCON_FPEMU does not use the C 'double' type, but instead works
   41     over only 64-bit integers and embeds its own emulation of IEEE-754
   42     operations. This is slower but portable, since it will work on any
   43     machine with a C99-compliant compiler.
   44 
   45   - FALCON_AVX2 and FALCON_FMA
   46 
   47     FALCON_AVX2, when enabled, activates the use of AVX2 compiler
   48     intrinsics. This works only on x86 CPU that offer AVX2 opcodes.
   49     Use of AVX2 improves performance. FALCON_AVX2 has no effect if
   50     FALCON_FPEMU is used.
   51 
   52     FALCON_FMA further enables the use for FMA ("fused multiply-add")
   53     compiler intrinsics for an extra boost to performance. This
   54     setting is ignored unless FALCON_FPNATIVE and FALCON_AVX2 are
   55     both used. Occasionally (but rarely), use of FALCON_FMA will
   56     change the keys and/or signatures generated from a given random
   57     seed, impacting reproducibility of test vectors; however, this
   58     has no bearing on the security of normal usage.
   59 
   60   - FALCON_ASM_CORTEXM4
   61 
   62     When enabled, inline assembly routines for FP emulation and SHAKE256
   63     will be used. This will work only on the ARM Cortex M3, M4 and
   64     compatible CPU. This assembly code is constant-time on the M4, and
   65     about twice faster than the generic C code used by FALCON_FPEMU.
   66 
   67 
   68 USAGE
   69 -----
   70 
   71 See the Makefile for compilation flags, and config.h for configurable
   72 options. Type 'make' to compile: this will generate two binaries called
   73 'test_falcon' and 'speed'. 'test_falcon' runs unit tests to verify that
   74 everything computes the expected values. 'speed' runs performance
   75 benchmarks on Falcon-256, Falcon-512 and Falcon-1024 (Falcon-256 is a
   76 reduced version that is faster and smaller than Falcon-512, but provides
   77 only reduced security, and not part of the "official" Falcon).
   78 
   79 Applications that want to use Falcon normally work on the external API,
   80 which is documented in the "falcon.h" file. This is the only file that
   81 an external application needs to use.
   82 
   83 For research purposes, the inner API is documented in "inner.h". This
   84 API gives access to many internal functions that perform some elementary
   85 operations used in Falcon. That API also has some non-obvious
   86 requirements, such as alignment on temporary buffers, or the need to
   87 adjust FPU precision on 32-bit x86 systems.
   88 
   89 
   90 LICENSE
   91 -------
   92 
   93 This code is provided under the MIT license:
   94 
   95 ==========================(LICENSE BEGIN)============================
   96 Copyright (c) 2017-2019  Falcon Project
   97 
   98 Permission is hereby granted, free of charge, to any person obtaining
   99 a copy of this software and associated documentation files (the
  100 "Software"), to deal in the Software without restriction, including
  101 without limitation the rights to use, copy, modify, merge, publish,
  102 distribute, sublicense, and/or sell copies of the Software, and to
  103 permit persons to whom the Software is furnished to do so, subject to
  104 the following conditions:
  105 
  106 The above copyright notice and this permission notice shall be
  107 included in all copies or substantial portions of the Software.
  108 
  109 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  110 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  111 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  112 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  113 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  114 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  115 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  116 ===========================(LICENSE END)=============================
  117 
  118 The code was written by Thomas Pornin <thomas.pornin@nccgroup.com>, to
  119 whom questions may be addressed. I'll endeavour to respond more or less
  120 promptly.