locality_falcon

A complete, web-safe Dart/Flutter implementation of Falcon — the NIST-standardized, lattice-based post-quantum signature scheme — designed to run signing and verification on end-user devices (mobile, desktop, and Flutter Web).

It is a faithful port of the reference implementation tprest/falcon.py: the Dart output is byte-for-byte identical to the reference (same keys, same signatures for the same seed), and the two interoperate — a signature produced by one verifies under the other.

Why Falcon

Small payloads, frequent signing/verification, and tiny public keys (≈900 B for Falcon-512, ≈1.8 KB for Falcon-1024) make Falcon the right fit for messaging-style workloads where keys are shared often. See the design rationale.

Usage

import 'dart:convert';
import 'package:locality_falcon/falcon.dart';

void main() {
  final falcon = Falcon(512);                 // 2..1024, powers of two
  final (sk, vk) = falcon.keygen();           // secret key + verification key (bytes)

  final message = utf8.encode('hello quantum world');
  final signature = falcon.sign(sk, message); // Uint8List, 666 B for Falcon-512

  assert(falcon.verify(vk, message, signature) == true);
  assert(falcon.verify(vk, utf8.encode('tampered'), signature) == false);
}

Reproducible / deterministic mode (e.g. for tests or KATs) — inject a seeded ChaCha20 stream (the same PRNG the reference uses):

final seed = Uint8List(56); // your 56-byte seed
final sig = falcon.sign(sk, message, randombytes: ChaCha20(seed).randombytes);

Parameter sets

Set	n	public key	signature	NIST level
Falcon-512	512	897 B	666 B	1
Falcon-1024	1024	1793 B	1280 B	5

Smaller degrees (2…256) are supported for testing.

Web safety

The whole stack avoids 64-bit-int assumptions so it behaves identically on native and on dart2js/Wasm (where int is a 53-bit double):

SHAKE-256 via PointyCastle (64-bit register emulation).
The Gaussian sampler's FACCT approxExp and all NTRU-solve arithmetic use BigInt where exact integers exceed 2⁵³.
The NTT keeps every intermediate below q² ≈ 1.5·10⁸ < 2⁵³.

Architecture

Single-responsibility modules, none over 300 lines (see lib/sign/ARCHITECTURE.md):

lib/sign/
  complex.dart, fft.dart, phi.dart, constants/   # FFT over R[x]/(x^n+1)
  ntt/ntt.dart                                   # negacyclic NTT mod q
  sampler/gaussian_sampler.dart                  # discrete Gaussian (FACCT)
  rng/{random_bytes,chacha20}.dart               # secure + deterministic RNG
  hash/{shake256,hash_to_point}.dart             # SHAKE-256 XOF, hash-to-point
  encoding/{poly_codec,signature_codec}.dart     # key/signature (de)serialization
  ffsampling/{ldl,ffldl,ff_sampling,ff_tree}.dart# fast Fourier sampling
  ntrugen/{bigint_poly,reduce,ntru_solve,ntru_gen}.dart  # NTRU key generation
  api/{falcon,falcon_keygen,falcon_sign,falcon_verify,...}.dart  # public API

Testing

122 tests, all cross-validated against the Python reference:

flutter test

Component tests check each primitive (SHAKE-256, ChaCha20, samplerZ, NTT, hash-to-point, encoding) byte-for-byte against vectors in test/vectors/; the end-to-end tests check the NTRU equation f·G − g·F = q, byte-identical signature reproduction, cross-verification with the reference, and tamper rejection at n = 8…512.

Regenerate the vectors (requires Python + pycryptodome and a checkout of the reference) with python3 tool/gen_vectors.py.

Security notes

This is a clean, spec-faithful implementation intended for correctness and portability. It has not been independently audited, and the port prioritizes matching the reference over constant-time guarantees — review side-channel resistance before production use. Always sign with the default secure RNG; the seeded ChaCha20 path exists only for reproducible tests.

Credits

Thanks to Shindeyu aka 0xpingu for significant development contributions.

Libraries

demo/falcon_demo
falcon: Falcon — a web-safe Dart implementation of the post-quantum signature scheme (faithful port of the reference tprest/falcon.py).
sign/api/falcon
sign/api/falcon_params
sign/api/secret_key
sign/complex
sign/constants/phi_32
sign/constants/phi_64
sign/constants/phi_128
sign/constants/phi_256
sign/constants/phi_512
sign/constants/phi_1024
sign/constants/phi_2048
sign/encoding/poly_codec: Serialization of Falcon polynomials whose coefficients live in [0, q).
sign/encoding/signature_codec: Compression and decompression of Falcon signature vectors.
sign/falcon_utils
sign/ffsampling/ff_sampling
sign/ffsampling/ff_tree
sign/ffsampling/ffldl
sign/ffsampling/ldl
sign/fft
sign/hash/hash_to_point
sign/hash/shake256
sign/ntrugen/bigint_poly: Exact-integer polynomial arithmetic over Zx/(x^n + 1), used by NTRU key generation. Coefficients grow far beyond 2^53 during ntruSolve, so every value is a BigInt (this is also what keeps the code correct on the web).
sign/ntrugen/ntru_gen
sign/ntrugen/ntru_solve
sign/ntrugen/reduce
sign/ntt/ntt: Negacyclic Number Theoretic Transform modulo q = 12289: arithmetic on polynomials in Z_q[x] / (x^n + 1), n a power of two (2 <= n <= 1024).
sign/phi
sign/poly/rounding
sign/rng/chacha20
sign/rng/random_bytes
sign/sampler/gaussian_sampler