Cryptanalysis of the Binary Permuted Kernel Problem

Thales Bandiera Paiva; Routo Terada

Paper 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Applied Cryptography and Network Security 2021 (ACNS 2021)
Keywords: permuted kernel problem cryptanalysis post-quantum cryptography
Contact author(s): thalespaiva @ gmail com
History: 2021-03-27: received
Short URL: https://ia.cr/2021/398
License: CC BY

BibTeX

@misc{cryptoeprint:2021/398,
      author = {Thales Bandiera Paiva and Routo Terada},
      title = {Cryptanalysis of the Binary Permuted Kernel Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/398},
      year = {2021},
      url = {https://eprint.iacr.org/2021/398}
}