Cryptology ePrint Archive: Report 2020/1503

Key Recovery Attack on Bob's Secrets in CRYSTALS-KYBER and SABER

Satoshi Okada and Yuntao Wang

Abstract: CRYSTALS-KYBER and SABER are two lattice-based encryption algorithms in the third round finalists of NISTís post-quantum cryptography standardization project. In ProvSec 2020, Wang et al. introduced a notion of ďmeta-PKEĒ for (ring) Learning With Errors crypto mechanism. They also proposed a key reuse attack on NewHope and LAC cryptosystems which meet the meta-PKE model. In their attack, the encryptor Bobís partial (or even all) secrets can be recovered under the key reuse scenario. In this paper, we consider the meta-PKE model inCRYSTALS-KYBER and SABER. By improving Wang et al.ís method, we show that our proposed attacks cost only 4, 3, and 4 queries to recover Bobís secrets for any security levels of I (AES-128), III (AES-192), and V (AES-256), respectively in CRYSTALS-KYBER. Simultaneously, only 6, 4, and 4 queries are required to recover Bobís secret for security levels I, III, and V in SABER.

Category / Keywords: public-key cryptography / PQC, Key Reuse Attack, Meta-PKE, CRYSTALS-KYBER, SABER

Date: received 30 Nov 2020, last revised 1 Dec 2020

Contact author: okada-satoshi323 at g ecc u-tokyo ac jp,y-wang@jaist ac jp

Available format(s): PDF | BibTeX Citation

Version: 20201202:100441 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]