A Code-Based Linkable Ring Signature

Scheme

Pedro Branco and Paulo Mateus(B)

SQIG - Instituto de Telecomunicações, Department of Mathematics,

IST-Universidade de Lisboa, Lisbon, Portugal
pmat@math.ist.utl.pt

Abstract. Linkable ring signature schemes are cryptographic primitives

which have important applications in e-voting and e-cash. They are ring
signature schemes with the extra property that, if the same user signs
two messages, a verifier knows they were signed by the same user. In
this work, we present a new linkable ring signature scheme. The secu-
rity of our proposal is based on the hardness of the syndrome decod-
ing problem. To construct it, we use a variant of Stern’s protocol and
apply the Fiat-Shamir transform to it. We prove that the scheme has
the usual properties for a linkable ring signature scheme: unforgeability,
signer anonymity, non-slanderability and linkability.

Keywords: Linkable ring signature scheme · Code-based cryptography

1 Introduction
With the advent of the quantum computer, most of the standard asymmetric
cryptography is threatened since Shor’s algorithm is able to solve both dis-
crete logarithm and factorization problems [28]. As a consequence of this fact,
the development of post-quantum cryptographic primitives is crucial for the
future. Among the most important cryptographic primitives are digital signa-
ture schemes. They have the same legal value of a physical signature and can be
used in a wide range of applications such as authentication for a secure access to
a website, non-repudiation of contracts, validating transactions (as in the Bitcoin
system and other cryptocurrencies system) or e-voting. However, post-quantum
(in particular, code-based) digital signature schemes are still very inefficient for
applications and there are a lot of signature types for which there is no code-
based variant.
Linkable ring signature schemes [24] are a special type of ring signature
schemes that allow linkability, i.e., that allow two different signatures to be
linked to the same signer in a ring. Their applications to e-voting, e-cash and
cryptocurrencies are well known [27,31]. But, until now, there was no construc-
tion of this primitive based on coding theory.
In this work, we present the first linkable ring signature scheme whose security
is based on a hard problem in coding theory, the syndrome decoding problem.
c Springer Nature Switzerland AG 2018
J. Baek et al. (Eds.): ProvSec 2018, LNCS 11192, pp. 203–219, 2018.
https://doi.org/10.1007/978-3-030-01446-9_12
204 P. Branco and P. Mateus

Until this moment, most of the linkable ring signature schemes had their security
based on the discrete logarithm problem, which makes them useless for the post-
quantum era. Since our construction is based on a well-known code-based hard
problem, it is conjecture to be robust against quantum attacks and thus, suitable
for the post-quantum world.

1.1 Previous Work

Ring Signatures. Ring signature schemes are a special type of digital signa-
ture [26]. They allow for a user in a group to sign a message in name of the
group while preserving its anonymity. They can be seen as a particular case of
group signature scheme [13], where a member of a group can sign messages in
name of the group such that a verifier cannot know who signed the message but
the anonymity can be revoked by a group manager.
In some applications, one may be interested in knowing if two ring signatures
were issued by the same user in the ring. This can be done trivially using a group
signature scheme. The problem is that, in group signature schemes, anonymity
only exists as long as the group manager wants. Sometimes we may wish to
preserve the anonymity of a signer in a ring and give the verifier the chance to
know if two signatures were issued by the same user. This is the motivation for
creating linkable ring signature schemes.
Linkable Ring Signatures. Linkable ring signatures [24] are ring signature
schemes where it is possible to determine when two different messages were
signed by the same group user. They have important applications in e-cash and
e-voting [31]. At the moment, most of the existing signature schemes are based
on the discrete logarithm problem [7,23–25,31,32]. Therefore their security is
threatened: Shor’s algorithm [28] solves the discrete logarithm problem and,
thus, it breaks all of these linkable ring signature schemes. Very recently two dif-
ferent lattice-based linkable ring signature schemes were presented [8,30], which
are conjectured to be secure against quantum adversaries.
Code-Based Signatures. The first signature scheme based on coding theory
appeared in 2001 [14] and, in the last years, there was a huge development
of post-quantum signatures and, in particular, of code-based signature schemes.
The first code-based ring signature scheme appeared in 2007 [34]. After that,
many other variants were proposed like threshold ring signatures schemes [3,16],
undeniable signature schemes [2] or group signature schemes [4,5,18]. But, as
far as the authors know, this is the first proposal for a linkable ring signatures
scheme based on coding theory.
The signature schemes of [14,34] use trapdoors and, for this reason, their
security is based on both the Syndrome Decoding problem and on the Goppa
Distinguisher problem [14]. The latter can be solved when Goppa codes are used
with high rates [19] and hence, we have to increase their security parameters,
making them impractical in real-life applications. To overcome this problem, we
use the Fiat-Shamir transform (following [3,16]) to obtain linkable ring signature
scheme with more practical key sizes.
 A Code-Based Linkable Ring Signature Scheme 205

1.2 Our Contribution

In this paper, we give the first construction of a linkable ring signature scheme
whose security is based on a hard problem in coding theory. We also give a
variant of the proposed linkable ring signature scheme that provides the usual
security properties of existential unforgeability, anonymity and linkability.
To construct our proposal, we use a variant of Stern’s protocol and then we
apply the Fiat-Shamir transform to it. Signatures can be linked to each other
by a vector r that is the syndrome of the secret key of the signer by a random

matrix H.

1.3 Organization of the Paper

We begin the paper by introducing some notation and preliminary results. In

Sect. 3 we present both linkable ring signature schemes, one that achieves security
in the classical setting and a variant that achieves security in the quantum
setting. The proof of security for both schemes is given in Sect. 4. Finally, we
conclude this work by proposing parameters for the scheme and analyzing its
signature and key size.

2 Notation and Preliminaries

If A is an algorithm, y ← A(x) denotes the result of running A on input x

and outputting y and AO denotes A running with access to oracle O. If S is a
finite set, then x ←$ S means that x is chosen uniformly at random from S. A
negligible function negl(n) is a function such that negl(n) < 1/poly(n) for every
polynomial poly (n) and sufficiently large n. We denote Pr[A | B1 , . . . , Bn ] the
probability of event A after events B1 , . . . , Bn happened sequentially.

2.1 Linkable Ring Signature

In this section, we give the definition of a linkable ring signature scheme and
present the security model we adopt. By linked signatures we mean that they
were signed by the same user in the ring.
Definition 1. A linkable ring signature scheme is a tuple of algorithms
(KeyGen, Sign, Ver, Link) where:

– (pk, sk) ← KeyGen(1κ ) is a probabilistic polynomial-time (PPT) algorithm

that receives as input the security parameter κ and outputs a pair of public
and secret keys (pk, sk).
– σ ← Sign(1κ , pk, M, sk) is a PPT algorithm that receives as input a security
parameter κ, a list of public keys pk of size N (where the public key corre-
sponding to sk is included), a message M to be signed and a secret key sk. It
outputs a signature σ.
206 P. Branco and P. Mateus
 
– b ← Ver 1κ , pk, M, σ is a deterministic polynomial-time algorithm that
receives as input a security parameter κ, a list of public keys pk of size N , a
message M and a signature σ and outputs a bit b ∈ {0, 1} corresponding to
whether the signature σ is a valid one (b = 1) or not (b = 0).
– b ← Link(1κ , pk, M1 , σ1 , M2 , σ2 ) is a deterministic polynomial-time algorithm
that takes as input a list of public keys pk two messages  M1 and M2 and
n
two signatures
 σ 1 and σ 2 such that Ver 1 , pk, M1 , σ 1 = 1 and Ver 1n , pk,
M2 , σ2 = 1. It outputs b = 1 for linked signatures and b = 0 otherwise.

The security model we adopt is based on [7,25]. In order for a linkable ring
signature scheme to be secure, it must be existential unforgeable, anonymous,
non-slanderable and linkable. Existential unforgeability prevents an adversary
from forging a signature in name of a group if it does not have a public key
in this group, for any message M , while anonymity certifies that an adversary
is incapable of knowing who inside the group has signed a given message. Non-
slanderability (firstly introduced in [31] and formalized in [7]) prevents an adver-
sary from creating a signature that is linked to a second signature issued by other
user. Linkability guarantees that a user cannot create two valid signatures that
are not linked.
In the following, let pk = {pk1 , . . . , pkN } be the set of public keys of the users
in the ring and L ⊆ pk. Sign(·, sk) is a signing oracle that receives queries of
the form (pk, M ), and outputs σ ← Sign(1κ , pk, M, ski ), for any i ∈ {1, . . . , N },
and Co(·) be a corruption oracle that receives queries of the for pk and outputs
the corresponding secret key sk.
Existential Unforgeability. Consider the following game:

A (κ, N ) :
Gameunf
1 : (pki , ski ) ← KeyGen(1κ ) i = 1, . . . , N
Sign(·,ski ),Co(·)
2 : (L, M, σ) ← A (pk)
κ
3 : b ← Ver (1 , L, M, σ)
4 : return b

where (L, M ) was not asked Sign(·, sk) and A only queried Co(·) for pk ∈
/ L. We
define
A (κ, N ) := Pr[b = 1] .
Advunf
If for all PPT adversaries A we have that Advunf A (κ, N ) ≤ negl(κ, N ) then the
linkable ring signature scheme is existentially unforgeable. This is called unforge-
ability with respect to insider corruption in [9] and it is the strongest level of
unforgeability that a ring signature can achieve.
 A Code-Based Linkable Ring Signature Scheme 207

Anonymity. Consider the following game:

Gameanon
A (κ, N ) :
1 : (pki , ski ) ← KeyGen(1κ ) i = 0, 1
2 : b ←$ {0, 1}
3 : b ← ASign(·,skb ),Sign(·,sk0 ),Sign(·,sk1 ) (pk0 , pk1 )
4 : return b

where the adversary is not allowed to ask queries with different L to Sign(·, skb )
nor to ask queries with the same L to both Sign(·, skb ) and Sign(·, sk0 ) or to both
Sign(·, skb ) and Sign(·, sk1 ). We do not allow this to happen to avoid the trivial
attacks. We define
1
Advanon
A (κ, N ) := Pr [b = b ] − .
2
If for all PPT adversaries A we have Advanon A (κ, N ) ≤ negl(κ, N ) then the link-
able ring signature scheme is anonymous. This definition is equivalent to the
definition of anonymity with respect to adversarially-chosen keys in [9], as it is
stated in [21].
Non-slanderability. Consider the following game:

A (κ, N ) :
Gamensla
1 : (pki , ski ) ← KeyGen(1κ ), i = 1, . . . N
Sign(·,ski )
2 : (L, pk1 , M1 ) ← A (pk)
κ
3 : σ1 ← Sign(1 , L, M1 , sk1 )
4 : (pk2 , M2 , σ2 ) ← ASign(·,ski ) (pk, L, sk2 , pk1 , M1 , σ1 )
5 : b ← Link(1κ , L, M1 , σ1 , M2 , σ2 )
6 : return b

where pk1 , pk2 ∈ L, pk1 = pk2 and both pairs (L, M1 ), σ1 and (L, M2 ), σ2 were
not asked to nor replied by Sign(·, ski ). We define

A (κ, N ) := Pr[b = 1] .
Advnsl

A (κ, N ) ≤ negl(κ, N ) then the linkable

If for all PPT adversaries A we have Advnsl
ring signature scheme has non-slanderability.
Linkability. Consider the game:

A (κ, N ) :
Gamelink
1 : (pki , ski ) ← KeyGen(1κ ), i = 1, . . . , N
Sign(·,ski )
2 : pk ← A (pk)
3 : (L, M1 , σ1 , M2 , σ2 ) ← ASign(·,ski ) (pk, pk)
4 : b ← 1 − Link(1κ , L, M1 , σ1 , M2 , σ2 )
5 : return b
208 P. Branco and P. Mateus

where Ver(1κ , L, M1 , σ1 ) = 1, Ver(1κ , L, M2 , σ2 ) = 1 and both pairs (L, M1 ), σ1

and (L, M2 ), σ2 were not asked to nor replied by Sign(·, ski ). We define

A (κ, L) := Pr[b = 1] .
Advlink

If for all PPT adversaries A we have that Advlink

A (κ, L) ≤ negl(κ, N ) then the
linkable ring signature scheme has linkability.

2.2 Sigma Protocols

Due to the lack of space, we review very briefly some basic concepts on sigma
protocols and on the Fiat-Shamir transform. For a more detailed review, see [17].
A sigma protocol (P, V) is a three-round protocol between a prover P and a
verifier V where the prover tries to convince the verifier about the validity of
some statement. A proof of knowledge (PoK) is a particular case of a sigma
protocol. Here, the prover P convinces the verifier V, not only about the veracity
of the statement but also that P has a witness for it. The three rounds of any
sigma protocol are the commitment (com) by the prover, the challenge (ch) by
the verifier and the response (resp) by the prover. A transcript (com, ch, resp)
is said to be valid if the verifier accepts it as a valid proof.
A sigma protocol must have the following properties: (i) completeness, which
guarantees that the verifier will accept the proof with high probability if the
prover has the secret; (ii) special soundness, which ensures that there is an extrac-
tor such that, given two valid transcripts (com, ch, resp) and (com, ch  , resp  )
where ch = ch  , then it can extract the secret; and (iii) honest-verifier zero-
knowledge (HVZK) which ensures that no information is gained by the verifier
by just looking at the proof. This is usually proven by showing the existence of a
simulator that can generate transcripts that are computationally indistinguish-
able from transcripts generated by the interaction between the prover and the
verifier.
As usual, we denote a relation of size n in X × W by Rn . Given x ∈ X
(which is public information) and w ∈ W (usually called the witness), it can
be computed whether Rn (x, w) = 1. We define the set LR = {x ∈ X : ∃w ∈
W s.t. Rn (x, w) = 1}.
The following definitions are taken from [33] and they will be useful to argue
post-quantum security of the Fiat-Shamir transform.
A sigma protocol (P, V) is said to be statistically sound if
 
Pr 1 ← V ∧ x ∈ / LRn | (x, com) ← A1 , ch ←$ {0, 1}l , resp ← A2 ≤ negl(n) ,

where A2 takes (ch) as input and V takes the transcript (com, ch, resp). The
sigma protocol (P, V) is said to have unpredictable commitments if for all (x, w)
such that Rn (x, w) = 1 we have that

Pr [com = com | com ← P(x, w), com ← P(x, w)] ≤ negl(n) .

 A Code-Based Linkable Ring Signature Scheme 209

Let K be a (possibly quantum) polynomial-time algorithm. We call K a hard

instance generator for some relation Rn of size n if, for all PPT adversaries A
and (x, w) ← K such that Rn (x, w) = 1 we have
Pr[R(x, w ) = 1 | w ← A(x)] ≤ negl(n) .

Definition 2 ([33]). We call K a dual-mode hard instance generator if there is

a PPT algorithm K∗ such that
Pr[1 ← A(x) | (x, w) ← K] − Pr [1 ← A(x) | x ← K∗ ] ≤ negl(n)
and
Pr[x ∈ LRn | x ← K∗ ] ≤ negl(n) .
Informally, a dual-mode hard instance generator is a hard instance generator
where, not only it is hard to find witnesses for a word x, but also it is hard to
distinguish if there is a witness w for this word x.

2.3 Fiat-Shamir Transform

The Fiat-Shamir transform [20] is a generic method to convert any PoK protocol
that is complete, special sound and HVZK into a signature scheme. The security
of the Fiat-Shamir transform is proven to be secure both in the random oracle
model (ROM) [1] and in the quantum random oracle model (QROM) [33], under
certain conditions.
The idea behind the Fiat-Shamir transform is that the prover is able to
simulate the challenge that is usually sent by the verifier. Since this challenge
should be chosen uniformly at random, the prover sets the challenge according
to a cryptographic hash function depending on the message to be signed and on
the commitment chosen previously by the prover. More precisely, given a proof
of knowledge (P, V), the prover computes com, then sets ch = h(com, M ) where
h is a cryptographic hash function and M is the message to be signed. Finally,
it computes resp such that (com, ch, resp) is a valid transcript. The signature of
M is (com, resp). For someone to verify the validity of the signature, one just
has to compute ch = h(com, M ) and then check that (com, ch, resp) is a valid
transcript.
The following result guarantees the security of the Fiat-Shamir transform in
the classical setting.
Theorem 1 ([1]). Suppose that (P, V) is a sigma protocol that is complete,
special sound and HVZK. Then the signature scheme obtained by applying the
Fiat-Shamir transform is secure in the ROM.
However, in the quantum setting, where an adversary can perform quantum
computations in the quantum random oracle model (QROM [11]), the Fiat-
Shamir transformation seems to be insecure, or, at least, it is not secure in
some cases [6]. Fortunately, Unruh gave sufficient conditions for the Fiat-Shamir
transform to be secure in the quantum setting [33].
210 P. Branco and P. Mateus

Theorem 2 ([33]). Let K be a dual-mode hard instance generator for some

relation R. Let (P, V) be a sigma protocol for the relation R that is complete,
statistical sound, HVZK and has unpredictable commitments. Then the signature
scheme obtained by applying the Fiat-Shamir transformation to (P, V) is secure
in the QROM.
We will use the Fiat-Shamir transform to construct a linkable ring scheme
and we will use Theorem 1 to prove its security in the ROM. Theorem 2 gives
the basis to prove security in the QROM.

2.4 Hard Problems in Coding Theory

We present the Syndrome Decoding (SD) problem, which is proven to be NP-
complete [10].
Problem 1 (Syndrome Decoding - Decision Version). Given a binary
matrix H ∈ {0, 1}(n−k)×n , a vector s ∈ {0, 1}n−k , and an integer t ≥ 0 deter-
mine whether there exists e such that w(e) ≤ t and HeT = sT .
The following problem is a generalization of the SD problem. We will call
this problem the General Syndrome Decoding (GDS) problem.
Problem 2 (General Syndrome Decoding). Given binary matrices H, G ∈
{0, 1}(n−k)×n , vectors s, r ∈ {0, 1}n−k , and an integer t ≥ 0 determine whether
there exists e such that w(e) ≤ t, HeT = sT and GeT = rT .
It is easy to see that SD can be reduced to the GSD problem. More precisely,
we have that (H, s, t) ∈ SD iff (H, s, H, s, t) ∈ GSD, which gives a Karp reduction
of SD to GSD. In other words, the SD problem is the diagonal of GSD. Moreover,
since the SD problem is NP-complete, we conclude that the SD problem and the
GSD problem are equivalent. Furthermore, observe that the reduction presented
is tight. Hence, the parameters for which the SD problem is infeasible also make
the GSD problem infeasible.
Note that it is trivial to conceive an algorithm that satisfies the conditions of
a dual-mode hard instance generator that creates instances of the SD problem, in
the sense of Definition 2: one just has to choose a random matrix and a random
error vector and then compute the syndrome of the error vector. The matrix,
the syndrome and the weight of the error vector form an instance of the SD
problem. The same applies to the GSD problem.
We present a variant of Stern’s protocol [29] based on the hardness of the
GSD problem. In this variant, the prover is able to prove that it has the solution
for an instance of the GSD problem. That is, given (H, s, G, r, t), it proves that
it has an error vector e such that HeT = s, GeT = rT and w(e) ≤ t. The
protocol is presented in Algorithm 1. We will call it the GStern’s protocol.
As in the original Stern’s protocol, when b = 1, V can check that c1 was
honestly computed by computing H(y + e) + s = Hy and G(y + e) + r = Gy.
Also, the verifier can check that the same error vector e that was used to compute
both the syndrome vectors s and r. The next lemma states that GStern’s protocol
has the usual properties of completeness, special soundness and HVZK.
 A Code-Based Linkable Ring Signature Scheme 211

Algorithm 1. GStern’s protocol

1. Public information: H, G ∈ {0, 1}n×n−k and s, r ∈ {0, 1}n−k .
2. Secret information: e ∈ {0, 1}n such that HeT = sT , GeT = rT and w(e) = t.
3. Prover’s commitment:
– Chooses y ←$ {0, 1}n and a permutation δ;
– Computes c1 = h(δ, HyT , GyT ), c2 = h (δ(y)) and c3 = h (δ(y + e));
– P sends c1 , c2 and c3 .
4. Verifier’s challenge: V sends b ←$ {0, 1, 2}.
5. Prover’s answer:
– If b = 0, P reveals y, δ;
– If b = 1, P reveals y + e, δ;
– If b = 2, P reveals δ(y), δ(e).
6. Verifier’s verification:
– If b = 0, V checks if h(δ, HyT , GyT ) = c1 and h (δ(y)) = c2 ;
– If b = 1, V checks if h(δ, H(y +e)T +sT , G(y +e)T +rT ) = c1 and h (δ(y + e)) =
c3 ;
– If b = 2, V checks if h (δ(y)) = c2 , h(δ(y) + δ(e)) = c3 and w (δ(e)) = t.

Lemma 1. The protocol presented in Algorithm 1 is complete, special sound

and HVZK.

Proof. The proof is similar to the proofs of completeness, special soundness and
HVZK for Stern’s protocol, presented in [29].

Next we present in Algorithm 2 a variant of the above protocol that enables

a prover to prove the knowledge of the solution of an instance of the problem
without revealing which one it is. It is based on the generic construction in [15]
and on the previous proof of knowledge. In this new protocol, given N instances
of the GSD problem, the prover is able to prove that it has a solution for one
of these instances, without revealing to the verifier which one is it. More pre-
cisely, given (H1 , s1 , G1 , r1 , t1 ), . . . , (HN , sN , GN , rN , tN ), the prover proves the
knowledge of an error vector e such that Hi eT = si , Gi eT = rTi and w(e) ≤ ti ,
for some i ∈ {1, . . . N } unknown to the verifier. Here, com corresponds to the
prover’s commitment, ch to the challenge by the verifier, resp the response of
the prover and (com, ch, resp) to a transcript according to the previous protocol.
The protocol presented in Algorithm 2 will be called N1 -GStern’s protocol.
The protocol is proven to be a proof of knowledge that is complete, special
sound and HVZK [15].
Based on the results of [33], for the GStern’s protocol to be secure in the
post-quantum setting it needs to achieve statistical soundness.
To this end, we need to introduce the concept of perfectly binding commit-
ment schemes. First, we present the definition of commitment scheme. A commit-
ment scheme is a protocol between two parties, the committer and the receiver,
that has two phases: the commitment phase where the committer commits to
a value, and the opening phase where the committer opens her commitment.
A commitment scheme should be hiding, meaning that the receiver should not
212 P. Branco and P. Mateus

N 
Algorithm 2. 1 -GStern’s protocol
1. Public information: H, G ∈ {0, 1}n×n−k , s1 , . . . , sN , r1 , . . . , rN ∈ {0, 1}n−k
and t ∈ Z.
2. Secret information: e ∈ {0, 1}n such that w(e) = t, HeT = sTi and GeT = rTi
for some i.
3. Prover’s commitment:
– P ∗ simulates transcripts (com j , ch j , resp j ) using the simulator S for GStern’s
protocol for j = i;
– P ∗ computes com i according to GStern’s protocol;
– P ∗ sends com 1 , . . . , com n ;
4. Verifier’s challenge: V sends b ←$ C.
5. Prover’s answer: 
– P computes ch i = b + j=i ch j ;
– P chooses resp i , according to com i and ch i ;
– Sends (com j , ch j , resp j ) for every j;
6. Verifier’s verification:
– V checks that (com j , ch j , resp j ) is valid for every j according to GStern’s pro-
tocol; 
– V checks that b = j ch j ;
– If all the previous conditions hold, V accepts.

be able to know the committer’s commitment before the opening phase; and it
should be binding, meaning that the committer should not be able to open a
different message from the one she has committed before. By a perfectly bind-
ing commitment scheme (PBCS) we mean a commitment scheme for which the
user that commits cannot change its commitment even if it has unlimited com-
putational power. In this work, we use a post-quantum PBCS as a black-box,
although it is known that PBCS exist in the post-quantum setting (see, for
instance [22], that is proven to be secure under the LPN problem, the dual and
equivalent version of the SD problem). In our construction, any commitment
scheme can be used as long as it is perfectly binding and computationally hiding
against quantum attacks.
As we show in the next result, to construct a variant of GStern’s protocol that
achieves statistical soundness, it is enough to replace the hash function h used
to create the commitments, in the Prover’s commitment phase, by a perfectly
binding commitment scheme. We will call it the PQ GStern’s protocol. Observe
that this is still a complete and HVZK protocol.
Lemma 2. PQ GStern’s protocol is statistically sound.

Proof. First, note that, if Com is a PBCS, then Com(x1 ) = Com(x2 ) for x1 = x2
except with negligible probability. If this happens with non-negligible probability,
then the user who is committing could send Com(x1 ) and then reveal x2 with
non-negligible probability, contradicting the fact that Com is perfectly binding.
Suppose that there is an algorithm A (not necessarily running in polynomial-
time) that breaks the statistical soundness of PQ Stern’s protocol. Then A is
 A Code-Based Linkable Ring Signature Scheme 213

able to find H, s, G, r and t, for which there is no e such that w(e) = t, HeT = s
and GeT = rT , and com such that it is able to answer correctly to any challenge
with non-negligible probability. This implies that either A is able to break the
special soundness of the protocol (note that, since there is no witness for the
instance (H, s.G, r, t) then the adversary must build its commitments according
to some strategy since, if it follows the protocol, it will be caught) or it is able
to break the PBCS. The first event happens with probability as close to zero as
we want and the second event also happens with negligible probability. In both
cases, we reach a contradiction. 

Recall that a sigma protocol is said to have unpredictable commitments if

the probability of getting the same value when running twice the commitment
phase of the sigma protocol is negligible, as it was defined in 2.2.
Lemma 3. PQ GStern’s protocol has unpredictable commitments.

Proof. Again, recall that Com(x1 ) = Com(x2 ) for x1 = x2 except with negligible
probability, when Com is a PBCS.
Now consider GStern’s protocol. For two commitments made in different
executions of the protocol to be equal, the prover would have to choose uniformly
at random two vectors y and z of length n and two permutations δ and γ over
1, . . . , n such that
1. (δ, HyT , GyT ) = (γ, HzT , GzT )
2. δ(y) = γ(z)
3. δ(y + e) = γ(z + e).
By 1. we conclude that δ = γ in order for the commitments to be equal. But
the probability of this happening is 1/n!. This is enough to prove the lemma,
since we have that

Pr[com = com  | com ← P(1n , x, w), com ← P(1n , x, w)] ≤ 1/n!

which is, of course, negligible in n. 

N 
To finish this section, note that the same technique can be applied to 1 -
GStern’s protocol in order toobtain
 new a sigma protocol that yield statistical
soundness. It is obvious that N1 -GStern’s protocol also has unpredictable com-
 
mitments. We will call PQ N1 -GStern’s protocol to this new version.

3 A Linkable Ring Signature Scheme

We present the new linkable ring signature scheme in Algorithm
  3. To obtain the
signature scheme we apply the Fiat-Shamir transform to N1 -GStern protocol.
 r) using its secret key
More precisely, the signer creates an instance I = (H, s, H,

and where the matrix H is obtained via a cryptographic hash function and r is
the syndrome of its secret key by H. Then, it applies the Fiat-Shamir transform
214 P. Branco and P. Mateus
 
to N1 -GStern’s protocol on input (H, s, H, r) where s = (s1 , . . . sN ) are the
public keys of the members in the ring and r = (r, . . . , r). On the one hand, the
verifier will not be able to check which user computed r, due to the hardness
of the SD problem. On the other hand, r will be part of every signature issued
by this user with respect to the same ring. So, these signatures can be linked
by a verifier. In the following, let g and f be two different cryptographic hash
functions and consider a ring with N users with public keys pk = (pk1 , . . . , pkN ).

Algorithm 3. A new linkable ring signature scheme

1. Parameters: n, k, t ∈ N such that n > k, H ←$ {0, 1}n×(n−k)
2. Key Generation: Each user Pi :
– Chooses ei ←$ {0, 1}n such that w(e) = t;
– Computes sTi = HeTi .
Public key of user Pi : H, si , t.
Secret key of user Pi : ei such that w(e) = t and HeTi = sTi .
3. Sign: To sign message M , user Pi :
– Computes matrix g(pk) = H  and He
 Ti = rT ;
 
– Applies the Fiat-Shamir transform to N1 -GStern’s protocol on input (H, s, H,  r)
where s = (s1 , . . . , sN ) and r = (r, . . . , r):  
• Computes the commitments Com according to N1 -GStern’s protocol;
• Simulates the verifier’s challenge Ch as f (Com, M );  
• Computes the corresponding responses Resp according to step 5 of N1 -
GStern’s protocol;
• Outputs the transcript T = (Com, Ch, Resp).
– Outputs the signature (pk, M, σ) where σ = (r, Com, Resp).
4. Verify: To verify, the verifier:
– Computes Ch = f (Com, M );
– Computes H  = g(pk);
 
– Verifies that T = (Com, Ch, Resp) is a valid transcript, according to N1 -
GStern’s protocol and input (H, s, H,  r).
5. Link: Given two signatures (pk, M, σ) and (pk, M  , σ  ) where σ = (r, Com, Resp)
and σ  = (r , Com  , Resp  ) and such that Ver(pk, M, σ) = 1 and Ver(pk, M  , σ  ) = 1,
the verifier:
– Checks if r = r ;
– Outputs 1 if it is equal; else, outputs 0.

4 Security of the Scheme

In this section we present the results concerning the security of the proposed
scheme. We prove that the scheme has the usual properties for a linkable ring
signature scheme: existential unforgeability, anonymity, non-slanderability and
linkability. The proofs are presented in the extended version of the paper.
Existential Unforgeability. Existential unforgeability in the classical setting is a
direct consequence of the fact that the signature is obtained from a sigma proto-
col that is complete, special sound and HVZK and Theorem 1. The post-quantum
 A Code-Based Linkable Ring Signature Scheme 215

security of the proposed PQ linkable ring signature scheme is guaranteed by the

fact that the sigma protocol used in the Fiat-Shamir transform is complete,
statistically sound, HVZK and has unpredictable commitments.
Theorem 3. Assume that the GSD problem is hard. The linkable ring signature
scheme proposed is existentially unforgeable in the ROM.

Anonymity. In order to prove anonymity for the linkable ring signature scheme,
we reduce the GSD problem to that of breaking anonymity. In this proof, we
assume that we are able to break the anonymity of the scheme, and construct
an algorithm that solves the GSD problem. However, we have to know before-
hand some non-null coordinates of the error vector, namely we assume that t/2
positions are known. This is required because we know how the algorithm that
breaks the anonymity behaves when it is given two valid public key or when
it is given two random values as public keys. However, we do not know how it
behaves when it is given one valid public key and one random value as public
key. Moreover, given a tuple (H, s, G, r, t), we do not know if this represents a
valid public key of the cryptosystem or if it is a random tuple. However, if we
know part of the secret, we are able to construct another tuple (H, s , G, r , t)
that is a GSD tuple if (H, s, G, r, t) is a GSD tuple or that is a random tuple if
(H, s, G, r, t) is a random tuple. The fact that t/2 positions are known does not
threat the security proof since the GSD problem is still computationally hard.
We just have to increase the parameters to maintain the same level of security.

Theorem 4. Assume that the GSD problem knowing t/2 positions of the error
vector is hard. The proposed linkable ring signature scheme has anonymity in
the ROM.

Non-slanderability. To argue that our proposal has the non-slanderability prop-

erty, we prove that it is infeasible for an adversary to frame another user in
the ring. That is, given a message and a signature produced by some user, it
is infeasible for an adversary to create a signature for another message that is
linked to the first one.
Theorem 5. Assume that the GSD problem is hard. The linkable ring signature
scheme is non-slanderable in the ROM.

Linkability. Linkability prevents a user from signing two messages that are not
linked. To show that the proposed linkable ring signature scheme has linkability,
we must prove that it is infeasible for an adversary with access to at most one
secret key to create signatures that are not linked.
Theorem 6. Assume that the GSD problem is hard. The linkable ring signature
scheme is linkable in the ROM.
216 P. Branco and P. Mateus

5 Parameters and Key Size

To conclude, we propose parameters for the scheme and analyze its signature and
key size. For the cheating probability of GStern’s protocol to be approximately
2−80 , it has to be iterated 140 times. Recall that anonymity for our linkable ring
signature scheme is proven when knowing t/2 positions of the error vector. Hence,
to yield the standard security of approximately 80 bits for signature schemes
according to the best known attack [12], we consider a code with n = 1268,
k = n/2 and t = 130. Note that a code with these parameters has a security
of at least 80 bits even when knowing t/2 positions of the error vector. This is
necessary to maintain the anonymity of the scheme.
Size of the Sigma Protocol. Using a cryptographic hash function with a security
of 128 bits, each round of GStern’s protocol has approximately 2270 bits  of

exchange information. Let N be the number of users in the ring. Since N1 -
 
GStern’s protocol is just the previous protocol repeated N times, then N1 -
GStern’s protocol has 2270N bits of exchange information in each round.
Signature Size.
 To
 estimate the size of a signature, notice that the signature is a
transcript of N1 -GStern’s protocol repeated 140 times plus the size of a vector
r, in order to guarantee the usual level of security for signature schemes, which
is about 80 bits of security. Hence, the signature size is approximately 317 800N
bits , where N is the number of users in the ring. In other words, the signature
size is approximately 39N kBytes. For example, for a ring with N = 100 users,
the signature size is approximately 4 MBytes.
Public Key Size. The public key of the ring is composed by (H, s1 , . . . , sN ).
Therefore, the total size of the public key is approximately 803917 + 634N bits,
which is linear in the number of users in the ring. For each user, the public key
is of size 803917 + 634 bits and a secret key of size 1268 bits.
Comparison with Lattice-Based Linkable Ring Signature Schemes. The signature
size of our proposal is slightly bigger than the signature size of the schemes
in [8,30] (around 4 times bigger for the same number of users in the ring). The
public key size is roughly the same as the scheme in [8] and it is ten times bigger
than the one presented in [30], for a ring with 10 users. The secret key size of
our proposal is much smaller than both schemes [8,30] (it is 50 times smaller
than [8] and 6 times smaller than [30]).

6 Discussion and Conclusion

Linkable ring signature schemes have become important in today’s world mainly
because of their importance in e-voting schemes and in cryptocurrencies. In
this paper we presented the first code-based linkable ring signature scheme.
To achieve this, we applied the Fiat-Shamir transform to a variant of Stern’s
protocol.
A candidate for post-quantum linkable ring signature
  scheme can be obtained
by applying the Fiat-Shamir transform to the PQ N1 -GStern protocol (that is,
 A Code-Based Linkable Ring Signature Scheme 217

the post-quantum version of Algorithm 2) in a similar way as presented in Algo-

rithm 3. It is easy to extend the the proofs of Theorem 3 (existential unforgeabil-
ity), Theorem 5 (non-slanderability) and Theorem 6 (linkability) for such ring
signature scheme in the QROM. But it is now straightforward to extend the
result of Theorem 4 (anonymity). We leave as an open problem the case where
an adversary can make queries in superposition to the random oracle, as usual
for other post-quantum signature schemes, e.g. [4,8]. Although this case was not
addressed yet by the community, it is strongly believed that there is no efficient
quantum attack on the anonymity for these schemes.
Finally, the protocol we described outputs signatures and keys which are too
long for some applications (as it is usual for code-based cryptographic schemes).
Still, we think that there is room for improvement. For example, in some appli-
cations, the public matrix H can be divided among the several users in the ring
since H is part of the public key of every user. This would reduce the key size
for each user.

Acknowledgments. The authors acknowledge the anonymous referees that con-

tributed to the readability and improvement of the final manuscript. The first
author thanks the support from DP-PMI and FCT (Portugal) through the grant
PD/BD/135181/2017. The authors thank IT, namely via SQIG and the FCT projects
number PEst-OE/EEI/LA0008/2013 and Confident PTDC/EEI-CTP/4503/2014. The
authors also thank the H2020 SPARTA project under SU-ICT-03.

References
1. Abdalla, M., An, J.H., Bellare, M., Namprempre, C.: From identification to sig-
natures via the fiat-shamir transform: minimizing assumptions for security and
forward-security. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332,
pp. 418–433. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-
7 28
2. Aguilar-Melchor, C., Bettaieb, S., Gaborit, P., Schrek, J.: A code-based undeniable
signature scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 99–119.
Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-45239-0 7
3. Aguilar Melchor, C., Cayrel, P.L., Gaborit, P., Laguillaumie, F.: A new efficient
threshold ring signature scheme based on coding theory. IEEE Trans. Inf. Theor.
57(7), 4833–4842 (2011)
4. Alamélou, Q., Blazy, O., Cauchie, S., Gaborit, P.: A practical group signature
scheme based on rank metric. In: Duquesne, S., Petkova-Nikova, S. (eds.) WAIFI
2016. LNCS, vol. 10064, pp. 258–275. Springer, Cham (2016). https://doi.org/10.
1007/978-3-319-55227-9 18
5. Alamélou, Q., Blazy, O., Cauchie, S., Gaborit, P.: A code-based group signature
scheme. Des. Codes Crypt. 82(1), 469–493 (2017). https://doi.org/10.1007/s10623-
016-0276-6
6. Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof sys-
tems: the hardness of quantum rewinding. In: Proceedings of the 2014 IEEE 55th
Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 474–483.
IEEE Computer Society, Washington (2014). http://dx.doi.org/10.1109/FOCS.
2014.57
218 P. Branco and P. Mateus

7. Au, M.H., Chow, S.S.M., Susilo, W., Tsang, P.P.: Short linkable ring signatures
revisited. In: Atzeni, A.S., Lioy, A. (eds.) EuroPKI 2006. LNCS, vol. 4043, pp.
101–115. Springer, Heidelberg (2006). https://doi.org/10.1007/11774716 9
8. Baum, C., Lin, H., Oechsner, S.: Towards practical lattice-based one-time link-
able ring signatures. Cryptology ePrint Archive, Report 2018/107 (2018). https://
eprint.iacr.org/2018/107
9. Bender, A., Katz, J., Morselli, R.: Ring signatures: stronger definitions, and con-
structions without random oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006.
LNCS, vol. 3876, pp. 60–79. Springer, Heidelberg (2006). https://doi.org/10.1007/
11681878 4
10. Berlekamp, E.R., McEliece, R.J., van Tilborg, H.: On the inherent intractability of
certain coding problems (corresp.). IEEE Trans. Inf. Theor. 24(3), 384–386 (1978)
11. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.:
Random Oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT
2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.
1007/978-3-642-25385-0 3
12. Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words
in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH
codes of length 511. IEEE Trans. Inf. Theor. 44(1), 367–378 (1998)
13. Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT
1991. LNCS, vol. 547, pp. 257–265. Springer, Heidelberg (1991). https://doi.org/
10.1007/3-540-46416-6 22
14. Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital
signature scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp.
157–174. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1 10
15. Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and sim-
plified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994.
LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994). https://doi.org/10.1007/
3-540-48658-5 19
16. Dallot, L., Vergnaud, D.: Provably secure code-based threshold ring signatures.
In: Parker, M.G. (ed.) IMACC 2009. LNCS, vol. 5921, pp. 222–235. Springer,
Heidelberg (2009). https://doi.org/10.1007/978-3-642-10868-6 13
17. Damgård, I.: On σ-protocols. Lecture Notes, University of Aarhus, Department for
Computer Science (2002)
18. Ezerman, M.F., Lee, H.T., Ling, S., Nguyen, K., Wang, H.: A provably secure group
signature scheme from code-based assumptions. In: Iwata, T., Cheon, J.H. (eds.)
ASIACRYPT 2015. LNCS, vol. 9452, pp. 260–285. Springer, Heidelberg (2015).
https://doi.org/10.1007/978-3-662-48797-6 12
19. Faugre, J., Gauthier-Umaa, V., Otmani, A., Perret, L., Tillich, J.: A distinguisher
for high-rate mceliece cryptosystems. IEEE Trans. Inf. Theor. 59(10), 6830–6844
(2013)
20. Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and
signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp.
186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7 12
21. Fujisaki, E., Suzuki, K.: Traceable ring signature. In: Okamoto, T., Wang, X. (eds.)
PKC 2007. LNCS, vol. 4450, pp. 181–200. Springer, Heidelberg (2007). https://
doi.org/10.1007/978-3-540-71677-8 13
22. Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-
knowledge proofs from learning parity with noise. In: Wang, X., Sako, K. (eds.)
ASIACRYPT 2012. LNCS, vol. 7658, pp. 663–680. Springer, Heidelberg (2012).
https://doi.org/10.1007/978-3-642-34961-4 40
 A Code-Based Linkable Ring Signature Scheme 219

23. Liu, J.K., Au, M.H., Susilo, W., Zhou, J.: Linkable ring signature with uncondi-
tional anonymity. IEEE Trans. Knowl. Data Eng. 26(1), 157–165 (2014)
24. Liu, J.K., Wei, V.K., Wong, D.S.: Linkable spontaneous anonymous group signa-
ture for Ad Hoc groups. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP
2004. LNCS, vol. 3108, pp. 325–335. Springer, Heidelberg (2004). https://doi.org/
10.1007/978-3-540-27800-9 28
25. Liu, J.K., Wong, D.S.: Linkable ring signatures: security models and new schemes.
In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganà, A., Lee, H.P., Mun, Y.,
Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3481, pp. 614–623. Springer,
Heidelberg (2005). https://doi.org/10.1007/11424826 65
26. Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: Boyd, C. (ed.)
ASIACRYPT 2001. LNCS, vol. 2248, pp. 552–565. Springer, Heidelberg (2001).
https://doi.org/10.1007/3-540-45682-1 32
27. van Saberhagen, N.: Cryptonote v 2.0 (2013)
28. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete log-
arithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997).
https://doi.org/10.1137/S0097539795293172
29. Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson,
D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994).
https://doi.org/10.1007/3-540-48329-2 2
30. Torres, W.A., et al.: Post-quantum one-time linkable ring signature and application
to ring confidential transactions in blockchain (lattice ringCT v1.0). Cryptology
ePrint Archive, Report 2018/379 (2018). https://eprint.iacr.org/2018/379
31. Tsang, P.P., Wei, V.K.: Short linkable ring signatures for e-voting, e-cash and
attestation. In: Deng, R.H., Bao, F., Pang, H.H., Zhou, J. (eds.) ISPEC 2005.
LNCS, vol. 3439, pp. 48–60. Springer, Heidelberg (2005). https://doi.org/10.1007/
978-3-540-31979-5 5
32. Tsang, P.P., Wei, V.K., Chan, T.K., Au, M.H., Liu, J.K., Wong, D.S.: Separa-
ble linkable threshold ring signatures. In: Canteaut, A., Viswanathan, K. (eds.)
INDOCRYPT 2004. LNCS, vol. 3348, pp. 384–398. Springer, Heidelberg (2004).
https://doi.org/10.1007/978-3-540-30556-9 30
33. Unruh, D.: Post-quantum security of Fiat-Shamir. In: Takagi, T., Peyrin, T. (eds.)
ASIACRYPT 2017. LNCS, vol. 10624, pp. 65–95. Springer, Cham (2017). https://
doi.org/10.1007/978-3-319-70694-8 3
34. Zheng, D., Li, X., Chen, K.: Code-based ring signature scheme. Int. J. Netw. Secur.
5(2), 154–157 (2007)