**PKP-Based Signature Scheme**

*Ward Beullens and 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 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.

**Category / Keywords: **public-key cryptography / public-key cryptography, post-quantum cryptography, Fiat-Shamir, 5-pass identification scheme, Permuted Kernel Problem.

**Date: **received 31 Jul 2018, last revised 28 Oct 2019

**Contact author: **ejkoussa at outlook com, ward beullens at esat kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20191028:100205 (All versions of this report)

**Short URL: **ia.cr/2018/714

[ Cryptology ePrint archive ]