Paper 2018/714

PKP-Based Signature Scheme

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
public-key cryptographypost-quantum cryptographyFiat-Shamir5-pass identification schemePermuted Kernel Problem.
Contact author(s)
ejkoussa @ outlook com
ward beullens @ esat kuleuven be
2019-10-28: last of 6 revisions
2018-08-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ward Beullens and Jean-Charles Faugère and Eliane Koussa and Gilles Macario-Rat and Jacques Patarin and Ludovic Perret},
      title = {PKP-Based Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2018/714},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.