Chapter 4

Digital Signature Scheme

4.1 Introduction
Digital signatures are asymmetric cryptographic schemes which aim at data
integrity and authenticity. There are some similarities to message authenti-
cation codes, but digital signatures are verified using a public key. Successful
verification shows that the data is authentic and has not been tampered with.
Since the private key is exclusively controlled by the signer, digital signatures
achieve not only data integrity and authenticity, but also non-repudiation.
Signatures have applications beyond integrity protection, for example in en-
tity authentication protocols.
In this section, we define the concept of digital signature schemes.

Definition 4.1 (Digital Signature Scheme). A digital signature scheme

(DSS) consists of

• A message space M.

• A key space K = Kpk × Ksk (pairs of public (signing) and secret (veri-
fication) keys).

• A randomized key generation algorithm [Link](1λ ) that takes a se-

curity parameter λ as input and outputs a pair of keys (pk, sk).

• A signing algorithm Sign = {Signsk | sk ∈ Ksk } which may be ran-

domized. It takes a secret signing key and a message m as input, and
outputs the signature σ.

54
 • A verification algorithm Verify = {Verifypk | pk ∈ Kpk } that takes a
public verification key and a signature σ and a message m as input
and outputs 1 if the signature is valid or 0 otherwise.

Note that all algorithms above must run in polynomial time.

There are three main approaches in constructing DSS in code-based cryp-

tography:

1. Hash-&-Sign Signature

2. Zero-Knowledge (ZK):
Fiat-Shamir
Identification protocol −−−−−−−−−−−−−−→ DSS
Transformation
3. Schnorr-type Signature

4.2 Hash-&-Sign Signature

The only unbroken signature scheme based on the Niederreiter PKE was
introduced by Courtois et al. [CFS01]. The security of CFS scheme can be
reduced to the hardness of SD problem.

The idea of the CFS DSS is to repeatedly hash the document, randomized
by a counter of bit-length r, until the output is a decryptable ciphertext.
The signer uses his secret key to determine the corresponding error-vector.
Together with the current value of the counter, this error vector will then
serve as signature.

Let φn,t be an invertible function such that

φn,t : {0, 1}l → BH,Fq (n, t)

 
where l = log2 |BH,Fq (n, t)| .

CFS Digital Signature Scheme.

Parameters: m, n, k, t, r ∈ N where n > k and n >> t.

[Link](1λ ): Given parameters m, n, k, t, r, generate the following matrices:

• H: (n − k) × n parity check matrix of a binary irreducible Goppa codes

C with parameters n = 2m , k = n − mt and dH (C) ≥ 2t + 1.

55
 • S: (n − k) × (n − k) random binary invertible matrix.

• P : n × n random permutation matrix.

Consider a public hash function H. Then, output the public key pk = Hpub =
SHP and the secret key sk = (S, DC , P ).

Sign(m, sk, m): To sign a message m ∈ Fk2 :

1. Compute z = H(m)
$
2. Choose v ← Fr2

3. Compute s = H(zkv)

4. Compute w = DC (s[S T ]−1 ). If s[S T ]−1 is not decodable, repeat Step

2 to Step 4 until s[S T ]−1 is decodable.

5. e = w[P T ]−1

6. σ = (φ−1
n,t (e)kv)

Output the signature σ.

Verify(σ, pk, m): To verify a signature σ:

1. Compute e = φn,t φ−1

n,t (e)

T
2. s1 = eHpub

3. s2 = H (H(m)kv)

If s1 = s2 , then accept the signature σ; else reject σ.

Correctness of
CFS DSS. Note that e = w[P T ]−1 ⇔ eP T = w. Since

w = DC s[S T ]−1 , this implies that

wH T = s[S T ]−1 ⇔ wH T S T = s ⇔ s = eP T H T S T = eHpub

T
= s1 .

Also,
s2 = H (H(m)kv) = H(zkv) = s.
Therefore s1 = s = s2 .

56
The average number of attempts needed to reach a decodable syndrome can
be estimated by comparing the total number of syndromes to the number of
efficiently correctable syndromes:
   
Pt n Pt n
i=0 i=0
t t nt /t! 1
n−k
= mt
≈ = .
2 2 nt t!
So each syndrome has a probability of 1/t! to be decodable, which can be
tested in about t2 m3 binary operations. Therefore, the CFS DSS needs about
t2 m3 t! operations to generate a signature.

Hardness of CFS DSS. Courtois et al. claimed that the security of CFS
relies on the difficulty of List Bounded-Distance Decoding problem, which
can be reduced to the hardness of SD problem. We give the definition for the
List Bounded-Distance Decoding problem and give the rough idea of forging
a signature. For more information, we refer readers to [CFS01].

Problem 4.2 (List Bounded-Distance Decoding (LBBD) Problem). Given

an integer d, a binary (n − k) × n matrix H such that every d − 1 columns
 d−1 of
H are linearly independent, a subset S ⊂ Fn−k

2 , and and integer w ≤ 2 .
The List Bounded-Distance Decoding (LBBD) problem needs to determine
a vector v ∈ BH,Fq (n, w) such that vH T ∈ S.

An adversary who wishes to forges a signature with message m with the

public key HpubT , he has to find a word e of weight t such that its syndrome,

sHpub (e) lies in the set of the following set:

n o
(n−k)
S = H(H(m)kv) : v ∈ F2 .

If the adversary can solve LBBD(n, k, d, t, S), then he can determine a vector
e of weight t and forge a signature.

Strengths and Weaknesses of CFS DSS using binary Goppa codes.

1. Strengths:

• No attack is known, secure up to date (from 2001 to 2021!)

2. Weaknesses:

• Require a lot of repetitions to generate a decodable signatures

• Very large public key size (1.15 MB)

57
Discussions on Hash-&-Sign DSS.

1. Constructing DSS via this approach is generally difficult, as we require

suitable codes with acceptable repetitions to generate a decodable sig-
nature.

2. There are some other constructions of code-based signature via this

approach, for example Wave [DAST19] and Tsunami [BP18] which
their security are still at question.

3. For rank metric, the RankSign DSS [GRSZ19] was constructed. How-
ever, there are some security issues on RankSign [DAT18].

4.3 Signatures from Identification Protocol

In this section, we introduce the concept of Zero-Knowledge identification
protocol. Then we give some examples for code-based identification protocols
and their corresponding signature schems.

Definition 4.3 (Zero-Knowledge (Informal Def.)). A zero-knowledge proof

(ZKP) is a digital protocol that allows for data to be shared between two
parties without the use of a password or any other information associated
with the transaction.
To be more precise, a ZKP is a method by which one party (the prover
P) can prove to another party (the verifier V) that they know a value x,
without conveying any information apart from the fact that they know the
value x. The essence of zero-knowledge proofs is that it is trivial to prove
that one possesses knowledge of certain information by simply revealing it;
the challenge is to prove such possession without revealing the information
itself or any additional information.
In its most basic sense, a zero-knowledge proof can be thought of as a protocol
through which a digital authentication process can be facilitated without
the use of any passwords or other sensitive data. As a result of this, no
information, either from the sender’s or receiver’s end, can be compromised
in any way.

Example 4.4 (The Alibaba Cave). There is a well-known story presenting

the fundamental ideas of zero-knowledge proofs. It is common practice to
label the two parties in a zero-knowledge proof as Peggy (the prover P of
the statement) and Victor (the verifier V of the statement).

58
In this story, Peggy has uncovered the secret word used to open a magic door
in a cave. The cave is shaped like a ring, with the entrance on one side and
the magic door blocking the opposite side. Victor wants to know whether
Peggy knows the secret word; but Peggy, being a very private person, does
not want to reveal her knowledge (the secret word) to Victor or to reveal the
fact of her knowledge to the world in general.
They label the left and right paths from the entrance A and B. First, Victor
waits outside the cave as Peggy goes in. Peggy takes either path A or B;
Victor is not allowed to see which path she takes. Then, Victor enters the
cave and shouts the name of the path he wants her to use to return, either
A or B, chosen at random. Providing she really does know the magic word,
this is easy: she opens the door, if necessary, and returns along the desired
path.

However, suppose she did not know the word. Then, she would only be
able to return by the named path if Victor were to give the name of the
same path by which she had entered. Since Victor would choose A or B at
random, she would have a 50% chance of guessing correctly. If they were to
repeat this trick many times, say 20 times in a row, her chance of successfully
anticipating all of Victor’s requests would become vanishingly small (≈ 2−20 ,
about one in a million).
Thus, if Peggy repeatedly appears at the exit Victor names, he can conclude
that it is extremely probable that Peggy does, in fact, know the secret word.
Definition 4.5 (Identification Protocol). In cryptography, an identification
protocol is a type of ZKP. Like all zero-knowledge proofs, it allows one party,
the Prover, to prove his identity (who possess secret information) to another
party, the Verifier, without revealing to Verifier what that secret information
is.
Example 4.6 (Discrete log of a given value). Peggy wants to prove to Victor
that she knows the discrete log of a given value in a given group.

59
For example, given a value y, a large prime p and a generator g, she wants to
prove that she knows a value x such that g x mod p = y, without revealing
x. Indeed, knowledge of x could be used as a proof of identity, in that Peggy
could have such knowledge because she chose a random value x that she
didn’t reveal to anyone, computed y = g x mod p and distributed the value
of y to all potential verifiers, such that at a later time, proving knowledge of
x is equivalent to proving identity as Peggy.
The protocol proceeds as follows: in each round, Peggy generates a ran-
dom number r, computes C = g r mod p and discloses this to Victor. After
receiving C, Victor randomly issues one of the following two requests: he
either requests that Peggy discloses the value of r, or the value of (x +
r) mod (p − 1)(x + r) mod (p − 1). With either answer, Peggy is only dis-
closing a random value, so no information is disclosed by a correct execution
of one round of the protocol.
Victor can verify either answer; if he requested r, he can then compute
g r mod p and verify that it matches C. If he requested (x+r) mod (p − 1),
he can verify that C is consistent with this, by computing g (x+r) mod (p−1)
mod p and verifying that it matches C · y mod p. If Peggy indeed knows
the value of x, she can respond to either one of Victor’s possible challenges.
If Peggy knew or could guess which challenge Victor is going to issue, then she
could easily cheat and convince Victor that she knows x when she does not:
if she knows that Victor is going to request r, then she proceeds normally:
she picks r, computes C = g r mod p and discloses C to Victor; she will be
able to respond to Victor’s challenge. On the other hand, if she knows that
Victor will request (x + r) mod (p − 1), then she picks a random value r0 ,
0 0
computes C 0 = g r · (g x )−1 = g r · y −1 mod P , and discloses C 0 to Victor as
the value of C that he is expecting. When Victor challenges her to reveal
(x + r) mod (p − 1), she reveals r0 , for which Victor will verify consistency,
0
since he will in turn compute g r mod p which matches C 0 .
However, if in either one of the above scenarios Victor issues a challenge other
than the one she was expecting and for which she manufactured the result,
then she will be unable to respond to the challenge under the assumption
of infeasibility of solving the discrete log for this group. If she picked r and
disclosed C = g r mod p, then she will be unable to produce a valid (x + r)
mod (p − 1) that would pass Victor’s verification, given that she does not
know x. And if she picked a value r0 that poses as (x + r) mod (p − 1),
then she would have to respond with the discrete log of the value that she
disclosed âĂŞ but Peggy does not know this discrete log, since the value C
she disclosed was obtained through arithmetic with known values, and not

60
 $
Prover’s secret sk = (x ← Z+ )
pk = (a large prime p, a generator g of Zp , y = g x mod p)
Prover P Verifier V
$
r ← [0, p − 1]
C = g r mod p
−−−−−−−−−−−−−−−−−−→
←−−−−−−−−−−−−−−−−−−
$
b ← {0, 1}

if b = 0: z = (x + r) mod (p − 1)
−−−−−−−−−−−−−−−−−−→
?
(C · y) mod p ≡ g z mod p
if b = 1: r
−−−−−−−−−−−−−−−−−−→
?
C ≡ g r mod p

by computing a power with a known exponent.

Thus, a cheating prover has a 0.5 probability of successfully cheating in one
round. By executing a large enough number of rounds, the probability of a
cheating prover succeeding can be made arbitrarily low.

Number of Rounds. We need to choose the number of rounds δ in order

to decrease the impersonation probability to our needs. As far as it concern
the identification protocols, for Example 4.6 the impersonation probability
of one single round is 0.5. In general, to reach a security level λ with an
impersonation probability of Primp , i.e. to compute the number of δ, we
need to set δ = logPrimp (2−λ ). This results in δ = 128 for Example 4.6 to
achieve λ = 128-bit security.
As mentioned above, the Fiat-Shamir transform [FS86] can turn any ZKP
identification scheme into a signature scheme. In particular, the Fiat-Shamir
transform allows to replace the interactive step with a non-interative random
oracle access, by considering a cryptographic hash function. We use Example
4.6 to illustrate how to apply this transformation.
Example 4.7 (Signature Scheme from Example 4.6). Parameters: p, δ ∈ N.
[Link](1λ ): Given parameters p, δ, generate the following matrices:

• p: a large prime,

61
 • g: a generator of Zp ,

• x: a random positive integer.

Consider a public cryptographic hash function H. Then, output the public

key pk = (p, g, y = g x mod p) and the secret key sk = x.

Sign(m, sk, m): To sign a message m ∈ Fk2 :

1. For i = 1, . . . , δ:
$
• Choose randomly ri ← [0, p − 1]
• Compute Ci = g ri mod p

2. Compute cmt = (C1 , . . . , Cδ )

3. Compute ch = H (cmtkm)

4. For i = 1, . . . , δ:

• if chi = 0, then rspi = (x + r) mod (p − 1);

• if chi = 1, then rspi = r.

Output the signature σ = (cmt, ch, rsp).

Verify(σ, pk, m): To verify a signature σ:

1. If ch 6= H (cmtkm), then reject σ.

2. For i = 1, . . . , δ:

• if chi = 0 and (cmti · y) mod p 6≡ g rspi mod p, reject σ;

• if chi = 1 and cmti 6≡ g rspi mod p, reject σ.

Else, accept the signature σ.

Remark 4.8. The Fiat-Shamir transformation to convert an identification
protocol to a signature scheme is also known as commit-and-challenge ap-
proach.

We can construct identification protocol which its hardness is based on hard

problems in coding theory. There are a few code-based identification protocol
and signature schemes derived, such as Stern’s identification protocol [Ste94],
Veron identification protocol [V9́7] and CVE [CVA11] identification protocol.

62
 Stern’s Identification Protocol and Signature Scheme
We first describe the specification for Stern’s identification protocol.
 
$
Prover’s secret sk = e ← BH,F2 (n, w)
 
$ (n−k)×n
pk = H ← F2 , s = eH T
Prover P Verifier V
$
y← Fn2
random n × n
permutation
matrix P
c0 = H P kyH T

c1 = H (yP )
c2 = H ((y + e)P )
−−−−−−−−−−−−−−→
←−−−−−−−−−−−−−−
$
b ← {0, 1, 2}

if b = 0: yP , eP
−−−−−−−−−−−−−−→ Accept if
wtH (eP ) = w
c1 = H(yP )
c2 = H(yP + eP )
if b = 1: y + e, P
−−−−−−−−−−−−−−→ Accept if
c0 = H(P k(y + e)H T + s)
c2 = H((y + e)P )
if b = 2: y, P
−−−−−−−−−−−−−−→ Accept if
c0 = H(P kyH T )
c1 = H(yP )

Impersonation Attacks. An attacker executes the protocol with a verifier

tries to give answers the verifier will accept. It is impossible to give commit-
ments that can be opend for all 3 values of b. Without the knowledge of the
secret e, we want to calculate the probability of success. We consider the
following choices:
$
Choice 1. Pick y, P and e0 ← BH,F2 (n, w).

63
 Send c0 = H(P kyH T ), c1 = H(yP ) and c2 = H((y + e0 )P ).
If b = 0, send yP and e0 P , the verification process will pass.
If b = 2, send y and P , the verification process will pass.
But when b = 1, send y + e0 and P , then c0 6= H(P k(y + e0 )H T + s).
$
Choice 2. Pick y + e0 , P and e0 ← BH,F2 (n, w).
Send c0 = H(P k(y + e0 )H T + s), c1 = H(yP ) and c2 = H((y + e0 )P ).
If b = 0, send yP and e0 P , the verification process will pass.
If b = 1, send y + e0 and P , the verification process will pass.
But when b = 2, send y + e0 and P , then c0 6= H(P k(y + e0 )H T ).
$
Choice 3. Pick y + e0 , P and e0 ← Fn2 such that s = e0 H T .
Send c0 = H(P kyH T ), c1 = H(yP ) and c2 = H((y + e0 )P ).
If b = 1, send y + e0 and P , the verification process will pass.
If b = 2, send y and P , the verification process will pass.
But when b = 0, send yP and e0 P , then wtH (e0 P ) > w.

Therefore, without the knowledge of the secret e, the probability of success

is at most Primp = 32 . This results in δ = log 2 (2−128 ) = 218 rounds for
3
128-bit security level.

Stern’s Signature Scheme.

Parameters: n, k, w, δ ∈ N.

[Link](1λ ): Given parameters n, k, w, δ, generate the following:

$ (n−k)×n
• H ← F2 ,
$
• e ← BH,F2 (n, w).

Consider a public hash function H. Then, output the public key pk =

T


H, s = eH and the secret key sk = e.

Sign(m, sk, m): Let δ be the number of rounds for the Stern signature. To
sign a message m ∈ Fk2 , for i = 1, . . . , δ:

$
1. Choose randomly yi ← Fn2 .

64
 2. Choose a random n × n permutation matrix Pi .

3. Compute

ci,0 = H(P kyH T ), ci,1 = H(yP ), ci,2 = H((y + e)P ).

Let cmt = (c1,0 , c1,1 , c1,2 , . . . , cδ,0 , cδ,1 , cδ,2 ). Compute

ch = H(cmtkm) ∈ F2δ
2 .

Let f (v, w) be the function that maps the bits v and w to the set {0, 1, 2}
following the rule:

00 7→ 0, 01 7→ 1, 10 7→ 2, 11 7→ either 0, 1, 2 in a cyclic fashion.

For i = 1, . . . , δ:

• Let bi = f (ch2i−1 , ch2i ).

• If bi = 0, then rspi = (yP, eP ).

• If bi = 1, then rspi = (y + e, P ).

• If bi = 2, then rspi = (y, P ).

Output the signature σ = (cmt, rsp).

Verify(σ, pk, m): To verify a signature σ:

1. Compute ch = H(cmtkm).

2. For i = 1, . . . , δ and j = 0, 1, 2:

• Compute bi = f (ch2i−1 , ch2i ).

• For bi = 0, rspi,1 = yi Pi and rspi,2 = ePi .
If wtH (rspi,2 ) 6= w or ci,1 6= H(rspi,1 ) or ci,2 6= H(rspi,1 + rspi,2 ),
then reject the signature.
• For bi = 1, rspi,1 = yi + e and rspi,2 = Pi .
If ci,0 6= H(rspi,2 krspi,1 H T +s) or ci,2 6= H(rspi,1 rspi,2 ), then reject
the signature.
• For bi = 2, rspi,1 = yi and rspi,2 = Pi .
If ci,0 6= H(rspi,2 krspi,1 H T ) or ci,1 6= H(rspi,1 rspi,2 ), then reject
the signature.

65
Else, accept the signature σ.
Strengths and Weaknesses of DSS from ZKP.

1. Strengths:
• Very small public key size (public key can be vectors only)
2. Weaknesses:
• Inefficient, as the the protocol requires δ rounds of repetitions
• Large signature size due to the repetitions
• Security also relies on Primp

Discussions on DSS from ZKP.

1. Constructing DSS via this approach is quite straightforward, when we

have a code-based identification protocol.
2. For rank metric, the analogous Veron and CVE identification protocol
and DSS were constructed.
3. For Lee metric, so far there is no construction on the identification
protocol and DSS based on this approach.

4.4 Schnorr-type Signature Schemes

In this section, we introduce the Schnorr-type signature schemes in code-
based settings. We first recall the specification for Schnorr signature scheme
[Sch90].
Schnorr Signature Scheme.
Parameters: q ∈ N where q is prime.
[Link](1λ ): Given parameter q, generate the following:

• a group G of prime order q with generator g.

$
• x ← Z+
q

Consider a public hash function H : {0, 1}∗ → Zq . Then, output the public
key pk = (g, y = g x ) and the secret key sk = x.
Sign(m, sk, m): To sign a message m:

66
 $
1. Choose k ← Z+
q .

2. Compute r = g k .

3. Compute c = H(rkm).

4. Compute s = k − xc.

Output the signature σ = (s, c).

Verify(σ, pk, m): To verify a signature σ, compute rv = g s y c . If c =

H(rv kM ), then accept the signature σ; else reject σ.

Correctness of Schnorr DSS. Note that

rv = g s y c = g k−xc g xc = g k = r.

Hence c = H(rkm) = H(rv km).

Remark 4.9. In fact, the Schnorr DSS was constructed by applying Fiat-
Shamir transformation to Schnorr’s identification protocol. However, due
to its popularity and straightforwardness of its construction, some code-
based DSS is constructed by considering the Schnorr DSS directly without
referring back to Schnorr’s identification protocol. Sometimes, this approach
is referred as the Schnorr-Lyubashevsky’s framework.

We now introduce the follwing code-based DSS constructed via the Schnorr’s
approach. We first discuss the similarity in the idea of construction.

Discrete Log Syndrome Decoding

Hard Problem
y = gx s = eH T
$
Secret Key x e ← BH,F2 (n, w)
Public Key y, g s, H
$
Ephemeral Key k u ← BH,F2 (n, w)
r = gk y = uH T
Commit
c = H(rkm) c = H(ykm)
Challenge s = k − cx z =u−c?e
yv = zH T + c ∗ s
Verify rv = g s y c
wtH (s) = ?

67
 Discussions on adaptations of Schnorr’s Signature in Code-based
Settings. One of the key features for the above adaptations to work, is to
ensure that:
c ? e ∈ Fn2 and c ∗ s = c ∗ (eH T ) = (c ? e)H T .
There are two approaches to achieve the above.

Method I. This approach was suggested in [FRX+ 17], and named as RaCoSS
(Random Code-based Signature Scheme).
Suppose that the hash function H outputs k-dimensional vectors, i.e.
$
c ∈ Fk2 . Then, instead of considering e ← BH,F2 (n, w), we choose
 ran-

e1
$  ..
domly e1 , . . . , ek ← BH,F2 (n, w) and form the matrix E =  . ∈


ek
k×(n−k)
Fk×n
2 . Then the public key will include S = EH T
∈ F2 .
There-
fore, we can define ? and ∗ as the usual matrix multiplication. We thus
have
c ? E = cE ∈ Fn2 and c ∗ S = c EH T = (cE)H T = (c ? E)H T .
 

Method II. This approach was suggested by Persichetti [Per18].

Suppose that the hash function H outputs k-dimensional vectors, i.e.
c ∈ Fk2 . Let n = 2k, and we consider H to be a parity-check matrix
for a [2k, k]-ideal code, generated by h and P = X k + 1. When we
$
consider e ← BH,F2 (n, w), we have e = (e1 , e2 ) where e1 , e2 ∈ Fk2 .
Then, we have s = eH T = (e1 , e2 )H T = e1 + e2 h mod P .
We define ? : Fk2 × F2k 2k
2 → F2 as

c ? e = c ? (e1 , e2 ) := (ce1 mod P, ce2 mod P ).

Furthermore, we define ∗ : Fk2 × Fk2 → Fk2 as
c ∗ s = cs mod P.
Therefore, we have
c ? e = (ce1 , ce2 ) ∈ Fn2 ,
c ∗ s = c ∗ (e1 + e2 h) = c(e1 + e2 h) mod P
= ce1 + ce2 h mod P = (ce1 , ce2 )H T
= (c ? e)H T .

68
Unfortunately, these two DSS are both cryptanalyzed in [BHLP17] and
[SBC19] respectively. Here, we will only illustrate the cryptanalysis on the
RaCoSS scheme.

Cryptanalysis on RaCoSS. Assume that H = [H1 | H2 ] where H1 ∈

GLn−k (F2 ). For any message m:

1. Choose any arbitrary u ∈ Fn2 and compute y = uH T

2. Compute c = H(ykm).
(n−k)
3. Compute z1 = (uH T − cS)[H1T ]−1 . Note that z1 ∈ F2 .

4. Let z = (z1 k0, . . . , 0) ∈ Fn2 .

5. Output (c, z) as forgery.

In the Verify algorithm of RaCoSS, the verifier needs to check whether

? ?
wtH (z) ≤ th and c = H(yv km). Their choice of parameters are: n = 2400,
k = 2060, n − k = 340, th = 1548. From this forgery, the signature (c, z)
satisfies:

wtH (z) = wtH (z1 ) ≤ n − k = 340 < th = 1548,

 T 
T H1
yv = zH + cS = (z1 , 0k ) + cS
H2T
= z1 H1T + 0n−k + cS
= uH T − cS + cS
= uH T = y
⇒ c = H(ykm) = H(yv km).

Therefore, this is a successful forgery of signature.

Strengths and Weaknesses of Schnorr-type DSS.

1. Strengths:

• Public key size can be small, when only vectors are considered
• Signature size can be small as compared to DSS from identification
protocol

2. Weaknesses:

69
 • Structurally hard to construct a secure one

Discussions on Schnorr-type DSS.

1. There are several constructions trying to overcome the weaknesses of

Schnorr-type DSS in the Hamming metric. Unfortunately, there is no
secure one up-to-date.

2. Some approaches to construct the Schnorr-type DSS based on the “Re-

stricted SD problem are proposed. However, its security is still at
question.

3. For rank metric, there are several constructions based on this approach,
such as Durandal [ABG+ 19b], MURAVE [LT20b] and RPS [LT20a].
These DSS are based on the RSD problem and some other new problems
defined in the rank metric coding theory setting.

4. For Lee metric, so far there is no construction based on this approach.

70
Bibliography

[ABD+ 18] C. Aguilar, O. Blazy, J.-C. Deneuville, P. Gaborit, and G. Zé-

mor. Efficient encryption from random quasi-cyclic codes.
IEEE Transactions on Information Theory, 64(5):32, May
2018.
[ABG+ 19a] N. Aragon, O. Blazy, P. Gaborit, A. Hauteville, O. Ruatta,
and G. Zémor. Low rank parity check codes: New decoding
algorithms and applications to cryptography. IEEE Trans. In-
formation Theory, 65(12):7697–7717, 2019.
[ABG+ 19b] N. Aragon, O. Blazy, P. Gaborit, A. Hauteville, and G. Zémor.
Durandal: A rank metric based signature scheme. In Advances
in Cryptology – EUROCRYPT 2019, pages 728–758. Springer
International Publishing, 2019.
[AGHT18] A. Aragon, P. Gaborit, A. Hauteville, and J.-P Tillich. A new
algorithm for solving the Rank Syndrome Decoding Problem.
In Proceedings of IEEE International Symposium on Informa-
tion Theory 2018 (ISIT 2018), pages 2421–2425, Vail, Col-
orado, USA, June 2018. IEEE.
[Ale03] M. Alekhnovich. More on average case vs approximation com-
plexity. In 44th Annual IEEE Symposium on Foundations of
Computer Science (FOCS 2003), pages 298–307, 2003.
[APRS20] Daniel Apon, Ray Perlner, Angela Robinson, and Paolo San-
tini. Cryptanalysis of ledacrypt. Cryptology ePrint Archive,
Report 2020/455, 2020. [Link]
455.
[Bar94] S. Barg. Some new np-complete coding problems. Problemy
Peredachi Informatsii, 30(3):23–28, 1994.

71
[BBB+ 20] M. Bardet, P. Briaud, M. Bros, P. Gaborit, V. Neiger, O. Ru-
atta, and J.-P. Tillich. An algebraic attack on rank metric
code-based cryptosystems. In Advances in Cryptology (EURO-
CRYPT 2020), pages 64–93, 2020.

[BBC+ 20] M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. Perlner,

D. Smith-Tone, J.-P. Tillich, and J. Verbel. Algebraic attacks
for solving the rank decoding and minrank problems without
gröbner basis, 2020.

[BHLP17] D. J. Bernstein, A. H ulsing, T. Lange, and L. Panny. Post-

quantum cryptography, round 1 submissions, racoss, official
comments., 2017. Available at [Link]

[BJMM12] A. Becker, A. Joux, A. May, and A. Meurer. Decoding ran-

dom binary linear codes in 2n/20: How 1 + 1 = 0 improves
information set decoding. In Annual International Conference
on the Theory and Applications of Cryptographic Techniques
(EUROCRYPT 2015), pages 520–536, 2012.

[BMT78] E. Berlekamp, R. McEliece, and H. V. Tilborg. On the inherent

intractability of certain coding problems. IEEE Transactions
on Information Theory, 24(3):384–386, 1978.

[BP18] P.S.L.M. Barreto and E. Persichetti. Cryptanalysis of the wave

signature scheme, 2018.

[BRC60] R. C. Bose and D. K. Ray-Chaudhuri. On a class of error cor-

recting binary group codes. Information and Control, 3(1):68–
79, 1960.

[BTP11] D.J. Bernstein, T. Lange T, and C. Peters. Smaller decod-

ing exponents: ball-collision decoding. In Annual Cryptology
Conference (CRYPTO 2011), pages 743–760, 2011.

[CFS01] N. T. Courtois, M. Finiasz, and N. Sendrier. How to achieve

a mceliece-based digital signature scheme. In Proc. Int. Conf.
ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer
Science, pages 157–174, Heidelberg, 2001. Springer.

[CS96] F. Chabaud and J. Stern. The cryptographic security of the

syndrome decoding problem for rank distance codes. In Proc.
Int. Conf. ASIACRYPT 1996, pages 368–381, 1996.

72
[CVA11] P.-L. Cayrel, P. Veron, and S. M. El Yousfi Alaoui. A zero-
knowledge identification scheme based on the q-ary syndrome
decoding problem. In The Proceedings of International Work-
shop on Selected Areas in Cryptography (SAC 2011), pages
171–186, 2011.

[DAST19] T. Debris-Alazard, N. Sendrier, and J.-P. Tillich. Wave: A

new family of trapdoor one-way preimage sampleable functions
based on codes. In Advances in Cryptology — ASIACRYPT’
19, pages 21–51. Springer Berlin Heidelberg, 2019.

[DAT18] T. Debris-Alazard and J.-P. Tillich. Two attacks on rank met-

ric code-based schemes: Ranksign and an ibe scheme. In Pro-
ceedings of the 24th International Conference on the Theory
and Application of Cryptology and Information Security, ASI-
ACRYPT 2018, pages 62–92. Springer, 2018.

[FHZ18] Tomas Fabsic, Viliam Hromada, and Pavol Zajac. A reac-

tion attack on ledapkc. Cryptology ePrint Archive, Report
2018/140, 2018. [Link]

[FLP08] J.-C. Faugère, F. Levy-dit-Vehel, and L. Perret. Cryptanaly-

sis of MinRank. In Advances in Cryptology, volume 5157 of
Lecture Notes in Computer Science, pages 280–296, New York,
2008. Springer-Verlag.

[FRX+ 17] K. Fukushima, P.S. Roy, R. Xu, S. Kiyomoto, K. Morozov, and

T. Takagi. Racoss signature scheme, 2017.

[FS86] A. Fiat and A. Shamir. How to prove yourself: Practical solu-

tions to identification and signature problems. In The Proceed-
ings of the Theory and Application of Cryptographic Techniques
(CRYPTO 1986), pages 186–194, 1986.

[Gab85] E. M. Gabidulin. Theory of codes with maximum rank dis-

tance. Probl. Pereda. Inf., 21:3–16, 1985.

[GC00] L. Goubin and N. T. Courtois. Cryptanalysis of the TTM cryp-

tosystem. In Proceedings of the 6th International Conference
on the Theory and Application of Cryptology and Information
Security, pages 44–57, Kyoto, Japan, December 2000.

73
[Gib95] J. K. Gibson. Severely denting the Gabidulin version of the
McEliece public-key cryptosystem. Designs, Codes and Cryp-
tography, 6(1):37–45, 1995.

[GJ20] Q. Guo and T. Johansson. A new decryption failure against

hqc. In International Conference on the Theory and Appli-
cation of Cryptology and Information Security (ASIACRYPT
2020), pages 353–382, 2020.

[GKH17] C.T. Gueye, J.B. Klamti, and S. Hirose. Generalization of

bjmm-isd using may-ozerov nearest neighbor algorithm over an
arbitrary finite field Fq . In International Conference on Codes,
Cryptology, and Information Security, pages 96–109, 2017.

[GKK+ 17] L. Galvez, J.-L. Kim, M.J. Kim, Y.-S. Kim, and N. Lee. McNie:
Compact McEliece-Niederreiter cryptosystem in NIST PQC
Round 1 Submission, 2017. Available at [Link]
gov/CSRC/media/Projects/Post-Quantum-Cryptography/
documents/round-1/submissions/[Link].

[GMRZ13] P. Gaborit, G. Murat, O. Ruatta, and G. Zemor. Low rank par-

ity check codes and their application to cryptography. In The
Proceedings of Workshop on Coding and Cryptography (WCC
2020), pages 168âĂŞ–180, 2013.

[GO01] E. M. Gabidulin and A. V. Ourivski. Modified GPT PKC

with right scrambler. Electron. Notes Discrete Math., 6:168–
177, 2001.

[GPT91] E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. Ideals

over a non-commutative ring and their application in cryptol-
ogy. In Advances in Cryptology - EUROCRYPT’91, volume
547 of Lecture Notes in Computer Science, pages 482–489, Hei-
delberg, 1991. Springer.

[GRS16] P. Gaborit, O. Ruatta, and J. Schrek. On the complexity of

the rank syndrome decoding problem. IEEE Transactions on
Information Theory, 62(2):106–109, 2016.

[GRSZ19] P. Gaborit, O. Ruatta, J. Schrek, and G. Zemor. Ranksign:

An efficient signature algorithm based on the rank metric. In
The Proceedings of International Workshop on Post-Quantum
Cryptography (PQCrypto 2014), pages 88–107, 2019.

74
[GZ16] P. Gaborit and G. Zémor. On the hardness of the decoding
and the minimum distance problems for rank codes. IEEE
Transactions on Information Theory, 62(12):7245–7252, 2016.

[Hir16] S. Hirose. May-ozerov algorithm for nearest-neighbor prob-

lem over Fq and its application to information set decoding.
In International Conference for Information Technology and
Communications, pages 115–126, 2016.

[Hoc59] A. Hocquenghem. Codes correcteurs d’erreurs. Chiffres,

2:147âĂŞ–156, 1959.

[HTW20] Anna-Lena Horlemann-Trautmann and Violetta Weger. In-

formation set decoding in the lee metric with applications to
cryptography. Advances in Mathematics of Communications,
2020.

[IKKR20] F. Ivanov, G. Kabatiansky, E. Krouk, and N. Rumenko. A

new code-based cryptosystem. In Code-Based Cryptography
Workshop (CBCrypto 2020), pages 41–49, 2020.

[IKR+ 20] C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal, and

V. Weger. Generalization of the ball-collision algorithm. Jour-
nal of Algebra Combinatorics Discrete Structures and Applica-
tions, 7(2):195–207, 2020.

[LB88] P. J. Lee and E. F. Brickell. An observation on the security of

mceliece’s public-key cryptosystem. In Workshop on the Theory
and Application of Cryptographic Techniques (EUROCRYPT
1988), pages 275–280, 1988.

[LCKN20] Y. Lee, J. Cho, Y. S. Kim, and J. S. No. Cryptanalysis of

the ivanov-kabatiansky-krouk-rumenko cryptosystems. IEEE
Communications Letters, 2020.

[Leo88] J.-S. Leon. A probabilistic algorithm for computing minimum

weights of large error-correcting codes. IEEE Transactions on
Information Theory, 34(5):1354–1359, 1988.

[Loi17] P. Loidreau. A new rank metric codes based encryption

scheme. In International Workshop on Post-Quantum Cryp-
tography (PQCrypto 2017), volume 10346 of Lecture Notes in
Computer Science, pages 3–17, Cham, 2017. Springer.

75
[LP06] F. Levy-dit-Vehel and L. Perret. Algebraic decoding of rank
metric codes. In Proc. YACC, pages 1–19, 2006.
[LT18a] T. S. C. Lau and C. H. Tan. A new technique in rank metric
code-based encryption. Cryptography, 2(4):32, 2018.
[LT18b] T. S. C. Lau and C. H. Tan. A new encryption scheme
based on rank metric codes. In Proceedings of the 23rd
Australasian Conference on Information Security and Privacy
(ACISP 2018), pages 750–758, Wollongong, NSW, Australia,
July 2018. Springer.
[LT18c] T. S. C. Lau and C. H. Tan. Key recovery attack on mcnie
based on low rank parity check codes and its reparation. In
Proceedings of Advances in Information and Computer Security
(IWSEC 2018), pages 19–34, Sendai, Miyagi, Japan, Septem-
ber 2018. Springer.
[LT19] T. S. C. Lau and C. H. Tan. New rank codes based encryption
scheme using partial circulant matrices. Designs, Codes and
Cryptography, 87:2979–2999, 2019.
[LT20a] T. S. C. Lau and C. H. Tan. Rank preserving code-based signa-
ture. In 2020 IEEE International Symposium on Information
Theory (ISIT 2020), pages 846–851, 2020.
[LT20b] T. S. C. Lau and C. H. Tan. Murave: A new rank code-based
signature with multiple rank verification. In Proceedings of the
International Code-based Cryptography Workshop (CBCrypto
2020), to appear, 2020.
[LT21] Terry S. C. Lau and Chik H. Tan. Polynomial-time plaintext
recovery attacks on the ikkr code-based cryptosystems. Ad-
vances in Mathematics of Communications, 2021.
[MAB+ 18] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux,
O. Blazy, J.-C. Deneuville, P. Gaborit, A. Hauteville, O. Ru-
atta, J.-P. Tillich, and G. Zémor. Rollo - rank-ouroboros, lake
& locker, 2018. Available at [Link]
rollo-specification_2018-[Link].
[McE78] R. J. McEliece. A public-key cryptosystem based on algebraic
coding theory. The Deep Space Network Progress Report 42-
44, Jet Propulsion Laboratory, Pasedena, CA, 1978.

76
[MO15] A. May and I. Ozerov. On computing nearest neighbors with
applications to decoding of binary linear codes. In Annual
International Conference on the Theory and Applications of
Cryptographic Techniques (EUROCRYPT 2015), pages 203–
228, 2015.

[MS87] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-

Correcting Codes. North-Holland, 3rd. edition, 1987.

[Nie86] H. Niederreiter. Knapsack-type cryptosystems and algebraic

coding theory. Probl Contr Inf Theory, 15(2):157–166, 1986.

[NPC+ 17] R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin, and

J. Buchmann. On lower bounds for information set decoding
over Fq and on the effect of partial knowledge. International
Journal of Information and Coding Theory, 4(1):47–78, 2017.

[OG03] A. V. Ourivski and E. M. Gabidulin. Column scrambler

for the GPT cryptosystem. Discrete Applied Mathematics,
128(1):207–221, 2003.

[OJ02] A. V. Ourivski and T. Johansson. New technique for decoding

codes in the rank metric and its cryptography applications.
Problems of Information Transmission, 38(3):237–246, 2002.

[Ove06] R. Overbeck. Extending Gibson’s attacks on the GPT cryp-

tosystem. In Proc. of WCC 2005, volume 3969 of Lecture Notes
in Computer Science, pages 178–188, Berlin, 2006. Springer.

[Ove08] R. Overbeck. Structural attacks for public key cryptosystems

based on Gabidulin Codes. Journal of Cryptology, 21(2):280–
301, 2008.

[Per18] E. Persichetti. Efficient one-time signatures from quasi-cyclic

codes: A full treatment. Cryptography, 2(4):30, 2018.

[Pet10] C. Peters. Information-set decoding for linear codes over

Fq . In International Workshop on Post-Quantum Cryptogra-
phy (PQCrypto 2010), pages 81–94, 2010.

[Pra62] E. Prange. The use of information sets in decoding cyclic codes.

IRE Transactions on Information Theory, 8(5):5–9, 1962.

77
[Reg05] O. Regev. On lattices, learning with errors, random linear
codes, and cryptography. In 37th ACM Symp. on Theory of
Computing (STOC 2005), pages 84–93, 2005.

[SBC19] P. Santini, M. Baldi, and F. Chiaraluce. Cryptanalysis of a one-

time code-based digital signature scheme. In The Proceedings of
IEEE International Symposium on Information Theory (ISIT
2019), pages 2594–2598, 2019.

[Sch90] C.P. Schnorr. Efficient identification and signatures for smart

cards. In Advances in Cryptology — CRYPTO’ 89 Proceedings,
pages 239–252. Springer New York, 1990.

[SS92] V. M. Sidelnikov and S. O. Shestakov. On insecurity of cryp-

tosystems based on generalied Reed-Solomon codes. Discrete
Mathematics and Applications, 2:439–444, 1992.

[Ste88] J. Stern. A method for finding codewords of small weight. In

International Colloquium on Coding Theory and Applications,
pages 106–113, 1988.

[Ste94] J. Stern. A new identification scheme based on syndrome de-

coding. In Proc. Int. Conf. CRYPTO 1993, volume 773 of
Lecture Notes in Computer Science, pages 13–21, Heidelberg,
1994. Springer.

[V9́7] P. Véron. Improved identification schemes based on error-

correcting codes. Appl. Algebra Eng. Commun. Comput.,
8(1):57âĂŞ69, 1997.

[WBS+ 20] V. Weger, M. Battaglioni, P. Santini, F. Chiaraluce, M. Baldi,

and E. Persichetti. Information set decoding of lee-metric codes
over finite rings. [Link] ePrint, page 2001.08425, 2020.

[WKH+ 21] V. Weger, K. Khathuria, A.-L. Horlemann, M. Battaglioni,

P. Santini, and E. Persichetti. On the hardness of the lee syn-
drome decoding problem. [Link] ePrint, page 2002.12785,
2021.

[WTBB+ 20] G. Wafo-Tapa, S. Bettaieb, L. Bidoux, P. Gaborit, and E. Mar-

catel. A practicable timing attack against hqc and its counter-
measure. Advances in Mathematics of Communications, 2020.

78