=Paper=
{{Paper
|id=Vol-2343/paper11
|storemode=property
|title=Combinatorial Digital Signature Scheme
|pdfUrl=https://ceur-ws.org/Vol-2343/paper11.pdf
|volume=Vol-2343
|authors=Eliane Koussa,Jean-Charles Faugere,Gilles Macario-Rat,Jacques Patarin,Ludovic Perret
|dblpUrl=https://dblp.org/rec/conf/bdcsintell/KoussaFMPP18
}}
==Combinatorial Digital Signature Scheme==
https://ceur-ws.org/Vol-2343/paper11.pdf
Combinatorial Digital Signature Scheme
*
1st Jean-Charles FAUGÈRE 2nd Eliane KOUSSA 3rd Gilles M ACARIO -R AT
INRIA and UPMC Uni Paris 6 Versailles Laboratory of Mathematics Orange Labs
Sorbonne Universities UVSQ, University of Paris-Saclay Paris, France
Paris, France Versailles, France gilles.macariorat@orange.com
jean-charles.faugere@inria.fr eliane.koussa@uvsq.fr
4th Jacques PATARIN 5th Ludovic P ERRET
CNRS, Versailles Laboratory of Mathematics INRIA and UPMC Uni Paris 6
UVSQ, University of Paris-Saclay Sorbonne Universities
, Versailles, France Paris, France
jpatarin@club-internet.fr Ludovic.Perret@lip6.fr
Abstract—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 Dig-
remains the one which was introduced by J. PATARIN and
P. C HAUVAUD 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 crypto-
paradigm, 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
Index Terms—public-key cryptography, post-quantum cryp-
tography, Fiat-Shamir, 5-pass identification scheme, Permuted applicable.
Kernel Problem.
II. M AIN RESULTS
The main contribution of this paper is to present a new post-
I. I NTRODUCTION
quantum signature scheme.
The construction of large quantum computers would break In [JJ01], a new approach to attack PKP was introduced.
all public-key cryptographic schemes in use today based on the The authors of this latter, assume that the technique described
48
in their article, is faster than any previously known method. where a time-memory trade-off was introduced. Moreover,
But, after the complexity analysis of the PKP problem, it J. PATARIN and P. C HAUVAUD improve algorithms for the
appears that we have different results: the improved algorithm Permuted Kernel Problem [PC93]. Also, in [JJ01], a new time-
presented in [PC93] form the best attack on PKP. Besides, we memory trade-off was proposed. After all, it appears that the
are particularly interested in the design of a signature scheme. attack of PATARIN -C HAUVAUD [PC93] is the most efficient
Similarly to the approaches cited above, by applying the one. The details of each attack and the numerical results are
Fiat-Shamir transform, we study the design of post-quantum given in the main article.
signature constructed from a 5-pass authentication scheme We assume that the matrix A ∈ Mm×n (F p ) is of rank m,
based on the PKP problem. given in a systematic form:
Our objective is to define the most optimal parameters for
A = (ai j )1≤i≤m,1≤ j≤n = A0 |I ,
hard instances of this problem, with respect to the security
levels identified by NIST [NIS]. where A0 = (a0i j )1≤i≤m,1≤ j≤n−m ∈ Mm×n−m (F p ) and I is the
The PKP-DSS scheme based on PKP compared well with the identity matrix of size m. By denoting Aπ = (aiπ( j) ), the effect
other similar (in terms of construction) schemes. We obtained of the permutation π over the columns of A, it’s easy to see
the following results: comparable signature size for the same that Aπ Vπ = AV.
security levels. Then, this makes the signature scheme based
on PKP a competitive cryptosystem. A. Brute-force search
First of all, let’s consider the exhaustive search. This test
III. T HE P ERMUTED K ERNEL P ROBLEM consists of examining all the possible candidates (permutations
In order to introduce the signature scheme, we first present of a set on n elements) for the solution in order to determine
the PKP problem [Sha89]. We also present the best technique whether a candidate satisfies the problem’s conditions. Despite
for solving it. the fact that this search technique is very general and naive,
mainly in this case, where the search space is large, it is
A. Introduction to PKP important to consider its complexity which is in n!.
PKP [Sha89], [GJ79] is the problem on which the security
B. A new Approach of A. J OUX and E. JAULMES
of PKP-DSS is based. PKP is a linear algebra problem which
asks to find a kernel vector of given matrix under a vector- In [JJ01], A. J OUX and E. JAULMES introduce a new time-
entries constraint. It’s a generalization of the Partition problem memory trade-off algorithm which is an application of the
[GJ79, pg.224]. More precisely, it is defined as follows: algorithm described in [JL01] to the Permuted Kernel Problem.
In fact, the algorithm consists of two main steps: A-Phase
Input. A finite field F p , a matrix A ∈ Mm×n (F p ) and a and B-Phase. The authors of [JJ01] assume that the B-Phase
n-vector V ∈ F p n . controls the time complexity of this approach. Without going
Question. Find a permutation π over (1, . . . , n) such that too far into the analysis of this technique, we found that
A ×Vπ = 0, where Vπ = (Vπ( j) ), j = 1, . . . , n. the contrary is true. By considering a reasonable choices
A reduction of the 3-Partition problem proves PKP to be of parameters, it turns out that the time complexity of the
NP-Complete [GJ79] in the good reasoning (i.e.its hardness algorithm is dominated by the A-Phase. This is one of the
grows exponentially with p). A fundamental design assump- most interesting points of our article.
tion of PKP-DSS is that solving random instances of PKP Thus, this attack is not the most efficient for solving PKP
are hard to solve in practice (Section IV). In fact, the solidity but, the attack of PATARIN -C HAUVAUD [PC93]. This also
of PKP comes from, on the one hand, the big number of shows that the PKP problem is more difficult to attack than
permutations, on the other hand, from the small number of we thought before our article, which has a good impact when
possible permutations which may suit the kernel equations. it comes to the PKP-based signature scheme.
More precisely, PKP is hard because it obligates the choice of C. Improved algorithms for PKP
a vector, with already fixed set of entries, from the kernel of
J. PATARIN and P. C HAUVAUD combine in [PC93] the
the matrix A.
two ideas presented in the previous attacks (see [BCCG92],
Note that, to reach higher security levels, it’s more desirable
[Geo92]). The result was a reduction in the time required to
that the n-vector V has distinct coordinates.
attack PKP. They also present some new ideas in order to
IV. B EST KNOWN ATTACKS reduce this time the memory needed.
Thus, this leads to a new algorithm which is quicker and
The implementation’s efficiency of the first IDS, proposed
more efficient than the attacks cited above. The details and
by A. S HAMIR [Sha89], based on PKP problem has led to
the numerical results are given in the main article [PC93].
several solving tools. In fact, there are various attacks for PKP,
Here is the Magma code that gives the time complexity of the
which are all exponential.
last improved algorithm.
In [Geo92], J. G EORGIADES presents symmetric polynomi-
als equations which will be utilized by all the other attacks. patarin6:=function(n,m,p)
The authors of [BCCG92] investigate also the security of PKP, cmin:=999999;
49
Lp:=Ceiling(Log(2,p)); verifies the two properties : statistically hiding and compu-
nS :=Binomial(n,m); tationally binding (see [HNO+ 09], [Dam99] for details). The
NU:=Round((1-&*[ 1-p^(i-m) : commitments are computed using the function Com. Note that,
i in [0..m-1]])*nS); it is possible to let Com be H a one way hash and collision
PR:=[ Round( m*(nS-NU)*Binomial(m,i) intractable function, behaving like a random oracle.
* (1-1/p)^(m-i)/p^i) : i in [0..m]];
B. PKP 5-pass IDS
a:=Maximum([ i+1 : i in [0..m] | PR[i+1] gt
100 ]); In this section, we present (slightly modified version of)
for k:=2 to m do; PKP-IDS. It can be described as three probabilistic polynomial
P, V
r:=n-m-1+k; time algorithms IDS = K EY G EN , for which we
for l:=1 to r do; give below a literal description. The security parameter of the
s:=r-l; identification scheme is noted λ .
if s+a lt n-m then continue; end if; Generation of the public key and secret key in PKP-IDS.
pr:=Maximum(1,Factorial(n)/Factorial(n-l) The users first agree on a prime number p, and a m × n matrix
/p^(k-1)); A with coefficients in F p . The public-key in PKP-IDS is given
for t:=1 to s-1 do; by an instance of PKP with a preassigned solution that will
u:=s-t; be the secret-key. Thus, each user picks a (right) kernel-vector
pr2:=Maximum(1,Factorial(n-u)/ W ∈ Ker(A), then randomly generates a secret permutation of
Factorial(n-s)/p); n elements sk = π and finishes by computing V = Wπ −1 .
step1 := Factorial(n)/Factorial(n-l); We summarize the public-key/secret-key generation in Al-
step20 := Factorial(n-u)/Factorial(n-s); gorithm 1. It takes the security parameter λ as input.
step2 := Binomial(n,u) * ( step20 +
Algorithm 1 pk/sk generation in PKP-IDS
Factorial (u) * pr2 * pr);
ctime:= Log(2,Maximum(step1, step2)); 1: procedure PKP-IDS.K EY G EN (1λ )
if ctime lt cmin then cmin:=ctime; 2: pk.seed ← Randomly sample λ bits
nbper:=Round(Log(2,Factorial(n)/p^m)); 3: Randomly sample a matrix A ∈ Mm×n (F p ) using a
nbker:=Round(Log(2,Factorial(p) pseudo-random generator with pk.seed
/Factorial(p-m)/p^m)); 4: Randomly pick a n-vector W ∈ Ker(A)
mem:=Round(Log(2,step1*l*Lp)); 5: sk.seed ← Randomly sample λ bits
U:=ctime; 6: Generate a random permutation π ∈ Sn using a pseudo-
end if; random generator with sk.seed
end for; 7: sk ← π
end for; 8: Compute V = Wπ −1
end for; 9: pk ← (p, pk.seed,V )
return U; 10: Return (pk, sk)
end function; 11: end procedure
V. I DENTIFICATION SCHEME (IDS) BASED ON PKP One 5-pass round of identification : Prover P and
Verifier V . Prover and Verifier are interactive algorithms that
In this section, we present the 5-pass Zero-Knowledge
realize the identification protocol in 5 passes. The 5 passes
Identification Scheme (ZK-IDS) based on the computational
consist in one commitment and two responses transmitted
hardness of PKP [Sha89], [LP11], noted here PKP-IDS.
from the prover to the verifier and two challenges transmitted
We first quote and refer to some of the general defini-
from the verifier to the prover. Random choices of prover and
tions given in [CHR+ 18] : Identification scheme, Complete-
verifier are made using the uniform distribution. The protocol
ness, Soundness (with soundness error), Honest-verifier zero-
of identification is summarized in Algorithm 2.
knowledge, and also in [HNO+ 09], [Dam99] : statistically
From Shamir in [Sha89] we have the following results.
hiding commitment, computationally binding commitment. We
Theorem 5.1: PKP-IDS is complete. PKP-IDS is statistically
then apply and adapt these definitions to the Identification
zero knowledge when the commitment scheme Com is com-
scheme base on PKP and give and prove its own properties
putationally binding. PKP-IDS is sound with soundness error
of performance and security. This approach will be more p+1
convenient for presenting the signature scheme in the next 2p when the commitment scheme Com is computationally
binding.
section.
Definition 5.2 (N rounds of PKP-IDS): Let PKP-IDS=
(K EY G EN, P, V ) then PKP − IDSN = (K EY G EN, P N , V N )
A. Preliminaries
is the parallel composition of N rounds of PKP − IDS.
In what follows and as in [CHR+ 18], we assume the Key sizes. The secret key is the permutation π obtained
existence of a non-interactive commitment scheme Com which using a pseudo random generator that takes as input a seed of
50
Algorithm 2 One round of the 5-pass identification scheme So next, we introduce the basic definitions needed. Then,
1: procedures P(sk), V (pk) similarly to the MQ-based signatures and Picnic, we define
2: //Prover setup our scheme, and we finish with a comparison with other
3: P sets R ← Random vector in F p n cryptosystems.
4: P sets σ .seed ← Random seed of λ bits
A. Introduction
5: P sets σ ← Random permutation in Sn using a pseudo-
random generator with σ .seed The classical method of Fiat-Shamir (FS) transforms an in-
6: //Commitment step by the Prover teractive proof of knowledge (identification scheme) into a non
P sets C0 ← Com σ , AR interactive one (signature scheme). This work is a direct appli-
7:
8: P sets C1 ← Com πσ , Rσ cation of this method to get PKP-DSS from PKP-IDS. Fiat-
9: P sends (C0 , C1 ) to V Shamir transform for PKP-IDS. We recall that PKP-IDS the
10: //First challenge by the verifier previously defined identification scheme achieves soundness
11: V sets Ch0 ← c random in F p with soundness error κ = 1+p 2p . We select N the number of
12: V sends Ch0 to P parallel rounds of PKP-IDS such that κ N is negligible in λ .
13: P sets Z ← Rσ + cVπσ and sends Z to V We select two cryptographic hash functions H1 : {0, 1}∗ → FNp
14: V sets Ch1 ← b random bit and H2 : {0, 1}∗ → {0, 1}N . By applying Construction 4.7
15: V sends Ch1 to P in [CHR+ 18], we get PKP-DSS= (K EY G EN, S IGN, V ERIFY).
16: if Ch1 = 0 then See Algorithms 3 and 4.
17: P reveals σ .seed to V A valid signature of a message m by PKP-DSS is then a
18: V accepts if Com σ , Aσ Z = C0 tuple (m, σ0 , σ1 , σ2 ), where σ0 , σ1 , σ2 hold the (vector of paral-
19: else lel) commitments and responses of the non interactive prover.
20: P reveals πσ to V The implicit values h1 = H1 (m, σ0 ) and h2 = H2 (m, σ0 , h1 , σ1 )
V accepts if Com πσ , Z − cVπσ = C1
21: represent the (vector of parallel) challenges of the non inter-
22: end if active verifier.
23: end procedure We get the similar result as Th. 5.1 in [CHR+ 18].
Theorem 6.1: PKP-DSS is Existential-Unforgeable under
Chosen Adaptive Message Attacks (EU-CMA) in the random
λ bits. The size of the public vector V is n log2 (p) bits. The oracle model, if
bit size of the public key (p, A,V ) is: • the search version of the Permuted Kernel problem is
intractable,
log2 (p) + λ + n log2 (p) bits. • the hash functions are modeled as random oracles,
Performance of the scheme. We can now provide the • the commitment functions are computationally binding,
communication complexity of the IDS, where its fraud’s computationally hiding, and the probability that their
probability is p+1 output takes a given value is negligible in the security
2p . Consider that the commitment function
Com used in the protocol, returns values of 2λ bits. The parameter,
• the pseudo-random generators are modeled as random
transfer of the n-vector Z ∈ F p n requires n log2 p Thus, the
fourth passes demand 4λ + (n + 1) log2 p + 1 bits. oracle, and
Note also that, compared to the original scheme of Shamir in • the pseudo-random generators have outputs computation-
[Sha89], we have reduced the complexity in communication by ally indistinguishable from random.
revealing only the seed used to generate the random elements. The proof is exactly the same as in [CHR+ 18].
More precisely, instead of revealing the random permutation B. Quantum analysis of PKP
σ , the prover P only sends its seed sigma.seed.
So, the last pass needs, according to Ch1 , λ bits to reveal Since we are comparing PKP-DSS to other post-quantum
the permutation σ if Ch1 = 0; and log2 (n!) bits to reveal the schemes, it is important to define the security of our scheme
permutation πσ , if Ch1 = 1. against quantum attacks. This can be done by investigating
In total, the weighted average bit complexity of the scheme quantum algorithms for solving PKP. However, till now there
repeated N rounds is given by: are no quantum versions of the known attacks on PKP cited
above IV. Also, there is no gain of considering Grover’s
1
4λ + (n + 1) log2 p + 1 + (λ + log2 (n!)) × N. algorithm because the best attack for solving PKP is much
2 more efficient than the exhaustive search (by a quadratic
VI. D IGITAL SIGNATURE SCHEME (DSS) BASED ON PKP factor).
We present here the main contribution of this work which Moreover, the post-quantum security of the F IAT- SHAMIR
is to construct a DSS i.e. a digital signature scheme, based on transform has been studied in [Unr15], [Unr17]. The author
the PKP problem, from the IDS defined in Section V-B. This of [Unr15] explains that the classic F IAT- SHAMIR transform
construction uses the well-known Fiat Shamir transformation might not be secure against quantum computers. Thus, a
[FS86]. new technique with the extra property of "extractability" was
51
Algorithm 3 Signing process in PKP-DSS Algorithm 4 Verification process in PKP-DSS
1: procedure PKP-DSS.S IGN (m, sk) 1: procedure PKP-DSS.V ERIFY m, pk, S =
R ← H0 sk || m ,
(R, S0 , S1 , S2 )
2: R is a message-dependent
D ← H0 pk || R || m ,
random value 2: D is the randomized
D ← H0 pk || R || m ,
3: D is the randomized message digest
Ch0 ← H1 (D, S0 )
message digest 3:
R(1) , . . . , R(N) ← RG0 R.seed, D
4: 4: Parse Ch0 as Ch0 := (c(1) , . .. , c(N) ), c( j) ∈ F p
5: σ (1) , . . . , σ (N) ← RG1 σ .seed, D 5: Ch1 ← H2 D, S0 , Ch0 , S1
6: for j f rom 1 to N do 6: Parse Ch1 as Ch1 := (b(1) , . . . , b(N) ), b( j) ∈ {0, 1}
( j)
7: C0 = Com σ ( j) , AR( j) , 7:
(1)
Parse S1 as S1 := resp0 || . . . ||resp0
(N)
( j) ( j)
8: C1 = Com πσ ( j) , Rσ ( j) . 8: Parse S2 as S2 :=
(1) (N) (1) (N)
9: COM(j) := C0 , C1
( j) ( j) resp1 || . . . ||resp1 ||C1−b(1) || . . . ||C1−b(N) .
10: end for 9: for j in (1 . . . N) do
( j)
S0 ← H0 COM(1)|| . . . ||COM(N) . Z ( j) := resp0 ,
11: 10:
12: Ch0 ← H1 D, S0 11: if b( j) = 0 then
( j)
13: Parse Ch0 as Ch0 := (c(1) , . . . , c(N) ), c( j) ∈ F p 12: σ ( j) := resp1 ,
( j)
C0 := Com σ ( j) , Aσ ( j) Z ( j)
14: for j f rom 1 to N do 13:
( j)
15: Z ( j) ← Rσ ( j) + c( j)Vπσ ( j) , 14: else ( j)
16:
( j)
resp0 := Z ( j) . 15: πσ ( j)=resp1
( j)
C1 = Com πσ ( j) , Z ( j) − c( j)Vπσ ( j)
16:
17: end for
18:
(1) (N)
S1 ← resp0 || . . . ||resp0 = Z (1) || . . . ||, Z (N) .
17: end if
( j) ( j)
19: Ch1 ← H2 D, S0 , Ch0 , S1 18: COM(j) := C0 , C1
20: Parse Ch1 as Ch1 := (b(1) , . . . , b(N) ), b( j) ∈ {0, 1} 19: end for
S00 ← H0 COM(1) || . . . ||COM(N) .
20:
21: for j in (1 . . . N) do
22: if b( j) = 0 then 21: return S00 = S0 .
( j) 22: end procedure
23: resp1 ← σ ( j) .
24: else
( j)
25: resp1 ← πσ ( j) .
26: end if By considering the scheme where the fraud’s probability is
27: end for Pf = p+1
2p . We require that
(1) (N) (1) (N)
S2 ← resp1 || . . . ||resp1 ||C1−b(1) || . . . ||C1−b(N) .
28:
PfN ≤ 2−λ ,
29: Return R, S0 , S1 , S2 .
30: end procedure as an attacker could perform a preimage search to control the
challenges. Hence, we get that N ≥ λ / log2 ( p+1 2p ).
We begin to present how to compute the complexity in
developed to obtain a quantum-secure transform. bits. Recall that the signature is composed of R the message-
In [Unr17], D. U NRUH justifies that the F IAT- SHAMIR trans- dependent random value, S0 , S1 and S2 , where S0 is the
form is secure under certain conditions. Currently, it seems hashed value of the commitments of all rounds, S1 is formed
impractical to apply the Unruh transform since the obtained by the first responses, and S2 is the concatenation of the some
scheme is costly in terms of signature’s size. Therefore, we commitments and the second responses to the challenges.
can keep the initial F IAT- SHAMIR as long as there is neither For S0 which is a hashed value, it costs 2λ bits. S1 depends
perfect proof nor quantum attack. on the size of Z, so it is in N × n log2 p. For S2 , we present
next each case:
C. Performance of the scheme • b=0: The signer reveals one seed sigma.seed (similarly to
2) as a response. It costs the seed size which is presented
Our main goal is to find the best parameters which can by λ bits. In addition to the size of the commitment C1 ,
ensure the minimal size of a signature. We show, in the we have in average:
next sections, that the PKP-based signature scheme provides
a signature’s size less than the other signature schemes, 1 3
A = Size(C1 ) + Size(resp1 ) = λ .
precisely MQDSS [CHR+ 18] and Picnic [CDG+ 17]. 2 2
• b=1: The signer reveals the permutation πσ ( j) as a
Signature size: We said that our signing scheme is con- response resp1 to the challenge b( j) . By adding also the
structed from the iterations of the IDS (given in 2). Now, to commitment C0 of size 2λ bits, we have in total:
have the total cost, it is important to define the number of 1
rounds N needed to achieve EU-CMA for λ bits of security. B = 2λ + log2 (n!) .
2
52
We have thus the following signature size: VI-C and the criteria defined above. Furthermore, our
size o f R size o f S0
parameters raise a secure scheme against all the attacks
z}|{ z}|{ described in Section IV, mainly, against the most efficient
2λ + 2λ + N n log2 (p) + A + B . attack: the algorithm of PATARIN -C HAUVAUD [PC93].
| {z }
size o f S1 and S2
How parameters affect performance As we said previ-
Parameters λ p n m Iterations number Best classical
ously, the DSS is mainly affected by the following set of Set N attack
parameters: (p, n, m). We now explicitly detail the choice PKP-DSS-128 128 977 61 28 129 2130 op.
of parameters. Recall that firstly the IDS [Sha89] was PKP-DSS-192 192 1409 87 42 193 2198 op.
designed to suit small devices. Thus, A. S HAMIR proposed PKP-DSS-256 256 1889 111 55 257 2262 op.
p = 256. Nowadays, with the 64−bit computer architecture, TABLE I
PKP-DSS PARAMETERS SETS
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. Next, we compare PKP-DSS to MQDSS [CHR+ 18] and
A solution of a random instance of PKP is to find a Picnic [CDG+ 17]. We consider the public/secret (pk/sk)
kernel n-vector (Vπ ) with distinct coordinates in F p . Hence, keys size and the signature size, for different security levels.
the probability to find such vector shouldn’t be too small.
Also in [Sha89], A. S HAMIR estimated n to be between Security level Parameters Sets Secret key Public key Signature
size (Bytes) size (Bytes) size (KBytes)
32 and 64. Later on, several attacks [BCCG92], [PC93]
128
shows that the choice n = 32 is not recommended for strong PKP-DSS-128 16 93 16.83
security requirements. So, to find an n-vector with no MQDSS-31-48 16 46 16.15
double in F p , and by considering the Birthday Paradox, we Picnic-L1-FS 16 32 33.2
√
keep the choice of n around 64, in addition to n ≈ O p .
192
PKP-DSS-192 24 139.1 38.02
On the other hand, the probability of an arbitrary vector MQDSS-31-64 24 64 33.23
to be in the kernel of the matrix A ∈ Mm×n whose rank Picnic-L3-FS 24 48 74.9
is equal to m, is p−m . Moreover, if the n-vector V has
256
no double, the cardinal of its orbit under the possible PKP-DSS-256 32 184.4 67.49
MQDSS-31-88 32 87 60.28
permutations π is n!. Thus, in order to get one solution, Picnic-L5-FS 32 64 129.7
we have the following constraint: n! ≈ pm . TABLE II
Hence, following these criteria, we have in total: C OMPARISON OF DIFFERENT SCHEMES
p ≈ O n2 ,
n! ≈ nn ≈ pm . One can conclude that the IDS based on PKP constitutes
one of the most efficient schemes.
This leads to take m ≈ n log(n)/log(p) ≈ n/2.
How to choose the security parameter λ . Recall
that, the security parameter λ controls the number of VII. C ONCLUSION
iterations N = λ / log2 ( p+1
2p ) performed to achieve a security In this article, we discussed some of the most well-known
level needed. It also defines the output of the hash and technique for solving PKP. Particularly, we drew attention
commitments functions which is in 2λ , in addition to the to the fact that, the Approach of PATARIN -C HAUVAUD
seeds length. [PC93] is the most efficient attack on PKP.
In general, the hash and commitment functions require Moreover, our main motivation is the construction of
collision resistance, preimage resistance, and/or second a post-quantum secure cryptosystem. In [Sha89], a Zero-
preimage resistance. Thus, in this article, to reach for knowledge identification scheme (ZK-IDS) was introduced.
example a security of 128 bits, we initiate λ to be exactly A well-known method, namely F IAT- SHAMIR technique
of 128 bits. As well for the others security levels (192 and [FS86], is used to turn an IDS into a digital signature
256). scheme (DSS).
However, as shown in [GS94], it is always possible to The authors of [CHR+ 18], presents a DSS, named
reduce this choice of 256-bit hash values while keeping a MQDSS. It was built from an IDS based on the MQ prob-
security level of 128 bits. Yet, to compare PKP-DSS to the lem (Multivariate quadratic equations solving problem).
other schemes (as MQDSS) we keep this doubling. Note Thus, they give several sets of parameters which provide
that, the optimization of [GS94] can be applied to PKP- post-quantum security.
DSS as well to the other schemes (MQDSS, Picnic,...). As well, Picnic [CDG+ 17] is designed to be secure against
In the following table we present several parameters classical and quantum attacks. It was also constructed
sets for different levels of security. We define these from a Zero-knowledge identification scheme to match
parameters by considering the formulas given in Section different security levels.
53
Hence, similarly to the technique used to build these [GJ79] Michael R Garey and David S Johnson. Computers and
schemes, we have constructed a DSS based on the PKP intractability: a guide to np-completeness, 1979.
[GS94] Marc Girault and Jacques Stern. On the length of crypto-
problem. We utilized the ZK-authentication scheme pre- graphic hash-values used in identification schemes. In Annual
sented in [Sha89] to deduce the signature scheme. In order International Cryptology Conference, pages 202–215. Springer,
to compare this latter to the other schemes, we have tested 1994.
[HNO+ 09] Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer
the most known techniques to solve PKP. Reingold, and Salil Vadhan. Statistically hiding commitments
We finally conclude several sets of parameters given in and statistical zero-knowledge arguments from any one-way
VI-C which provides 128, 192 and 256 bits of classical function. SIAM Journal on Computing, 39(3):1153–1218,
2009.
security. Mainly, we conclude that the DSS based on [JJ01] Éliane Jaulmes and Antoine Joux. Cryptanalysis of pkp:
PKP gives signatures with a size comparable to the ones a new approach. In International Workshop on Public Key
in MQDSS and smaller than the ones given by Picnic. Cryptography, pages 165–172. Springer, 2001.
[JL01] Antoine Joux and Reynald Lercier. “chinese & match”, an
Consequently, this is what makes from this PKP-DSS a alternative to atkin’s “match and sort” method used in the
competitive scheme to the other related cryptosystems. sea algorithm. Mathematics of computation, 70(234):827–836,
2001.
ACKNOWLEDGMENT [LP11] Rodolphe Lampe and Jacques Patarin. Analysis of some
natural variants of the pkp algorithm. IACR Cryptology ePrint
My sincere gratitude and appreciation go to my Archive, 2011:686, 2011.
[NIS] Security strength categories. https://csrc.nist.gov/CSRC/
supervisos, Prof. Jacques Patarin and R.D Jean-Charles media/Projects/Post-Quantum-Cryptography/documents/
Faugère for their valuable comments and suggestions. call-for-proposals-final-dec-2016.pdf.
Our continuous discussion, their immense knowledge and [PC93] Jaques Patarin and Pascal Chauvaud. Improved algorithms
for the permuted kernel problem. In Annual International
thought provoking questions helped me to get results of Cryptology Conference, pages 391–402. Springer, 1993.
better quality. Also, i would especially like to show my [Sha89] Adi Shamir. An efficient identification scheme based on per-
deepest thanks for A.P Ludovic Perret for sharing his muted kernels. In Conference on the Theory and Application
of Cryptology, pages 606–609. Springer, 1989.
enormous experiences and illuminating views on all the [Unr15] Dominique Unruh. Non-interactive zero-knowledge proofs in
issues related to my Phd. His professional and aspiring the quantum random oracle model. In Annual International
guidance pushed me to widen my work from different Conference on the Theory and Applications of Cryptographic
Techniques, pages 755–784. Springer, 2015.
perspectives. [Unr17] Dominique Unruh. Post-quantum security of fiat-shamir. In
I take this opportunity to express thanks, to Mr. Gilles International Conference on the Theory and Application of
Macario-Rat for also helping me to conduct this PhD Cryptology and Information Security, pages 65–95. Springer,
2017.
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.
R EFERENCES
[BBBV97] Charles H Bennett, Ethan Bernstein, Gilles Brassard, and
Umesh Vazirani. Strengths and weaknesses of quantum
computing. SIAM journal on Computing, 26(5):1510–1523,
1997.
[BCCG92] Thierry Baritaud, Mireille Campana, Pascal Chauvaud, and
Henri Gilbert. On the security of the permuted kernel
identification scheme. In Annual International Cryptology
Conference, pages 305–311. Springer, 1992.
[CDG+ 17] Melissa Chase, David Derler, Steven Goldfeder, Claudio Or-
landi, Sebastian Ramacher, Christian Rechberger, Daniel Sla-
manig, and Greg Zaverucha. Post-quantum zero-knowledge
and signatures from symmetric-key primitives. In Proceed-
ings of the 2017 ACM SIGSAC Conference on Computer and
Communications Security, pages 1825–1842. ACM, 2017.
[CHR+ 18] Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona
Samardjiska, and Peter Schwabe. Mqdss specifications, 2018.
[Dam99] Ivan Damgård. Commitment Schemes and Zero-Knowledge
Protocols, pages 63–86. Springer Berlin Heidelberg, Berlin,
Heidelberg, 1999.
[FS86] Amos Fiat and Adi Shamir. How to prove yourself: Prac-
tical solutions to identification and signature problems. In
Conference on the Theory and Application of Cryptographic
Techniques, pages 186–194. Springer, 1986.
[Geo92] Jean Georgiades. Some remarks on the security of the
identification scheme based on permuted kernels. Journal
of Cryptology, 5(2):133–137, 1992.
54