Paper 2019/412

On the complexity of the Permuted Kernel Problem

Eliane KOUSSA and Gilles MACARIO-RAT and Jacques PATARIN

Abstract

In this document, we investigate the complexity of an old-time combinatorial problem - namely Permuted Kernel Problem (PKP) - about which no new breakthrough were reported for a while. PKP is an NP-complete algebraic problem that consists of finding a kernel vector with particular entries for a publicly known matrix. It’s simple, and needs only basic linear algebra. Hence, this problem was used to develop the first Identification Scheme (IDS) which has an efficient implementation on low-cost smart cards. The Permuted Kernel Problem has been extensively studied. We present a summary of previously known algorithms devoted to solve this problem and give an update to their complexity. Contrary to what is shown in JOUX-JAULMES's article, and after a thorough analysis of the State-of-the-art attacks of PKP, we claim that the most efficient algorithm for solving PKP is still the one introduced by J. PATARIN and P. CHAUVAUD. We have been able to specify a theoretical bound on the complexity of PKP which allows us to identify hard instances of this latter. Among all the attacks, the problem PKP is in spite of the research effort, still exponential.