A post-quantum signature that fits a microcontroller

Mitaka is a variant of Falcon, the lattice signature scheme standardised as FN-DSA, with a considerably simpler signing procedure that can be parallelised while keeping Falcon's efficiency advantage. It offers two ways to sign: a default one relying on floating-point arithmetic, and an alternative called MitakaZ that avoids floating point at the cost of more Gaussian samples. MitakaZ is the more portable of the two and, until now, had not been implemented in practice.

Four authors at the Institute for Advanced Study at Tsinghua University have published that implementation. They optimise the MitakaZ Gaussian sampler to suit fixed-point arithmetic, replacing the wide integral Gram root decomposition it used with a fixed-point square Cholesky decomposition, which substantially reduces the cost of integer Gaussian sampling.

The analysis is stricter than usual for an implementation paper. The authors prove bounds on intermediate values and representation errors without empirical assumptions about their magnitudes, and their distributional analysis models each integer Gaussian call as exact at its represented inputs. That matters for a signature scheme, where an implementation detail visible through the output distribution is a security problem rather than a performance one.

The measurements come from two very different machines. On an Intel Core i7-1360P the native AVX2 implementation produces signatures in an average of 361 kilocycles for Mitaka-512 and 707 kilocycles for Mitaka-1024, measured with Linux hardware performance events. On an ARM Cortex-M4F STM32F411 — a microcontroller — the same operations cost 4.0 and 7.8 megacycles. The work is a preprint, received and approved on 17 October.