On the complexity of the Permuted Kernel Problem

Eliane KOUSSA; Gilles MACARIO-RAT; Jacques PATARIN

Paper 2019/412

On the complexity of the Permuted Kernel Problem

Eliane KOUSSA, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Cryptanalysis Identification scheme complexity post-quantum cryptography Permuted Kernel Problem.
Contact author(s): ejkoussa @ outlook com
History: 2019-09-17: revised; 2019-04-22: received; See all versions
Short URL: https://ia.cr/2019/412
License: CC BY

BibTeX

@misc{cryptoeprint:2019/412,
      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{https://eprint.iacr.org/2019/412}},
      url = {https://eprint.iacr.org/2019/412}
}