Paper 2019/412

On the complexity of the Permuted Kernel Problem

Eliane KOUSSA, Gilles MACARIO-RAT, and Jacques PATARIN


In 1989, A. Shamir introduced an interesting public-key scheme of a new nature, a Zero-Knowledge (ZK) Identification scheme, based on PKP: the Permuted Kernel Problem. PKP is an NP-hard algebraic problem which has been extensively studied. Among all the attacks, the problem PKP is in spite of the research effort, still exponential. This problem was used to develop an Identification Scheme (IDS) which has a very efficient implementation on low-cost smart cards. There has been recently a renewed interest in PKP-based cryptography due to post quantum security considerations, simple security proofs, and the design of new PKP-based signature algorithm. In 2018 and through the Fiat-Shamir transform, the PKP-IDS was used to construct a post-quantum signature scheme which was submitted to a Chinese competition for the design of post-quantum cryptographic algorithms (organized by the Chinese Association CACR). This latter was improved later. The aim of this document is two-fold. First, we investigate the complexity of the combinatorial problem - namely PKP. We also present a summary of previously known algorithms devoted to solve this problem. Contrary to what is shown previously, and after a thorough analysis of the State-of-the-art attacks of PKP, we claim that the Joux-Jaulmes attack is not the most efficient algorithm for solving PKP. In fact, the complexity of the Joux-Jaulmes attack underestimate the amount of certain important phase of the algorithm. Second, we examine the complexity given by various algorithms, specifically the ones introduced by Patarin-Chauvaud and Poupard. It is relatively complex to obtain a general complexity formula due to the very numerous variants. However, we have been able to develop a program and provide its approximate space and time complexities which allow us to identify hard instances and secure sets of parameters of this problem with respect to the best attack currently known.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
CryptanalysisIdentification schemecomplexitypost-quantum cryptographyPermuted Kernel Problem.
Contact author(s)
ejkoussa @ outlook com
2019-09-17: revised
2019-04-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eliane KOUSSA and Gilles MACARIO-RAT and Jacques PATARIN},
      title = {On the complexity of the Permuted Kernel Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/412},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.