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 problemcryptanalysispost-quantum cryptography
Contact author(s)
thalespaiva @ gmail com
History
2021-03-27: received
Short URL
https://ia.cr/2021/398
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/398}},
      url = {https://eprint.iacr.org/2021/398}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.