PKP-Based Signature Scheme

In this document, we introduce \(\textsf {PKP}\hbox {-}\textsf {DSS}\): a Digital Signature Scheme based on the Permuted Kernel Problem (PKP) [23]. PKP is a simple NP-hard [10] 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 (IDS) which has a very efficient implementation on low-cost smart cards. From this zero-knowledge identification scheme, we derive \(\textsf {PKP}\hbox {-}\textsf {DSS}\) with the traditional Fiat-Shamir transform [9]. Thus, \(\textsf {PKP}\hbox {-}\textsf {DSS}\) has a 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 \(\text {PKP}\) instances). We propose parameter sets following the thorough analysis of the State-of-the-art attacks on PKP presented in [17]. We show that \(\textsf {PKP}\hbox {-}\textsf {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 its turn is faster than Picnic2, SPHINCS, ...

Since the \(\text {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.