Paper 2011/686

Analysis of some natural variants of the PKP Algorithm

Rodolphe LAMPE and Jacques PATARIN


In 1989, Adi Shamir proposed a new zero-knowledge identification scheme based on a NP-complete problem called PKP for Permuted Kernel Problem. For a given prime p, a given matrix A and a given vector V , the problem is to find a permutation \pi such that the permuted vector V_\pi verifies A.V_\pi = 0 mod p. This scheme is still in 2011 known as one of the most efficient identification scheme based on a combinatorial problem. However, we will see in this paper that it is possible to improve this scheme significantly by combining new ideas in order to reduce the total number of computations to be performed and to improve very efficiently the security against side channel attacks using precomputations. We will obtain like this a new scheme that we have called SPKP. Moreover, if we use precomputed values in the scheme SPKP, then the prover will need to perform no computations (i.e. only selection and transmission of precomputed values). This is very interesting for security against side channel attacks because our scheme is zero-knowledge and we don't perform any computations using the key during the identification so we prove that any attacker (even using side channel attacks) being successfully identified implies that he has a solution to the NP-complete problem PKP.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
identification schemezero knowledgepermuted kernel problem
Contact author(s)
rodolphe lampe @ gmail com
2012-07-04: last of 2 revisions
2011-12-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rodolphe LAMPE and Jacques PATARIN},
      title = {Analysis of some natural variants of the PKP Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2011/686},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.