Welcome to the resource topic for 2021/398
Title:
Cryptanalysis of the Binary Permuted Kernel Problem
Authors: Thales Bandiera Paiva, 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.
ePrint: https://eprint.iacr.org/2021/398
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .