-We present here a new signature scheme based on traditional number-theoretic problems. Despite the fact that it a combinatorial problem named the Permuted Kernel Problem isn't clear when and even if enormous quantum computations (PKP) [Sha89]. PKP is an NP-complete [GJ79] algebraic problem would be feasible, it is important to anticipate a technological that consists of simple mathematical operations and involves only basic linear algebra. breakthrough and design new public key cryptosytems that are To solve PKP is to find a particular kernel vector for a publicly resistant to quantum attacks. known matrix. Through the complexity analysis of solving PKP, Due to the call for post-quantum standards of the NIST we found the opposite of what is presented in [JJ01]. Precisely, (https://www.nist.gov/), there has been renewed interest in the we noticed that the most efficient algorithm for solving PKP transformed Zero-Knowledge Identification Schemes into Digremains the one which was introduced by J. PATARIN and P. CHAUVAUD in [PC93]. Moreover, PKP has always had the ital Signatures Schemes (DSS) via the Fiat-Shamir paradigm reputation of being the best combinatorial algorithm known for [FS86]. This transformation method is important since it authentication. It was used to build the first Identification Scheme yields to efficient signature schemes in terms of minimal and (IDS) which has an efficient implementation on low-cost smart sufficient security assumptions. cards. Consequently, and via the traditional Fiat-Shamir (FS) Particularly, we are interested in the post-quantum cryptoparadigm, we derive the signature scheme PKP-DSS from a Zero-Knowledge Identification Scheme (ZK-IDS) based on PKP graphic schemes which belongs to the post-quantum branch [Sha89]. whose security relies on the fact that there is no quantum Thus, PKP-DSS has a security that can be provably reduced, in algorithms known to solve NP-Complete problems [BBBV97]. the (classical) random oracle model, to essentially the hardness Namely, the Permuted Kernel Problem: the problem of finding of random instances of PKP. a permutation of a known vector such that the resulting vector Also, we propose different sets of parameters according to several security levels. Each parameter set arises signatures of is in the kernel of a given matrix. length comparable to the other signatures derived from Zero- Here, we study the application in cryptography of the PKP Knowledge identification schemes. In particular, PKP-DSS-128 problem over a finite field. We are essentially concerned about gives a signature size approximately about 18 KBytes for 128 bits this problem because it can be used to build a post-quantum of classical security, while the best known signature schemes built signature scheme based on the hardness of solving random from a ZK-IDS (such as MQDSS [CHR+18], Picnic [CDG+17],... ) give similar signatures ( 16 KB for MQDSS, 33 KB for instances of PKP. It is an old-time combinatorial NP-Complete Picnic,... ). problem. It requires simple operations which involve basic Since there are no known quantum attacks for solving PKP, linear algebra computations. For a little long time, no new we believe that the recommended sets of parameters provide a attacks on PKP were reported which makes the construction quantum secure scheme. of schemes based on hard instances of this problem more togIrnadpehxy,TeFrimats--Shpaumbilri,c-5k-epyascsryipdteongtrifiacpahtyio,nposscth-qemuaen,tuPmermcurytepd- applicable. Kernel Problem.
I. INTRODUCTION
The construction of large quantum computers would break all public-key cryptographic schemes in use today based on the
The main contribution of this paper is to present a new postquantum signature scheme.
In [JJ01], a new approach to attack PKP was introduced. The authors of this latter, assume that the technique described in their article, is faster than any previously known method. But, after the complexity analysis of the PKP problem, it appears that we have different results: the improved algorithm presented in [PC93] form the best attack on PKP. Besides, we are particularly interested in the design of a signature scheme. Similarly to the approaches cited above, by applying the Fiat-Shamir transform, we study the design of post-quantum signature constructed from a 5-pass authentication scheme based on the PKP problem.
Our objective is to define the most optimal parameters for hard instances of this problem, with respect to the security levels identified by NIST [NIS].
The PKP-DSS scheme based on PKP compared well with the other similar (in terms of construction) schemes. We obtained the following results: comparable signature size for the same security levels. Then, this makes the signature scheme based on PKP a competitive cryptosystem.
III. THE PERMUTED KERNEL PROBLEM
In order to introduce the signature scheme, we first present the PKP problem [Sha89]. We also present the best technique for solving it.
PKP [Sha89], [GJ79] is the problem on which the security of PKP-DSS is based. PKP is a linear algebra problem which asks to find a kernel vector of given matrix under a vectorentries constraint. It’s a generalization of the Partition problem [GJ79, pg.224]. More precisely, it is defined as follows:
n-vector V 2 Fpn.
Question. Find a permutation p over (1; : : : ; n) such that A Vp = 0, where Vp = (Vp( j)); j = 1; : : : ; n:
A reduction of the 3-Partition problem proves PKP to be NP-Complete [GJ79] in the good reasoning (i.e.its hardness grows exponentially with p). A fundamental design assumption of PKP-DSS is that solving random instances of PKP are hard to solve in practice (Section IV). In fact, the solidity of PKP comes from, on the one hand, the big number of permutations, on the other hand, from the small number of possible permutations which may suit the kernel equations. More precisely, PKP is hard because it obligates the choice of a vector, with already fixed set of entries, from the kernel of the matrix A.
Note that, to reach higher security levels, it’s more desirable that the n-vector V has distinct coordinates.
IV. BEST KNOWN ATTACKS
The implementation’s efficiency of the first IDS, proposed by A. SHAMIR [Sha89], based on PKP problem has led to several solving tools. In fact, there are various attacks for PKP, which are all exponential.
In [Geo92], J. GEORGIADES presents symmetric polynomials equations which will be utilized by all the other attacks. The authors of [BCCG92] investigate also the security of PKP, where a time-memory trade-off was introduced. Moreover, J. PATARIN and P. CHAUVAUD improve algorithms for the Permuted Kernel Problem [PC93]. Also, in [JJ01], a new timememory trade-off was proposed. After all, it appears that the attack of PATARIN-CHAUVAUD [PC93] is the most efficient one. The details of each attack and the numerical results are given in the main article.
given in a systematic form:
A = (ai j)1 i m;1 j n =
A0jI ; where A0 = (a0i j)1 i m;1 j n m 2 Mm n m(Fp) and I is the identity matrix of size m. By denoting Ap = (aip( j)), the effect of the permutation p over the columns of A, it’s easy to see that ApVp = AV:
First of all, let’s consider the exhaustive search. This test consists of examining all the possible candidates (permutations of a set on n elements) for the solution in order to determine whether a candidate satisfies the problem’s conditions. Despite the fact that this search technique is very general and naive, mainly in this case, where the search space is large, it is important to consider its complexity which is in n!.
In [JJ01], A. JOUX and E. JAULMES introduce a new timememory trade-off algorithm which is an application of the algorithm described in [JL01] to the Permuted Kernel Problem. In fact, the algorithm consists of two main steps: A-Phase and B-Phase. The authors of [JJ01] assume that the B-Phase controls the time complexity of this approach. Without going too far into the analysis of this technique, we found that the contrary is true. By considering a reasonable choices of parameters, it turns out that the time complexity of the algorithm is dominated by the A-Phase. This is one of the most interesting points of our article.
Thus, this attack is not the most efficient for solving PKP but, the attack of PATARIN-CHAUVAUD [PC93]. This also shows that the PKP problem is more difficult to attack than we thought before our article, which has a good impact when it comes to the PKP-based signature scheme.
J. PATARIN and P. CHAUVAUD combine in [PC93] the two ideas presented in the previous attacks (see [BCCG92], [Geo92]). The result was a reduction in the time required to attack PKP. They also present some new ideas in order to reduce this time the memory needed.
Thus, this leads to a new algorithm which is quicker and more efficient than the attacks cited above. The details and the numerical results are given in the main article [PC93]. Here is the Magma code that gives the time complexity of the last improved algorithm. patarin6:=function(n,m,p) cmin:=999999; Lp:=Ceiling(Log(2,p)); nS :=Binomial(n,m); NU:=Round((1-&*[ 1-p^(i-m) :
i in [0..m-1]])*nS); PR:=[ Round( m*(nS-NU)*Binomial(m,i) *(1-1/p)^(m-i)/p^i) : i in [0..m]]; a:=Maximum([ i+1 : i in [0..m] | PR[i+1] gt 100 ]); for k:=2 to m do; r:=n-m-1+k; for l:=1 to r do; s:=r-l; if s+a lt n-m then continue; end if; pr:=Maximum(1,Factorial(n)/Factorial(n-l) /p^(k-1)); for t:=1 to s-1 do; u:=s-t; pr2:=Maximum(1,Factorial(n-u)/
Factorial(n-s)/p); step1 := Factorial(n)/Factorial(n-l); step20 := Factorial(n-u)/Factorial(n-s); step2 := Binomial(n,u) * ( step20 +
Factorial (u) * pr2 * pr); ctime:= Log(2,Maximum(step1, step2)); if ctime lt cmin then cmin:=ctime; nbper:=Round(Log(2,Factorial(n)/p^m)); nbker:=Round(Log(2,Factorial(p)
/Factorial(p-m)/p^m)); mem:=Round(Log(2,step1*l*Lp)); U:=ctime; end if; end for; end for; end for; return U; end function;
V. IDENTIFICATION SCHEME (IDS) BASED ON PKP In this section, we present the 5-pass Zero-Knowledge Identification Scheme (ZK-IDS) based on the computational hardness of PKP [Sha89], [LP11], noted here PKP-IDS.
We first quote and refer to some of the general definitions given in [CHR+18] : Identification scheme, Completeness, Soundness (with soundness error), Honest-verifier zeroknowledge, and also in [HNO+09], [Dam99] : statistically hiding commitment, computationally binding commitment. We then apply and adapt these definitions to the Identification scheme base on PKP and give and prove its own properties of performance and security. This approach will be more convenient for presenting the signature scheme in the next section.
In what follows and as in [CHR+18], we assume the existence of a non-interactive commitment scheme Com which verifies the two properties : statistically hiding and computationally binding (see [HNO+09], [Dam99] for details). The commitments are computed using the function Com. Note that, it is possible to let Com be H a one way hash and collision intractable function, behaving like a random oracle.
In this section, we present (slightly modified version of) PKP-IDS. It can be described as three probabilistic polynomial time algorithms IDS = KEYGEN; P; V for which we give below a literal description. The security parameter of the identification scheme is noted l .
Generation of the public key and secret key in PKP-IDS. The users first agree on a prime number p, and a m n matrix A with coefficients in Fp. The public-key in PKP-IDS is given by an instance of PKP with a preassigned solution that will be the secret-key. Thus, each user picks a (right) kernel-vector
n elements sk = p and finishes by computing V = Wp 1 .
We summarize the public-key/secret-key generation in Algorithm 1. It takes the security parameter l as input. Algorithm 1 pk=sk generation in PKP-IDS 1: procedure PKP-IDS:KEYGEN(1l ) 2: pk.seed Randomly sample l bits 3: Randomly sample a matrix A 2 Mm n(Fp) using a pseudo-random generator with pk.seed 4: Randomly pick a n-vector W 2 Ker(A) 5: sk.seed Randomly sample l bits 6: Generate a random permutation p 2 Sn using a pseudorandom generator with sk.seed 7: sk p 8: Compute V = Wp 1 9: pk (p; pk.seed;V ) 10: Return (pk; sk) 11: end procedure
One 5-pass round of identification : Prover P and Verifier V . Prover and Verifier are interactive algorithms that realize the identification protocol in 5 passes. The 5 passes consist in one commitment and two responses transmitted from the prover to the verifier and two challenges transmitted from the verifier to the prover. Random choices of prover and verifier are made using the uniform distribution. The protocol of identification is summarized in Algorithm 2.
From Shamir in [Sha89] we have the following results.
Theorem 5.1: PKP-IDS is complete. PKP-IDS is statistically zero knowledge when the commitment scheme Com is computationally binding. PKP-IDS is sound with soundness error p+1 when the commitment scheme Com is computationally 2p binding.
Definition 5.2 (N rounds of PKP-IDS): Let PKP-IDS= (KEYGEN; P; V ) then PKP IDSN = (KEYGEN; PN ; V N ) is the parallel composition of N rounds of PKP IDS.
Key sizes. The secret key is the permutation p obtained using a pseudo random generator that takes as input a seed of Algorithm 2 One round of the 5-pass identification scheme 1: procedures P(sk); V (pk) 2: //Prover setup 3: P sets R Random vector in Fpn 4: P sets s .seed Random seed of l bits 5: P sets s Random permutation in Sn using a pseudorandom generator with s .seed 6: //Commitment step by the Prover 7: P sets C0 Com s ; AR 8: P sets C1 Com ps ; Rs 9: P sends (C0; C1) to V 10: //First challenge by the verifier 11: V sets Ch0 c random in Fp 12: V sends Ch0 to P 13: P sets Z Rs + cVps and sends Z to V 14: V sets Ch1 b random bit 15: V sends Ch1 to P 16: if Ch1 = 0 then 17: P reveals s .seed to V 18: V accepts if Com s ; As Z = C0 19: else 20: P reveals ps to V 21: V accepts if Com ps ; Z cVps = C1 22: end if 23: end procedure l bits. The size of the public vector V is n log2(p) bits. The bit size of the public key (p; A;V ) is:
log2(p) + l + n log2(p) bits:
Performance of the scheme. We can now provide the communication complexity of the IDS, where its fraud’s probability is p2+p1 . Consider that the commitment function Com used in the protocol, returns values of 2l bits. The transfer of the n-vector Z 2 Fpn requires n log2 p Thus, the fourth passes demand 4l + (n + 1) log2 p + 1 bits.
Note also that, compared to the original scheme of Shamir in [Sha89], we have reduced the complexity in communication by revealing only the seed used to generate the random elements. More precisely, instead of revealing the random permutation s , the prover P only sends its seed sigma.seed.
So, the last pass needs, according to Ch1, l bits to reveal the permutation s if Ch1 = 0; and log2(n!) bits to reveal the permutation ps , if Ch1 = 1.
In total, the weighted average bit complexity of the scheme repeated N rounds is given by: 1 4l + (n + 1) log2 p + 1 + (l + log2(n!)) N: 2 VI. DIGITAL SIGNATURE SCHEME (DSS) BASED ON PKP
We present here the main contribution of this work which is to construct a DSS i.e. a digital signature scheme, based on the PKP problem, from the IDS defined in Section V-B. This construction uses the well-known Fiat Shamir transformation [FS86].
So next, we introduce the basic definitions needed. Then, similarly to the MQ-based signatures and Picnic, we define our scheme, and we finish with a comparison with other cryptosystems.
The classical method of Fiat-Shamir (FS) transforms an interactive proof of knowledge (identification scheme) into a non interactive one (signature scheme). This work is a direct application of this method to get PKP-DSS from PKP-IDS. FiatShamir transform for PKP-IDS. We recall that PKP-IDS the previously defined identification scheme achieves soundness with soundness error k = 12+pp . We select N the number of parallel rounds of PKP-IDS such that kN is negligible in l . N
and H2 : f0; 1g ! f0; 1gN . By applying Construction 4.7 in [CHR+18], we get PKP-DSS= (KEYGEN; SIGN; VERIFY). See Algorithms 3 and 4.
A valid signature of a message m by PKP-DSS is then a tuple (m; s0; s1; s2), where s0; s1; s2 hold the (vector of parallel) commitments and responses of the non interactive prover. The implicit values h1 = H1(m; s0) and h2 = H2(m; s0; h1; s1) represent the (vector of parallel) challenges of the non interactive verifier.
We get the similar result as Th. 5.1 in [CHR+18].
Chosen Adaptive Message Attacks (EU-CMA) in the random oracle model, if the search version of the Permuted Kernel problem is intractable, the hash functions are modeled as random oracles, the commitment functions are computationally binding, computationally hiding, and the probability that their output takes a given value is negligible in the security parameter, the pseudo-random generators are modeled as random oracle, and the pseudo-random generators have outputs computationally indistinguishable from random.
The proof is exactly the same as in [CHR+18].
Since we are comparing PKP-DSS to other post-quantum schemes, it is important to define the security of our scheme against quantum attacks. This can be done by investigating quantum algorithms for solving PKP. However, till now there are no quantum versions of the known attacks on PKP cited above IV. Also, there is no gain of considering Grover’s algorithm because the best attack for solving PKP is much more efficient than the exhaustive search (by a quadratic factor).
Moreover, the post-quantum security of the FIAT-SHAMIR transform has been studied in [Unr15], [Unr17]. The author of [Unr15] explains that the classic FIAT-SHAMIR transform might not be secure against quantum computers. Thus, a new technique with the extra property of "extractability" was Algorithm 3 Signing process in PKP-DSS 1: procedure PKP-DSS.SIGN(m; sk) 2: R H0 sk jj m , R is a message-dependent random value 3: D H0 pk jj R jj m , D is the randomized message digest 4: R(1); : : : ; R(N) RG0 R:seed; D 5: s (1); : : : ; s (N) RG1 s :seed; D 6: for j f rom 1 to N do 7: C(0j) = Com s ( j); AR( j) ; 8: C(1j) = Com ps ( j); R(sj()j) :
COM(j) := C(0j); C( j)
1 end for S0 H0 COM(1)jj : : : jjCOM(N) : Ch0 H1 D; S0 Parse Ch0 as Ch0 := (c(1); : : : ; c(N)); c( j) 2 Fp for j f rom 1 to N do
Z( j)
R(sj()j) + c( j)Vps( j) ,
resp(0j) := Z( j):
end for
S1 resp(
resp(1j) s ( j): else
resp(1j) ps ( j):
end if
end for
S2
resp(
(1) = Z(1)jj : : : jj; Z(N) : 29: Return R; S0; S1; S2 : 30: end procedure developed to obtain a quantum-secure transform.
In [Unr17], D. UNRUH justifies that the FIAT-SHAMIR transform is secure under certain conditions. Currently, it seems impractical to apply the Unruh transform since the obtained scheme is costly in terms of signature’s size. Therefore, we can keep the initial FIAT-SHAMIR as long as there is neither perfect proof nor quantum attack.
Our main goal is to find the best parameters which can ensure the minimal size of a signature. We show, in the next sections, that the PKP-based signature scheme provides a signature’s size less than the other signature schemes, precisely MQDSS [CHR+18] and Picnic [CDG+17].
Signature size: We said that our signing scheme is constructed from the iterations of the IDS (given in 2). Now, to have the total cost, it is important to define the number of rounds N needed to achieve EU-CMA for l bits of security. Algorithm 4 Verification process in PKP-DSS 9: as an attacker could perform a preimage search to control the challenges. Hence, we get that N l = log2( p2+p1 ).
We begin to present how to compute the complexity in bits. Recall that the signature is composed of R the messagedependent random value, S0, S1 and S2, where S0 is the hashed value of the commitments of all rounds, S1 is formed by the first responses, and S2 is the concatenation of the some commitments and the second responses to the challenges. For S0 which is a hashed value, it costs 2l bits. S1 depends on the size of Z, so it is in N n log2 p. For S2, we present next each case: b=0: The signer reveals one seed sigma:seed (similarly to 2) as a response. It costs the seed size which is presented by l bits. In addition to the size of the commitment C1, we have in average:
A = We have thus the following signature size: size o f R size o f S0 z2}l|{ + z2}l|{ + N n log2(p) + A + B :
| size o f S{z1 and S2 }
How parameters affect performance As we said previously, the DSS is mainly affected by the following set of parameters: (p; n; m). We now explicitly detail the choice of parameters. Recall that firstly the IDS [Sha89] was designed to suit small devices. Thus, A. SHAMIR proposed p = 256. Nowadays, with the 64 bit computer architecture, the computations modulo a prime number of 32 or 64 bits are feasible. Thus, we consider that p is of 8; 16; 32; or 64 bits.
A solution of a random instance of PKP is to find a kernel n-vector (Vp ) with distinct coordinates in Fp. Hence, the probability to find such vector shouldn’t be too small. Also in [Sha89], A. SHAMIR estimated n to be between 32 and 64. Later on, several attacks [BCCG92], [PC93] shows that the choice n = 32 is not recommended for strong security requirements. So, to find an n-vector with no double in Fp, and by considering the Birthday Paradox, we keep the choice of n around 64, in addition to n O pp .
On the other hand, the probability of an arbitrary vector to be in the kernel of the matrix A 2 Mm n whose rank is equal to m, is p m. Moreover, if the n-vector V has no double, the cardinal of its orbit under the possible permutations p is n!. Thus, in order to get one solution, we have the following constraint: n! pm.
Hence, following these criteria, we have in total: p n!
O n2 ; nn pm.
This leads to take m n log(n)=log(p) n=2.
How to choose the security parameter l . Recall that, the security parameter l controls the number of iterations N = l = log2( p2+p1 ) performed to achieve a security level needed. It also defines the output of the hash and commitments functions which is in 2l , in addition to the seeds length.
In general, the hash and commitment functions require collision resistance, preimage resistance, and/or second preimage resistance. Thus, in this article, to reach for example a security of 128 bits, we initiate l to be exactly of 128 bits. As well for the others security levels (192 and 256).
However, as shown in [GS94], it is always possible to reduce this choice of 256-bit hash values while keeping a security level of 128 bits. Yet, to compare PKP-DSS to the other schemes (as MQDSS) we keep this doubling. Note that, the optimization of [GS94] can be applied to PKPDSS as well to the other schemes (MQDSS, Picnic,...).
In the following table we present several parameters sets for different levels of security. We define these parameters by considering the formulas given in Section VI-C and the criteria defined above. Furthermore, our parameters raise a secure scheme against all the attacks described in Section IV, mainly, against the most efficient attack: the algorithm of PATARIN-CHAUVAUD [PC93].
Parameters Set PKP-DSS-128 PKP-DSS-192 PKP-DSS-256 l p n
m 128 977 61 28 192 1409 87 42 256 1889 111 55
TABLE I PKP-DSS PARAMETERS SETS
Iterations number
N 129 193 257
Next, we compare PKP-DSS to MQDSS [CHR+18] and Picnic [CDG+17]. We consider the public/secret (pk=sk) keys size and the signature size, for different security levels.
Security level
Parameters Sets
Secret key size (Bytes)
Public key size (Bytes)
Signature size (KBytes) 8 2 1 2 9 1
One can conclude that the IDS based on PKP constitutes one of the most efficient schemes.
VII. CONCLUSION
In this article, we discussed some of the most well-known technique for solving PKP. Particularly, we drew attention to the fact that, the Approach of PATARIN-CHAUVAUD [PC93] is the most efficient attack on PKP.
Moreover, our main motivation is the construction of a post-quantum secure cryptosystem. In [Sha89], a Zeroknowledge identification scheme (ZK-IDS) was introduced. A well-known method, namely FIAT-SHAMIR technique [FS86], is used to turn an IDS into a digital signature scheme (DSS).
The authors of [CHR+18], presents a DSS, named MQDSS. It was built from an IDS based on the MQ problem (Multivariate quadratic equations solving problem). Thus, they give several sets of parameters which provide post-quantum security.
As well, Picnic [CDG+17] is designed to be secure against classical and quantum attacks. It was also constructed from a Zero-knowledge identification scheme to match different security levels.
Hence, similarly to the technique used to build these schemes, we have constructed a DSS based on the PKP problem. We utilized the ZK-authentication scheme presented in [Sha89] to deduce the signature scheme. In order to compare this latter to the other schemes, we have tested the most known techniques to solve PKP.
We finally conclude several sets of parameters given in VI-C which provides 128; 192 and 256 bits of classical security. Mainly, we conclude that the DSS based on PKP gives signatures with a size comparable to the ones in MQDSS and smaller than the ones given by Picnic. Consequently, this is what makes from this PKP-DSS a competitive scheme to the other related cryptosystems.
ACKNOWLEDGMENT
My sincere gratitude and appreciation go to my supervisos, Prof. Jacques Patarin and R.D Jean-Charles Faugère for their valuable comments and suggestions. Our continuous discussion, their immense knowledge and thought provoking questions helped me to get results of better quality. Also, i would especially like to show my deepest thanks for A.P Ludovic Perret for sharing his enormous experiences and illuminating views on all the issues related to my Phd. His professional and aspiring guidance pushed me to widen my work from different perspectives.
I take this opportunity to express thanks, to Mr. Gilles Macario-Rat for also helping me to conduct this PhD research.
I am also grateful to the University of Pierre and Marie Curie (UPMC), and in particular, to the LIP6 laboratory and the PolSys team for providing me with all the essential facilities being required for my work.