We present here a new signature scheme based on a combinatorial problem named the Permuted Kernel Problem(PKP) [Sha89]. PKP is an NP-complete [GJ79] algebraic problem that consists of simple mathematical operations and involves onlybasic linear algebra. To solve PKP is to find a particular kernel vector for a publicly known matrix. Through the complexity analysis of solving PKP, we found the opposite of what is presented in [JJ01]. Precisely, we noticed that the most efficient algorithm for solving PKP remains the one which was introduced by J. PATARIN and P. CHAUVAUDin [PC93]. Moreover, PKP has always had the reputation of being the best combinatorial algorithm known for authentication. It was used to build the first Identification Scheme (IDS) which has an efficient implementation on low-cost smartcards. Consequently, and via the traditional Fiat-Shamir (FS) paradigm, we derive the signature scheme PKP-DSS from a Zero-Knowledge Identification Scheme (ZK-IDS) based on PKP [Sha89].Thus, PKP-DSS has a security that can be provably reduced, in the (classical) random oracle model, to essentially the hardness of random instances of PKP. Also, we propose different sets of parameters according to several security levels. Each parameter set arises signatures of length comparable to the other signatures derived from Zero-Knowledge identification schemes. In particular, PKP-DSS-128 gives a signature size approximately about 18K Bytes for 128 bits of classical security, while the best known signature schemes built from a ZK-IDS (such as MQDSS [CHR+18], Picnic [CDG+17], ...) give similar signatures ($\simeq$16KB for MQDSS,$\simeq$33KB for Picnic, ...). Since there are no known quantum attacks for solving PKP, we believe that the recommended sets of parameters provide aquantum secure scheme.