Paper 2018/714

PKP-Based Signature Scheme

Jean-Charles Faugère and Eliane Koussa and Gilles Macario-Rat and Jacques Patarin and Ludovic Perret

Abstract

In this document, we introduce PKP-DSS a Digital Signature Scheme based on the so-called Permuted Kernel Problem (PKP). 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.\\ We construct PKP-DSS from a Zero-Knowledge Identification Scheme (ZKIDS) based on PKP. We derive the signature scheme PKP-DSS by using the traditional Fiat-Shamir (FS) transform. Thus, PKP-DSS has a security that can be provably reduced, in the (classical) random oracle model, to essentially the hardness of random instances of PKP.\\ Contrary to what is shown in "Cryptanalysis of PKP: A New Approach", and after a thorough analysis of the State-of-the-art attacks of PKP, we found that the most efficient solving tool for PKP was introduced by J. Patarin and P. Chauvaud.\\ In this paper, we also propose several sets of parameters for different security levels. Each parameter set arises signatures of length comparable to the other signatures derived from Zero-Knowledge identification schemes. In particular, PKP-DSS-128 gives a signature size approximately about 16 KBytes for 128 bits of classical security, while the best known signature schemes built from a ZKIDS (such as MQDSS, Picnic,... ) give similar signatures (approximately 16 KB for MQDSS, approximately 33 KB for Picnic,...).\\ Since there are no known quantum attacks for solving PKP, we believe that the recommended sets of parameters provides a quantum secure scheme.