Cryptology ePrint Archive: Report 2019/412

On the complexity of the Permuted Kernel Problem

Eliane KOUSSA and Gilles MACARIO-RAT and Jacques PATARIN

Abstract: 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.

Category / Keywords: public-key cryptography / Cryptanalysis, Identification scheme, complexity, post-quantum cryptography, Permuted Kernel Problem.

Date: received 19 Apr 2019, last revised 17 Sep 2019

Contact author: ejkoussa at outlook com

Available format(s): PDF | BibTeX Citation

Version: 20190917:140008 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]