Cryptology ePrint Archive: Report 2022/259

Partial Key Exposure Attacks on BIKE, Rainbow and NTRU

Andre Esser and Alexander May and Javier Verbel and Weiqiang Wen

Abstract: In a so-called partial key exposure attack one obtains some information about the secret key, e.g. via some side-channel leakage. This information might be a certain fraction of the secret key bits (erasure model) or some erroneous version of the secret key (error model). The goal is to recover the secret key from the leaked information.

There is a common belief that, as opposed to e.g. the RSA cryptosystem, most post-quantum cryptosystems are usually resistant against partial key exposure attacks. We strongly question this belief by constructing partial key exposure attacks on code-based, multivariate, and lattice-based schemes (BIKE, Rainbow and NTRU). Our attacks exploit the redundancy that modern PQ cryptosystems inherently use for efficiency reasons. The application and development of techniques from information set decoding plays a crucial role for achieving our results.

On the theoretical side, we show non-trivial information leakage bounds that allow for a polynomial time key recovery attack. As an example, for all schemes the knowledge of a constant fraction of the secret key bits suffices to reconstruct the full key in polynomial time.

Even if we no longer insist on polynomial time attacks, most of our attacks extend well and remain feasible up to large erasure and error rates. In the case of BIKE for example we obtain attack complexities around 60 bits when half of the secret key bits are erased, or a quarter of the secret key bits are faulty.

Our results show that even highly error-prone key leakage of modern PQ cryptosystems may lead to full secret key recoveries.

Category / Keywords: public-key cryptography / Erasure/Error Model, Asymptotics, Cold Boot Key Recovery

Date: received 26 Feb 2022

Contact author: andre r esser at gmail com, alex may at rub de, javier verbel at tii ae, weiqiang wen at telecom-paris fr

Available format(s): PDF | BibTeX Citation

Version: 20220302:140250 (All versions of this report)

Short URL: ia.cr/2022/259


[ Cryptology ePrint archive ]