Cryptology ePrint Archive: Report 2021/398

Cryptanalysis of the Binary Permuted Kernel Problem

Thales Bandiera Paiva and Routo Terada

Abstract: In 1989, Shamir presented an efficient identification scheme (IDS) based on the permuted kernel problem (PKP). After 21 years, PKP was generalized by Lampe and Patarin, who were able to build an IDS similar to Shamir's one, but using the binary field. This binary variant presented some interesting advantages over Shamir's original IDS, such as reduced number of operations and inherently resistance against side-channel attacks. In the security analysis, considering the best attacks against the original PKP, the authors concluded that none of these existing attacks appeared to have a significant advantage when attacking the binary variant. In this paper, we propose the first attack that targets the binary PKP. The attack is analyzed in detail, and its practical performance is compared with our theoretical models. For the proposed parameters originally targeting 79 and 98 bits of security, our attack can recover about 100% of all keys using less than $2^{63}$ and $2^{77}$ operations, respectively.

Category / Keywords: public-key cryptography / permuted kernel problem, cryptanalysis, post-quantum cryptography

Original Publication (in the same form): Applied Cryptography and Network Security 2021 (ACNS 2021)

Date: received 24 Mar 2021

Contact author: thalespaiva at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210327:071627 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]