Paper 2018/714

PKP-Based Signature Scheme

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

Abstract

In this document, we introduce PKP-DSS: a Digital Signature Scheme based on the Permuted Kernel Problem (PKP). PKP is a simple NP-hard combinatorial problem that consists of finding a kernel for a publicly known matrix, such that the kernel vector is a permutation of a publicly known vector. This problem was used to develop an Identification Scheme which has a very efficient implementation on low-cost smart cards. From this zero-knowledge identification scheme, we derive PKP-DSS with the traditional Fiat-Shamir transform. Thus, PKP-DSS has security that can be provably reduced, in the classical random oracle model, to the hardness of random instances of PKP (or, if wanted, to any specific family of PKP instances). We propose parameter sets following the analysis of State-of-the-art attacks on PKP. We show that PKP-DSS is competitive with other signatures derived from Zero-Knowledge identification schemes. In particular, PKP-DSS-128 gives a signature size of approximately 20 KBytes for 128 bits of classical security, which is approximately 30% smaller than MQDSS. Moreover, our proof-of-concept implementation shows that PKP-DSS-128 is an order of magnitude faster than MQDSS which in turn is faster than Picnic2, SPHINCS,... Since the PKP is NP-hard and since there are no known quantum attacks for solving PKP significantly better than classical attacks, we believe that our scheme is post-quantum secure.