ATMACA: Lattice-Based Threshold Signing for FALCON

Abstract: In this talk, we will introduce ATMACA, an efficient post-quantum threshold signature protocol for the FFT (fast Fourier transform) over NTRU-Lattice-Based Digital Signature Algorithm (FN-DSA/FALCON). The main difficulty of threshold signing for FALCON in multi-party computation (MPC) is that FALCON's sampler draws its Gaussian samples sequentially. Therefore, the number of rounds grows linearly with the ring degree. ATMACA evaluates the hybrid sampler used by Mitaka, a FALCON variant, with annular NTRU trapdoor generation (ANTRAG) keys. In this setting, only two steps are sequential, and the samples within each step are drawn in parallel. The signatures still pass the unchanged FALCON verifier. ATMACA tolerates a dishonest majority with security with abort, uses a trusted dealer, and aims for Category N1 at NIST security categories 1 and 5. We estimate fewer than 180 online rounds per attempt in expectation, and at most 350 under a reasonable iteration cap, against thousands reported for earlier threshold FALCON work. In this presentation, we go over the main design choices and differences from the past work.

Joint work: Erdem Alkım, Metin Bektaş, Erem Ersoy, Muhammed Said Gündoğan.

Suggested readings

• Preview Writeup (PDF): ATMACA (A Threshold Multiparty Algorithm for Compact Authentication): Lattice-Based Threshold Signing for FALCON
• Mitaka: a simpler, parallelizable, maskable variant of Falcon (ia.cr/2021/1486)
• Antrag: Annular NTRU Trapdoor Generation (ia.cr/2023/1335)
• Thresholdizing Standardized FALCON Signatures (ia.cr/2026/1300)