FALCON signature vulnerability to special attacks and its protection

Abstract

It is well known that quantum algorithms offer exponential speedup in solving the integer factorization and discrete logarithm problems that existing public-key systems rely on. Thus, post-quantum cryptography seeks alternative classical algorithms that can withstand quantum cryptanalysis. Growing concern about the quantum threat has prompted the National Institute of Standards and Technology (NIST) to invite and evaluate applications for a post-quantum cryptography standard, an ongoing process scheduled to be completed by 2023.

Falcon is an electronic signature algorithm based on the mathematics of algebraic lattices. The disadvantage of this algorithm is the small number of studies of resistance against special attacks, as well as attacks through side channels.

This material examines existing attacks on the implementation, and also analyzes the speed with applying countermeasures that would prevent such attacks. Although the Falcon scheme sampler, as well as certain mathematical transformations, are still vulnerable to attacks (which in turn allow the private key to be obtained), the efficiency of the components and mathematics of this signature algorithm make it competitive with other schemes, even with countermeasures against these attacks.

The work will also consider the attack by side channels on the Falcon. Such an attack is a known-plaintext attack that uses the device's electromagnetic radiation to derive secret signature keys, which can then be used to forge signatures in arbitrary messages. The obtained results show that Falcon is quite vulnerable to side-channel attacks and does not yet have protection against such attacks in the proposed implementation. Because of this, standardization or implementation should consider the possibility of physical attacks, as well as options for countering such attacks.