This is the html version of the file https://arxiv.org/abs/2008.06403.
Google automatically generates html versions of documents as we crawl the web.

Location via proxy:   [ UP ]   [Report a bug]   [Manage cookies]    No cookies    No scripts    No ads    No referrer    Show this form

Page 1

arXiv:2008.06403v3 [cs.CR] 30 Jan 2021

1

A New Path to Code-based Signatures via

Identification Schemes with Restricted Errors

Marco Baldi∗, Massimo Battaglioni∗, Franco Chiaraluce∗,

Anna-Lena Horlemann†, Edoardo Persichetti‡,

Paolo Santini∗ and Violetta Weger§

∗ Dipartimento di Ingegneria dell’Informazione, Universit`a Politecnica delle

Marche, Ancona, Italy

† Faculty of Mathematics and Statistics, University of St. Gallen, Switzerland

‡ Florida Atlantic University, Boca Raton, USA

§ Institute of Mathematics, University of Zurich, Zurich, Switzerland

Abstract

In this paper we introduce a variant of the Syndrome Decoding Problem (SDP), that we call

Restricted SDP (R-SDP), in which the entries of the searched vector are defined over a subset

of the underlying finite field. We prove the NP-completeness of R-SDP, via a reduction from the

classical SDP, and describe algorithms which solve such new problem. We study the properties

of random codes under this new decoding perspective, in the fashion of traditional coding theory

results, and assess the complexity of solving a random R-SDP instance. As a concrete application,

we describe how Zero-Knowledge Identification (ZK-ID) schemes based on SDP can be tweaked

to rely on R-SDP, and show that this leads to compact public keys as well as significantly reduced

communication costs. Thus, these schemes offer an improved basis for the construction of code-based

digital signature schemes derived from identification schemes through the well-know Fiat-Shamir

transformation.

I. INTRODUCTION

Public-key cryptography heavily relies on hard mathematical problems, that define the

security target for the scheme by tying the system’s private key to the public one, or a

The work of Edoardo Persichetti and (partially) Paolo Santini is supported by the National Science Foundation under

Grant No. CNS-1906360.

2

plaintext to the corresponding ciphertext. Among the mathematical problems utilized in the

context of public-key cryptography, one of the most studied is that of decoding random linear

codes in the Hamming metric, which was proved to be NP-complete [1], [2] and boasts a

vast literature of algorithms aimed at finding a solution [3]–[10]. Roughly speaking, this

problem asks to find a vector of low Hamming weight, i.e., containing only a few non-null

entries, such that its product with a given parity-check matrix returns a target vector, called

syndrome. For this reason, the problem is known as Syndrome Decoding Problem (SDP).

For decades, SDP has represented the foundation of the area called code-based cryptogra-

phy. Indeed, it allows building efficient and secure cryptosystems, which are largely inspired

by the seminal work of McEliece [11]. However, the situation is not the same for signature

schemes, and the vast majority of attempts to build a code-based signature scheme that is at

the same time secure and efficient were unsuccessful. This is the case, for instance, of the

scheme proposed by Courtois, Finiasz, and Sendrier [12], denoted as CFS in the following,

and its variants, which have tried to address the problem of decoding a random-like syndrome

into a low-weight vector in several ways, but always yielding to either unpractical performance

or even security breaches. The recent work of [13] highlights the fact that, over non-binary

finite fields, the decoding problem remains hard also when the solution is required to have

very high Hamming weight, as opposed to very low. Wave [14] is a signature scheme built

upon this fact, characterized by a public key size that grows as λ2, where λ is the security

level in bits. This provides an important improvement over CFS, although Wave still requires

a public key of 3 megabytes for 128 bits of classical security, which is rather large. All these

classic code-based signature schemes rely on some hidden code structure, which is at the

basis of the public key security and must be protected from attackers.

Constructing signatures via the Fiat-Shamir transform applied to a Zero-Knowledge Iden-

tification (ZK-ID) scheme is a promising alternative to this approach. In fact, code-based

identification schemes do not require any hidden structure, and hence are intrinsically resistant

to structural attacks. However, schemes such as Stern’s [15] feature non-trivial soundness

errors and require many repetitions, leading to very large signature sizes, whereas attempts to

translate the Schnorr-Lyubashevsky approach [16], like in [17], have been shown vulnerable to

attacks based on statistical analysis [18], [19]. Nevertheless, the scheme proposed by Cayrel,

Véron and El Yousfi Alaoui [20], denoted as CVE, has been shown suitable for obtaining

very fast signature schemes with a reduction in the key size in the order of 25% over Stern’s

[21].

3

Our contribution: We introduce a variant of the SDP, in which the solution vector

must take values over a restricted set of the finite field in which both the given code and

the syndrome are defined. For this reason, we denote the corresponding decoding problem

as Restricted SDP (R-SDP), and prove its NP-completeness through a reduction from the

classical SDP in the Hamming metric, over the same finite field. We then focus on a special

case of R-SDP, in which the coordinates of the error vector are chosen from {0, ±1}, and

use classical arguments from coding theory to derive conditions under which, for a random

code, the solution of the problem is unique with overwhelming probability. We assess the

complexity of solving R-SDP, by taking into account recent works that focus on SDP over

a ternary finite field [22], and derive tight estimates for the resulting cost. As a culminating

development of our work, we revisit the CVE scheme with a new formulation based on

restricted errors. Our results show that, using such an approach, we can obtain a noticeable

performance improvement by significantly reducing the communication cost and the public

key size, while preserving the security level.

Outline of the paper: The paper is organized as follows. In Section II we introduce

the notation that will be used throughout the paper and recall some coding theory notions.

In Section III we recall the CVE scheme, which we use as the starting point of our variant.

In Section IV, we introduce the concept of restricted error vectors and study their properties

from a coding-theoretic point of view; we define the associated R-SDP, and prove its NP-

completeness with a reduction from the canonical SDP. In Section V we analyze different

strategies to solve the R-SDP, in the specific case in which the weight of the searched vector

is maximal; in particular, we take into account both brute force approaches and more clever

strategies, which we adapt from recent results holding for the SDP over a ternary finite field

[22]. In Section VI, we adapt the CVE scheme to our new framework, and compare its

performance to that of schemes in the existing literature. Finally, we draw some concluding

remarks in Section VII.

II. PRELIMINARIES

In this section we introduce the notation that will be used throughout the paper, and provide

some basic notions from coding theory.

A. Notation

We denote by [a; b] the set of integers between a and b including a and b. As usual, Fq

denotes the finite field with q elements, where q is a prime power, while F∗

q = Fq \ {0}

4

denotes the multiplicative group of Fq. We use bold upper case (resp. lower case) letters to

denote matrices (resp. vectors). For a matrix A, we refer to its entry in the i-th row and j-th

column as ai,j, and for a vector a we denote its i-th entry by ai. The k × k identity matrix

is denoted by Ik. Let Sn be the symmetric group on n elements, where we will represent

elements σ of Sn as bijections from the integer set [0; n − 1] to itself, and the action on a

length n vector is represented as

σ(a) = (aσ(0),aσ(1), ··· ,aσ(n−1)) .

We will use Mn to denote the set of monomial transformations, i.e., all linear transfor-

mations that can be represented through the action of a permutation and non-zero scaling

factors. In other words, for each τ ∈ Mn, there exist σ ∈ Sn and v ∈ (F∗

q)n such that

τ(a) = (vσ(0)aσ(0),vσ(1)aσ(1), ··· ,vσ(n−1)aσ(n−1)) , ∀a ∈ Fn

q .

We use U(A) to denote the uniform distribution over a set A; for a random variable a, we

write a ∼ D if a is distributed according to the distribution D, and a

$

←− A if a is sampled

according to the uniform distribution over A, i.e., a ∼ U(A).

The support of a vector a ∈ Fn

q is defined as Supp(a) = {j ∈ [0; n − 1] | aj = 0}. For a

set J ⊂ [0; n − 1] and a vector a ∈ Fn

q , we denote by aJ the vector consisting of the entries

of a indexed by J. Analogously, for a set J ⊂ [0; n − 1] and a matrix A ∈ Fk×n

q

, we denote

by AJ the matrix consisting of the columns of A indexed by J.

B. Coding theory preliminaries

Here we briefly recall some basic notions for codes in the Hamming metric.

Definition 1. An [n, k] linear code C over Fq is a linear subspace of Fn

q of dimension k.

Any linear code can be represented by a generator matrix, which has the code as image,

or equivalently by a parity-check matrix, which has the code as kernel.

Definition 2. The Hamming weight of x ∈ Fn

q is equal to the size of its support, i.e.,

wtH(x) :=| Supp(x) |=| {j ∈ [0; n − 1] | xj = 0} | .

The Hamming distance between x and y ∈ Fn

q is defined as the Hamming weight of their

difference, i.e.,

dH{x, y} := wtH(x − y) =| {i ∈ [0; n − 1] | xi = yi} | .

5

The minimum Hamming distance of a code is the minimum of all pairwise non-zero Hamming

distances of the codewords.

The sphere of vectors of Fn

q with Hamming weight ω is denoted by SH

n,q,ω and the ball of

radius ω is denoted by BH

n,q,ω.

In the following proposition we recall the Gilbert-Varshamov bound in the Hamming

metric.

Proposition 3 (Theorem 13.73, [23]). Let q be a prime power, n and dH be positive integers.

There exists a linear code C over Fq of length n and minimum Hamming distance dH, such

that

| C |≥

qn

∑dH−1

j=0 (n

j)(q − 1)j

.

Definition 4. Let q be a prime power and 0 < k ≤ n be positive integers. For a code over

Fq of length n and dimension k, the Gilbert-Varshamov distance is defined as follows

dGV := max{dH ∣

∣

∣

∣

∣

dH−1

∑

i=0 (ni)(q − 1)i < qn−k } .

It is well known [24, Ch. 17, Problem (31)] that random codes in the Hamming metric

asymptotically attain the Gilbert-Varshamov distance with overwhelming probability.

Finally, we formally state the Syndrome Decoding Problem.

Problem 1. Syndrome Decoding Problem (SDP) Given H ∈ F

(n−k)×n

q

, s ∈ Fn−k

q

and t ∈ N,

decide whether there exists e ∈ Fn

q , with wtH(e) ≤ t, such that eH⊤ = s.

As mentioned in the introduction, the SDP is the foundation of code-based cryptography.

In particular, when the Hamming weight t is below the error correction capability following

from the Gilbert-Varshamov bound, the SDP has at most one solution with overwhelming

probability, when q and n are large.

III. ZERO KNOWLEDGE IDENTIFICATION SCHEMES BASED ON SYNDROME DECODING

In this section we focus on the CVE scheme [20]. This scheme will be described in detail

in Section III-B, since it is the scheme to which we apply our new technique (see Section

VI). For the sake of completeness, in Appendix A we also provide a description of a scheme

by Aguilar, Gaborit and Schrek [25], which we will denote by AGS and whose performance

will be compared to that of the scheme we propose.

6

Let us briefly recall the operating principles of such schemes, highlighting their main

features; then, in the following sections, we show how switching to restricted errors leads to

a strong boost in their performance.

A. General principles

Let R be a relation which is satisfied only by specific pairs of objects, such that checking

whether a pair of elements satisfies the relation is efficient (i.e., it can be done in polynomial

time). An identification scheme constructed upon R can be defined as a two-stage procedure,

as follows:

- in the first stage, the prover randomly generates a pair (sk, pk) satisfying R;

- in the second stage, the prover exchanges messages with the verifier, which is only

equipped with pk, with the goal of demonstrating knowledge of sk. At the end of the

protocol, the verifier decides whether to accept the prover or not.

Usually, the key pair is such that pk represents an instance of a hard problem, with sk

being a valid solution. Thus, the difficulty of finding, on input pk, a value sk

∗

that satisfies

the relation, without knowledge of sk, is at the core of the scheme, since authentication is

obtained through the proof of knowledge about the secret key.

An identification scheme is called zero-knowledge if no information about the secret key

is revealed during the identification process. Other required properties for an identification

scheme are completeness and soundness, the former meaning that a honest prover always

gets accepted and the latter requiring that an impersonator has only a small probability of

getting accepted. For a rigorous and complete description of these properties, we refer the

interested reader to [26].

Reducing the communication cost: A crucial quantity to analyze in an identification

scheme is the communication cost, i.e., the cost of a full interaction between the two parties,

which is measured as the number of bits that are exchanged. Many identification schemes are

constructed from Sigma protocols, i.e., three-pass proofs of knowledge for a certain relation.

In this case, the scheme presents a soundness error, meaning that an adversary impersonating

a prover (without access to the secret key) can “cheat” by pre-selecting a candidate response

that works only for a subset of the challenge space, and hope that the chosen challenge is

part of that subset. This implies that an impersonator is able to get accepted with a certain

non-zero probability (e.g., 2/3 or 1/2), which depends on the scheme. It follows that, in

order to achieve an acceptable level of authentication, the protocol is repeated several times,

7

and a prover is accepted only if every instance was answered successfully. If the cheating

probability is η, executing N rounds of the protocol leads to an overall authentication level

of ηN , and N is chosen so that the desired value (e.g., 2−128), is achieved.

In order to illustrate the process, we will analyze the case of the CVE scheme, that is the

main focus of our work. In this scheme, each round is based on the following paradigm:

1) the prover prepares two commitments c0, c1, which are obtained on the base of some

randomness;

2) the two commitments are sent to the verifier; after this exchange, some additional

messages may be exchanged between the two parties;

3) the verifier randomly picks b ∈ {0, 1}, and sends it to the prover;

4) the prover provides information that only allows to verify cb, but not cb⊕1;

5) the verifier checks the validity of cb.

When the protocol is repeated for multiple rounds, it is possible to reduce the overall

communication cost by exploiting the compression technique proposed in [25]. For the

sake of completeness, we summarize this procedure in Fig. 1. Before the 0-th round, the

prover generates the commitments for all the N rounds, and then sends a unique hash value

c = Hash(c0

0,c0

1,...,cN−1

0

,cN−1

1

) to the verifier. In the i-th round, after receiving the challenge

b, the prover sets its response f such that the verifier can compute ci

b, and additionally includes

ci

b⊕1. At the end of each round, the verifier uses f to compute ci

b, and stores it together with

ci

b⊕1. After the final round only, the verifier is thus able to check validity of the initial

commitment c, by computing the hash of all the stored ci

0, ci

1. This way, one hash is sent

at the beginning of the protocol, and only one hash (instead of two) is transmitted in each

round: this way, the number of exchanged hash values reduces from 2N to N + 1. For the

sake of clarity, this compression technique will not be included in the description of the

forthcoming schemes, but we remark that this can be applied, with slight modifications, to

all the schemes we analyze in the rest of the paper.

B. The CVE scheme

The CVE scheme [20] is an improvement of Stern’s [15] and Véron’s [27] identification

schemes, both based on the hardness of decoding a random binary code [1]. The former

scheme relies on non-binary codes over a large finite field. With this choice, the cheating

probability for a single round is reduced from 2/3 of Stern’s 3-pass scheme to

q−1

2q

by using

a 5-pass scheme based on codes over Fq. For the sake of completeness, the CVE scheme is

summarized in Fig. 2. We now briefly recall how the communication cost of this scheme

8

PROVER

VERIFIER

Generate ci

0, ci

1, for i = 0, ··· ,N − 1

Set c = Hash(c0

0,c0

1,...,cN−1

0

,cN−1

1

)

c

−→

←−−−−−−−−−−−−−−−−−−−−−−

Repeat single round for N times

−−−−−−−−−−−−−−−−−−−−−−−→

Check validity of c

GENERIC i-th ROUND

←−−−−−−−−−−−−−−−−−−−−

Exchange additional messages

−−−−−−−−−−−−−−−−−−−−−−→

Choose b

$

←− {0, 1}.

b

←−

Set f := information to compute ci

b

f, ci

b⊕1

−−−−−→

Store ci

b⊕1, compute and store ci

b

Fig. 1. Description of the compression technique for N rounds.

is derived [20, Section 4.2]. We first note that, in order to represent a length-n vector of

weight ω over Fq, we can either use the full vector, or just consider its support, together

with the ordered non-zero entries. The first option requires n ⌈log2(q)⌉ bits, while for the

second one we need ω(⌈log2(n)⌉+⌈log2(q − 1)⌉) bits. By considering the most convenient

choice for each set of parameters n, ω and q, representing a length-n vector of weight ω over

Fq requires ψ(n, q, ω) = min{n ⌈log2(q)⌉ ,ω(⌈log2(n)⌉+⌈log2(q − 1)⌉ )} bits. Furthermore,

objects that have been randomly generated (such as the monomial transformations) can be

compactly represented by the sole seed that is used as input of the pseudorandom generator.

Taking all of this reasoning and the compression technique into account, and denoting with

lHash and lSeed the length of hash values and seeds, respectively, for N rounds of the protocol

we get the following average communication cost:

lHash + N( ⌈log2(q − 1)⌉ + n ⌈log2(q)⌉ +1+ lHash +

ψ(n, q, ω) + lSeed

2

).

9

Public Data Parameters q, n, k, ω ∈ N, parity-check matrix H ∈ F

(n−k)×n

q

Private Key e ∈ SH

n,q,ω

Public Key

s = eH⊤ ∈ Fn−k

q

PROVER

VERIFIER

Choose u

$

←− Fn

q , τ

$

←− Mn

Set c0 = Hash(τ, uH⊤)

Set c1 = Hash(τ(u),τ(e))

c0,c1

−−−→

Choose z

$

←− F∗

q

z

←−

Set y = τ(u + ze)

y

−→

Choose b

$

←− {0, 1}

b

←−

If b = 0, set f := τ

If b = 1, set f := e′ = τ(e)

f

−→

If b = 0, accept if

c0 = Hash(τ,τ−1(y)H⊤ − zs)

If b = 1, accept if wtH(e′) = ω and

c1 = Hash(y − ze′, e′)

Fig. 2. The CVE scheme.

For the maximal communication cost, we take the maximum size of the response, and thus

we obtain

lHash + N( ⌈log2(q − 1)⌉ + n ⌈log2(q)⌉ +1+ lHash + max{ψ(n, q, ω) , lSeed}).

10

In order to derive secure parameters for the CVE scheme, one can proceed as follows. For

a given set of parameters n, k and q, the Gilbert-Varshamov bound is used to estimate the

minimum distance dH of a random code described by an (n − k) × n parity-check matrix H

over Fq. The weight of the private key can then be set as ω = ⌊dH/2⌋, since this guarantees

that there is no other vector of weight smaller than or equal to ω with syndrome equal to

the public key. In order to reach a security level of λ bits, ω must be sufficiently large, such

that using the best known attack algorithms requires a number of operations not lower than

2λ. The authors of [20] have used the analysis due to Peters [28] to estimate the Information

Set Decoding (ISD) complexity, and have proposed two parameters sets:

- q = 256, n = 128, k = 64, ω = 49, for 87-bits security;

- q = 256, n = 208, k = 104, ω = 78, for 128-bits security.

IV. DECODING RANDOM CODES WITH RESTRICTED ERRORS

In this section we introduce a variant of the decoding problem, in which the error vector

is constrained to take values in a subset of the finite field; for this reason, we speak of

restricted errors. In particular, we show that the associated decoding problem is NP-complete

and adapt the Gilbert-Varshamov bound to this case. We also study the complexity of solving

the decoding problem with restricted errors, through adaptions of modern algorithms for the

Hamming case.

A. R-SDP and NP-completeness

In this section we introduce a new variant of the decoding problem, by choosing a set of

vectors over Fq, with q being an odd prime power, whose Hamming weight is below some

threshold value; as an additional restriction, the vectors in the set take values in a specific

subset of the finite field. For the elements of the multiplicative group F∗

q associated to Fq, we

adopt a representation F∗

q = {x1 = 1,x2, ··· ,xq−1}, such that xi +xq−i = 0, for i ∈ [0; q−1

2

].

We will call this representation for the finite field elements “symmetric”; it is evident that,

for the same finite field, many symmetric representations may exist. Note that, when q is a

prime, the canonical symmetric representation is F∗

q = {1, 2,...,q − 1}.

More precisely, for a positive integer a ≤

q−1

2

, that we call the restriction parameter, we

define the restricted Hamming ball of radius t and parameter a as

E

(a)

n,q,t := {e ∈ Fn

q | wtH(e) ≤ t, e ∈ {0, ±x1, ··· , ±xa}n} .

11

Hence, we are focusing on a subset of Fq of size 2a + 1 where, for each element, the set

also contains its additive inverse. We formally define the syndrome decoding problem for a

restricted Hamming ball over an arbitrary finite field as follows.

Problem 2. Restricted Syndrome Decoding Problem (R-SDP) Let q = pm, with p = 2

being a prime and m ∈ N, and denote by Fq the corresponding finite field with q elements,

described through a symmetric representation. On input H ∈ F

(n−k)×n

q

, s ∈ Fn−k

q

and t ∈ N,

decide whether there exists an e ∈ E

(a)

n,q,t, such that eH⊤ = s.

The above problem is obtained by applying an additional restriction to the classical SDP

over a finite field Fq. It may thus seem intuitive that, like SDP, R-SDP belongs to the

hierarchical class of NP-complete problems. A formal proof of this property is provided in

the following theorem. Note that, in our proof, the restriction parameter a is not treated as

an input to R-SDP, since we can prove the NP-completeness for any fixed value of a.

Theorem 5. R-SDP is NP-complete.

Proof: We provide a reduction from the classical SDP in the Hamming metric, defined

over Fq, as formulated in Problem 1. This was proved to be NP-complete in [2].

Clearly, the finite field representation does not interfere with the definition of the problem;

thus, we directly consider a symmetric representation for the field. From now on, for the

sake of simplicity, we will denote F

(a)

q

= {0, ±x1,..., ±xa}.

We denote by {H, s,t} an arbitrary instance of SDP, and map it into an R-SDP instance,

that we denote by {H′, s,t}. If q = 3, then we can set H′ = H; otherwise, we construct H′

according to the following procedure. We first select a set U ⊆ F∗

q, such that every element

of F∗

q can be obtained as the product of one element from F

(a)

q

and one from U, that is

∀b ∈ F∗

q ∃u ∈ U, x ∈ F(a)

q

such that − xu = b or xu = b.

It is easily seen that, for all possible sets F

(a)

q , a choice for U always exists and for its

cardinality, that we denote by v, it is straightforward to show that ⌊

q−1

2a

⌋ ≤ v ≤ q −1. It may

also happen that, for the same element of F∗

q, more than one pair of factors from U and F

(a)

q

exists but, for our purposes, this is not an issue. Let u = (u0,...,uv−1) be a vector formed

by the elements of U: we finally obtain H′ as

H′ = [ u ⊗ h0

u ⊗ h1

··· u ⊗ hn−1 ],

12

where ⊗ denotes the Kronecker product and hi is the i-th column of H. This way, H′ has

n − k rows and n′ = nv columns, given by

h′

iv+j = ujhi, i ∈ [0; n − 1], j ∈ [0; v − 1].

We first show that, to each e′ ∈ (F

(a)

q )n′

such that e′H′⊤ = s, we can associate a vector

e ∈ Fn

q such that eH⊤ = s. In fact, consider that, ∀i ∈ [0; n − 1],

v−1

∑

j=0

e′

iv+jh′

iv+j = (

v−1

∑

j=0

e′

iv+juj)hi = βihi,

where βi ∈ Fq. On the one hand, it is easily seen that, if e′

iv+j = 0 for all j ∈ [0; v −1], then

βi = 0 as well. For the other cases, it might happen that βi = 0. The number of coefficients

βi that are non-zero is surely smaller than or equal to wtH(e′) and, if s = 0r, then at least

one of the βi must be non-zero. Let e ∈ Fn

q , such that ei = βi, ∀i ∈ [0; n − 1]: it is then

immediately seen that eH⊤ = s, and wtH(e) ≤ wtH(e′) ≤ t. If e′ ∈ E

(a)

n′,q,t

, then e has weight

smaller than or equal to t: existence of an e′ satisfying the constructed R-SDP instance, then,

implies existence of an e satisfying the initial SDP instance.

Finally, we show that e′ ∈ E

(a)

n′,q,t

exists if and only if a desired e exists, i.e., if the initial

SDP instance is a “yes” instance. In fact, as a consequence of the requirements on U, for

each βi we can always write

βi = λiuℓi xyi ,

for proper indices ℓi ∈ [0; v−1], yi ∈ [1; a] and λi ∈ {±1}. Then, we can always build a vector

e′ ∈ E

(a)

n′,q,thaving at most one non-zero entry among the ones in positions {iv, ··· , iv+v−1},

whose elements are defined as

e′

iv+j = 



λixyi

if j = ℓi,

0

elsewhere.

This vector has the same weight as e, and is such that eH⊤ = e′H′⊤. Given the bijection

between e and e′, it becomes clear that solving the given R-SDP instance means solving the

initial SDP instance. It follows that R-SDP is NP-complete.

We have a two-fold motivation to study R-SDP, arising from our interest in identification

schemes based on syndrome decoding. Firstly, in these schemes, the proof of knowledge is

provided by publishing a masked version of the secret key, which is a low-weight vector over

Fq. As already stressed in the previous sections, a crucial quantity to study the performance of

an identification scheme is the communication cost per round. Vectors with restricted entries

13

can clearly be represented with a lower number of bits, compared to vectors over the full field

Fq. Thus, we expect the performance of these schemes to benefit from the use of restricted

vectors. For this reason, from now on we limit our attention to the case of a = 1, which leads

to the lowest communication cost, since we impose the maximal non-trivial restriction to the

subset B. Secondly, these schemes are parameterized by choosing the weight of the secret

error vector as large as possible, but in such a way that only few solutions exist. We then

study the cost of the best known algorithms to solve the SDP adapted to this scenario. For a

random code, the minimum Hamming distance is estimated via the Gilbert-Varshamov bound,

which only depends on the code length, dimension and on the finite field size. We generalize

all these concepts to the case of restricted vectors, and derive conditions to guarantee that,

for a given random code, only a few solution to the R-SDP exist. Our results show that, for

random codes with the same parameters, we can achieve higher security levels by relying

on R-SDP instead of SDP. As we show more extensively in Section VI, our results lead to

strong improvements in the performances of already existing identification schemes.

B. Restricted minimum distance and properties of random codes

In this section we study the properties of random linear codes regarding the weight of

codewords with restricted entries. As mentioned before, we will focus on the case a = 1

and, to ease the notation, we will simply use En,q,t := E

(1)

n,q,t to denote the ball of vectors

with entries in {0, ±1} and with Hamming weight not larger than t. Since the sum of two

vectors in E

(1)

n,q,t results in a vector in E

(2)

n,q,t, we also need to study the latter ball. Our goal

is to derive conditions upon which, for a given code over Fq, with q ≥ 5 being an odd prime

power, the R-SDP has at most a unique solution with overwhelming probability.

Definition 6. Let q ≥ 5 be an odd prime power, and denote by Fq the corresponding finite

field with q elements, described with a symmetric representation. For a ∈ Fn

q , we define the

restricted weight of a as

˜wt(a) :=







#1(a)+2 · #2(a) if a ∈ {0, ±1, ±2}n,

∞

otherwise,

where #1(a) is the number of entries of a equal to ±1 and #2(a) is the number of entries

equal to ±2.

Note that, since q is a prime, the restricted weight of a vector over {0, ±1, ±2} corresponds

to its Lee weight [29].

14

Definition 7. Let q ≥ 5 be an odd prime power, and denote by Fq the corresponding finite

field with q elements, described with a symmetric representation. Let C be a linear code with

length n over Fq. We define its restricted minimum distance as

˜d:= min

{

˜wt(c) | c ∈C∩{0, ±1, ±2}n \ {0n}}.

If C∩{0, ±1, ±2}n = {0n}, then we set ˜d= ∞.

Note that the corresponding restricted distance is not a proper metric, but a pre-metric,

and that the restricted minimum distance of C is equal to the minimum Lee distance of

C∩{0, ±1, ±2}n. Its importance is stated in the following theorem.

Theorem 8. Let q ≥ 5 be an odd prime power, and denote by Fq the corresponding finite

field with q elements, described with a symmetric representation. Let C be a code over Fq,

with length n and restricted minimum distance ˜d. For any parity-check matrix H for C, and

for all t < ˜d/2, there cannot exist two distinct vectors e, e′ ∈ En,q,t such that eH⊤ = e′H⊤.

Proof: If eH⊤ = e′H⊤, then necessarily ˜e = e − e′ ∈ C. Furthermore, given that

e, e′ ∈ {0, ±1}n and e = e′, we have ˜e ∈ {0, ±1, ±2}n and ˜wt(˜e) ≤ 2t. This contradicts the

fact that the restricted minimum distance of C is ˜d > 2t.

Note that, if a code has no codewords (apart the zero one) living in {0, ±1, ±2}n, then

its restricted minimum distance is infinite and all vectors over {0, ±1} correspond to distinct

syndromes.

Analogously to the Hamming metric, we define a ball of radius t and center a ∈ Fn

q as

the set of all vectors whose difference with a has restricted weight smaller than or equal to

t, that is

˜B(a, t, q, n) :=

{x ∈ Fn

q | ˜wt(x − a) ≤ t

}.

(1)

The volume of each such ball does not depend on its center but only on its radius, hence we

get the following.

Proposition 9. Let q ≥ 5 be an odd prime power, and n and t ≤ 2n be positive integers.

Then the size of a restricted ball in Fn

q of radius t, as defined in (1), is given by

˜V(n, t) :=

t

∑

i=0

⌊i/2⌋

∑

j=max{0,i−n} (nj)(n − j

i − 2j)

2i−j.

Note that this is the same as the size of the Lee ball of radius t in Fn

5 , which can be found

in [30, Proposition 8, Corollary 9].

15

In the following theorem we derive a bound which, in the same fashion of the Gilbert-

Varshamov bound, states the minimal maximum dimension for a code achieving a given

restricted minimum distance.

Theorem 10. For a given finite restricted minimum distance ˜d and length n, there exists a

code in Fn

q of dimension ˜

k, where

˜

k ≥ n − 1 − logq (

˜V(n, ˜d− 1)

)

= n − 1 − logq 



˜d−1

∑

i=0

⌊i/2⌋

∑

j=max{0,i−n} (nj)(n − j

i − 2j)

2i−j

.

Proof: Let C ⊆ Fn

q with restricted minimum distance ˜d and maximum dimension

˜

k. In

the following we show that for every vector x ∈ Fn

q , there must be at least an αx ∈ F∗

q and

a codeword c in C such that ˜wt(αxx − c) ≤ ˜d− 1 or, analogously, αxx ∈ ˜B(c, ˜d− 1, q, n).

In other words, for each x ∈ Fn

q , at least one of its scalar multiples is contained in the ball

of radius ˜d− 1 with center in a codeword of C. Note that, if x ∈ C, then this is trivially true

since it is enough to consider a sphere with center in x; to show that this holds for all vectors

in the space, we consider x ∈ C. If there is no pair (αx, c) satisfying the above requirement,

then we can consider a new code C′, defined as

C′ = {βx + c | β ∈ Fq, c ∈ C} .

Such a code will be linear and will have dimension

˜

k+1. Furthermore, its restricted minimum

distance will not be lower than that of C, because by hypothesis all “new” codewords βx+c,

with β = 0, are outside of balls of radius ˜d− 1 centered in codewords of C. However, the

existence of C′ contradicts the fact that, by hypothesis, C has maximum dimension: thus, it

must be

∀x ∈ Fn

q ∃αx ∈ F∗

q, c ∈ C s.t. αxx ∈ ˜B(c, ˜d− 1, q, n).

Let A be the set of all valid vectors αxx: for a given x, we include all the scalar multiples

such that the above condition is verified. It is easily demonstrated that

qn−1 ≤| A |≤ qn.

In fact, A ⊆ Fn

q proves the upper bound, while the lower bound is obtained by assuming that

for each x, only one scalar multiple satisfies the condition. Given that A = ⋃c∈C ˜B(c, ˜d−

1, q, n), we consider the following chain of inequalities

qn−1 ≤ |A| = ∣∣∣∣

∣

⋃

c∈C ˜B(c, ˜d− 1, q, n)

∣

∣

∣

∣

∣

≤ ∑

c∈C ∣

∣

∣˜B(c,

˜d− 1, q, n)

∣

∣

∣ = q

˜k ˜V(n, ˜d− 1).

16

Simple further computations yield the claimed inequality.

Starting from the previous theorem, in the same fashion of the commonly called Gilbert-

Varshamov distance for the Hamming metric, we define the restricted Gilbert-Varshamov

minimum distance.

Definition 11. For a code with length n and dimension k over Fq, with q ≥ 5 being an odd

prime power, we define the restricted Gilbert-Varshamov distance as follows

˜dGV := 



∞

if ˜V(n, 2n) < qn−k−1,

max {˜d > 0

∣

∣

∣˜V(n,

˜d) ≤ qn−k−1 } otherwise.

Analogously to the classic formulations, the restricted Gilbert-Varshamov distance tells us

the maximum distance that a code of fixed length and rate can achieve. Note that ˜V(n, 2n) =

5n, and hence for large values of q and/or n (if q > 5), the restricted Gilbert-Varshamov

distance is equal to ∞, as long as k<n(1 − logq(5) − 1

n

). Thus, it makes sense to study

the probability with which a random code achieves this restricted minimum distance; in the

next theorem we show that this probability is bounded from below by a quantity that, as the

code length increases, asymptotically tends to 1.

Theorem 12. Let q > 5 be an odd prime power and k ≤ n (1 − logq(5) − ǫ), for 0 <

ǫ < 1 − logq(5). Let G

$

←− Fk×n

q

with rank k. Then the code generated by G has restricted

minimum distance ˜d= ∞ with probability at least 1 − q−ǫn.

Proof: First, the requirements on k and ǫ assure that 0 <k<n. The code generated by

G will have restricted minimum distance ˜d = ∞ if all its codewords (apart from the zero

one) do not live in {0, ±1, ±2}n. We first focus on a single codeword: since the entries of G

are random over Fq, each linear combination of the rows of G is a random length-n vector

with entries over Fq, as well. Thus, the probability that this codeword has a finite restricted

weight (i.e., it takes values in {0, ±1, ±2}) is

|{0, ±1, ±2}n \ 0n|

∣

∣Fn

q \ 0n∣

∣

=

5n − 1

qn − 1

<

5n

qn

= q−n(1−logq(5)).

Since there are qk codewords, from a union bound argument we get that the probability that

the code contains at least a codeword of restricted weight smaller than or equal to 2n is at

most

qkq−n(1−logq(5)) ≤ qn(1−logq(5)−ǫ)q−n(1−logq(5)) = q−ǫn.

17

Then, q−ǫn is an upper bound on the probability that the code generated by G contains at

least a codeword with finite weight; taking its complement, we obtain a lower bound on the

desired probability.

Note that, in Theorem 12, we need to assume q > 5; in fact, any non-zero code in Fn

5

must contain non-zero codewords from {0, ±1, ±2}n = Fn

5 and hence the restricted minimum

distance will always be finite.

V. SOLVING R-SDP WITH MAXIMUM WEIGHT

In this section we describe how R-SDP can be solved, in the particular case in which

the restricted weight of the searched vector is maximal (i.e., equal to the code length). We

focus on this particular case since it is the one we consider for our modification of the CVE

scheme, which we introduce in the next section. We chose this restriction since, as we show

in the next section, it is the one yielding the best performance in our target application.

Note that one can also rely on ISD algorithms to solve R-SDP; however, when the weight is

maximal, then ISD algorithms collapse to the brute force approach described in Section V-A.

Indeed, since the searched vector contains no zero elements, the whole procedure of an ISD

is reduced to searching for all possible vectors in the chosen information set. For solving

the R-SDP with arbitrary restricted weight, we note that one can use any ternary ISD, e.g.,

Peter’s generalization [28] of Stern’s algorithm [7]. The only difference to this algorithm is

that the operations are performed not over F3 but over Fq, thus we assume that addition has

a cost of ⌈log2(q)⌉ and multiplication has a cost of ⌈log2(q)⌉

2

.

Let us consider a random code with length n and dimension k, described by H ∈ F

(n−k)×n

q

,

and s ∈ Fn−k

q

, where s

$

←− {He⊤ | e ∈ {±1}n}. In other words, we assume that the given

R-SDP instance has at least one solution.

We start by determining the number of solutions that exist on average.

Proposition 13. Let H ∈ F

(n−k)×n

q

be the parity-check matrix of a random code with rate

R = k/n. Let s

$

←− {eH⊤ | e ∈ {±1}n}, and let us denote the set of length-n vectors with

entries over {±1} and syndrome equal to s as M. Then, unless n is very small, the average

cardinality of M is

M ≈ 1+2n(1−(1−R) log2(q)).

(2)

Proof: The thesis results from simple combinatorial arguments. First, we know that

the existence of at least one solution is guaranteed. Let e ∈ {±1}n such that s = eH⊤, and

V = {±1}n \e. Since we are considering a random code, we have that H is a random matrix,

18

hence sums of its columns will yield random vectors over Fn−k

q

. Thus, for each e′ ∈ V , we

can assume that e′H⊤ is random over Fq; therefore, the probability that the product equals

s is given by q−(n−k). Hence, on average, the cardinality of M is

M =1+

|V |

qn−k

=1+

2n − 1

qn−k

≈ 1 +

2n

qn−k

=1+2n(1−(1−R) log2(q));

notice that the approximation in this expression holds unless n is really small.

Note that this result implies that for growing q and/or n there will be most likely only one

solution, which concurs with the result in Theorem 12.

We now proceed by describing how the R-SDP can be solved in the considered setting.

We first consider a basic brute force approach, and then take into account the analysis in

[22] to derive a more efficient approach based on merging.

A. Brute force approach

Given H, we can choose a permutation π ∈ Sn and a full rank matrix S ∈ F

(n−k)×(n−k)

q

such that Sπ(H)=[H′

In−k], where π(H) denotes the matrix obtained by permuting the

columns of H according to π, and H′ ∈ F

(n−k)×k

q

. Notice that, if eH⊤ = s, then π(e) is

going to be a solution to the R-SDP instance defined by the parity-check matrix Sπ(H) and

syndrome s′ = Ss. Let us write x = (x0, x1), with x0 ∈ {±1}k and x1 ∈ {±1}n−k. Then

we want the following condition to be verified

x0H′⊤ + x1 = s′,

from which x1 = s′ − x0H′⊤. Thus, to solve the R-SDP, it is enough to go through vectors

x0 ∈ {±1}k and, for each candidate, compute the corresponding x1 and test whether it has

entries over {±1}. As soon as such a vector is found, we have a solution to the initial R-SDP,

that is, π−1([x0, x1]).

We can estimate the complexity of the above approach as follows.

Proposition 14. Let (H, s), with H ∈ F

(n−k)×n

q

drawn at random with rank n − k, and s

$

←−

{eH⊤ | e ∈ {±1}n}. With the brute-force approach, one can solve the R-SDP represented

by (H, s) with the following average cost

(n − k)2(n + 1) ⌈log2(q)⌉

2

∏n−k

j=1 (1 − q−j)

+

2k

1 + M

·

q

q − 2

k⌈log2(q)⌉,

where M =1+2n(1−(1−R) log2(q)) is the average number of solutions.

19

Proof: We neglect the cost of the column permutation. It is immediately seen that

∏n−k

j=1 (1 − q−j) corresponds to the probability that a random matrix of size n − k and

entries over Fq is non singular; given that H is random, ∏

n−k

j=1 (1 − q−j) also corresponds to

the probability that π(H) can be put into systematic form. To do this, we use Gaussian

elimination, with an overestimating cost given by (n − k)2(n + 1) ⌈log2(q)⌉

2

. Once we

have transformed both H and s, we start by testing vectors x0 ∈ {±1}k. For each vector,

we compute the corresponding x1, with a cost of k ⌈log2(q)⌉. For this we consider early

abort, i.e., we test simultaneously if the entries of x1 are in {±1}. A random element in Fq

has probability

q−2

q

to not be in {±1}, thus on average we can abort after computing

q

q−2

many entries. The expected number of existing solutions is M =1+2

n(1−(1−R) log2(q)) (see

Proposition 13). Thus, we have M vectors x0 leading to a solution: on average, before we

find one solution, we test 2k/(1 + M) candidates for x0.

B. Using the PGE+SS framework

We notice that the R-SDP, for q = 3, is essentially identical to the so-called ternary

syndrome decoding problem, i.e., the problem of decoding a random linear code defined

over F3. For such a problem, the state-of-art solver is described in [22], and follows the so-

called Partial Gaussian Elimination plus Subset Sum (PGE+SS) framework, briefly recalled

in the following. We directly adapt such a framework to our case, and parameterize the whole

description of the algorithm on an integer ℓ ∈ [1; n − k], whose meaning will be clarified

next. The PGE+SS approach is characterized by the following four consecutive steps:

1) Permutation: pick a random π ∈ Sn and apply π(H) by permuting the columns of H

according to π.

2) PGE: divide π(H) into four blocks, that is

π(H) = 



H′

0 ∈ F

(n−k−ℓ)×(n−k−ℓ)

q

H′

1 ∈ F

(n−k−ℓ)×(k+ℓ)

q

H′

2 ∈ F

ℓ×(n−k−ℓ)

q

H′

3 ∈ F

ℓ×(k+ℓ)

q











.

If H′

0 is singular, return to step 1, otherwise reduce π(H), i.e., find S ∈ F

(n−k)×(n−k)

q

,

such that

Sπ(H) = 



In−k−ℓ

H′ ∈ F

(n−k−ℓ)×(k+ℓ)

q

0ℓ×(n−k−ℓ)

H′′ ∈ F

ℓ×(k+ℓ)

q











.

Write sS = [s′, s′′], with s′ ∈ Fn−k−ℓ

q

and s′′ ∈ Fℓ

q.

20

3) Small R-SDP: produce a set E ⊆ {±1}k+ℓ containing (some) solutions to the R-SDP

instance represented by H′′ and s′′, i.e., such that

s′′ = H′′e′′⊤, ∀e′′ ∈ E.

4) Test: for each e′′ ∈ E, test whether e′ = s′ − e′′H′⊤ has entries over {±1}. If such a

vector e′ is found, return π−1([e′, e′′]); otherwise, restart from step 1.

We now briefly explain the rationale behind the procedure. First, for each e ∈ {±1}n such

that s = eH⊤, it also holds that sS = π(e)(Sπ(H))

⊤

. Let us write π(e)=[e′, e′′]; then







e′ + e′′H′⊤ = s′,

e′′H′′⊤ = s′′.

(3)

Notice that the pair (H′′, s′′) corresponds to another R-SDP instance, since the unknown e′′

has length k +ℓ and restricted weight k +ℓ. This instance is characterized by a smaller size,

since H′′ defines a code with length k + ℓ ≤ n and dimension k; since H is random, H′′ is

random as well. Let M denote the set of solutions to the initial R-SDP instance: for each

vector in M, an associated solution to the small instance exists. Namely, let M′ be the set

formed by the last k +ℓ entries of the vectors obtained by permuting those in M, according

to π: each vector in M′ is a solution for the small instance. Thus, every time E and M′ are

not disjoint, we have that each vector in their intersection can be used to build a solution for

the initial R-SDP instance. The rationale of this procedure is in the fact that, depending on

ℓ, building solutions to the small instance may be significantly easier. However, we remark

that the value of ℓ must be carefully optimized: indeed, when it is too low, the small instance

may be pretty easy to solve but, as a side-effect, it may have too many solutions and testing

them may become rather time consuming.

In the following section we describe how the small R-SDP instance can be solved relying

on Wagner’s algorithm [31]. In order to assess the complexity of this approach, we study the

algorithm under the assumption that it succeeds when it finds one of the vectors in M′. In

other words, if we find a vector e′′ ∈ {±1}k+ℓ such that e′′H′′⊤ = s′′ but e′′ ∈ M′, then we

do not consider this as a valid solution. We assume that the cardinality of M′ is the same

as that of M, and we estimate it through (2). Notice that this is a conservative assumption

because, in principle, it may happen that the cardinality of M′ is smaller than that of M.

Indeed, when we permute the vectors in M and consider only their last k +ℓ entries, it may

happen that two (or more) of the vectors obtained are identical.

21

C. Solving the small instance with Wagner’s algorithm

As in [22], we rely on Wagner’s algorithm to solve the small instance, which can be

rewritten in the form of a subset sum problem, where the elements of the given set correspond

to the columns of H′′ and can be seen as elements of the finite field with qℓ elements. Let

us consider a general description of Wagner’s algorithm and analyze its complexity. We

anticipate the conclusion that, differently from the case of the ternary SDP studied in [22],

in our case the most convenient approach is to rely on Wagner’s algorithm structured on just

one level.

The structure of Wagner’s algorithm depends on a positive integer a, which defines the

number of levels upon which the algorithm is divided. The set [0; k+ℓ−1] is partitioned into

2a sets Ji of approximately the same size (k+ℓ)/2a. Without loss of generality, we can assume

that the entries of each set Ji are consecutive, i.e., Ji = {⌊i · k+ℓ

2a ⌋,..., ⌊(i + 1) · k+ℓ

2a ⌋ − 1},

for i ∈ [0; 2a − 1]. For the sake of simplicity, we assume that 2a divides k + ℓ: thus, all sets

Ji have the same size k+ℓ

2a . Let H′′

j denote the ℓ × k+ℓ

2a

matrix formed by the columns of H′′

that are indexed by Ji.

We start on level 0 by choosing random subsets R0,..., R2a−1 from {±1}

k+ℓ

2a , each with

size 2v, where v is arbitrary, and building the initial lists

L

(0)

j

= {(z = pH′′⊤

j

, p)∣∣ p ∈ Rj}, for j ∈ [0; 2a − 2],

(4)

L

(0)

2a−1 = {(z = pH′′⊤

2a−1 − s′′ , p)∣∣ p ∈ R2a−1} .

(5)

The algorithm then proceeds, in each level, by pairwise merging the input lists, as explained

in detail below, and using the resulting lists as the input for the subsequent level; this

procedure halts when, in the a-th level, one remains with only one list. In each level, the

number of input lists equals 2a−i+1 and the number of the produced lists is 2a−i. In order to

merge the lists, the algorithm uses a − 1 positive integers 0 < u1 < u2 < ... < ua−1 < ℓ;

furthermore, we set u0 = 0 and ua = ℓ. In order to merge the lists in the i-th level, for

i ∈ [1; a] we use the following procedure: from two lists L

(i)

2j and L

(i)

2j+1, with j < 2a−i − 1,

we produce the list

L

(i+1)

j

= L

(i)

2j ⊓ui L

(i)

2j+1

= {(z2j + z2j+1, [p2j, p2j+1]) | (zb, pb) ∈ L

(i)

b , z2j + z2j+1 = 0 in the last ui entries}.

When the level a is reached, only one list remains, containing vectors p ∈ {±1}k+ℓ such

that pH′′⊤ = s′′.

22

Final set of solutions

Merge on remaining ℓ − u0 positions

L

(0)

0

L

(0)

1

L

(0)

2

L

(0)

3

Merge on u0 positions

u0

u0

ℓ − u0

ℓ

Level 0

Level 1

Level 2

Fig. 3. Wagner’s algorithm structured on two levels.

The whole procedure is detailed in Algorithm 1, while a graphical description of the

algorithm, for the case of a = 2, is shown in Figure 3.

Algorithm 1: Wagner’s algorithm structured on a levels

Input: H′′

0, ··· , H′′

2a−1 ∈ F

ℓ× k+ℓ

2a

q

, s′′ ∈ Fℓ

q, v ∈ N such that v ≤ k+ℓ

2a , a − 1 positive

integers u1 < ··· < ua−1 < ℓ.

Output: A list L

(a)

0

= {(pH′′⊤ , p)} such that p ∈ {±1}k+ℓ and pH′′⊤ = s′′

1 Set u0 = −1, ua = ℓ.

2 Choose random subsets R0, ··· , R2a−1 ⊆ {±1}(k+ℓ)/2, each of size 2v.

3 Build the lists L

(0)

j

= {(z = pH′′⊤

j , p) | p ∈ Rj} for j ∈ [0; 2a − 2].

4 Build the list L

(0)

2a−1 = {(z = pH′′⊤

2a−1 − s′′ , p)∣∣ p ∈ R2a−1}.

5 for i = 1 to a do

6

for j = 0 to 2a−i − 2 do

7

L

(i+1)

j

= L

(i)

2j ⊓ui L

(i)

2j+1

8 return L

(a)

0

Let us explain the rationale of the algorithm. For x such that xH′′⊤ = s′′, we indicate with

23

xi the vector formed by the entries of x that are indexed by Ji. Notice that

2a−1

∑

j=0

xjHj

′′⊤ = s′′.

(6)

Wagner’s algorithm searches for solutions of the R-SDP instance (H′′, s′′) by exploiting

the representation in (6): one starts with lists of candidates for each sub-vector xj and, in

each level, filters them to obtain, in the end, a set of solutions. In the final step, i.e., on

level a, we get a final list of solutions of the smaller R-SDP, since we look for vectors

adding up to s′′. Since the lists are only chosen of size 2v, the algorithm is probabilistic.

We remind that we are interested in finding specific solutions to the small R-SDP instance,

namely, we want Wagner’s algorithm to find one of the vectors in M′; moreover, we assume

|M′| = M =1+2n(1−(1−R) log2(q)). In the next proposition we derive the probability that

Wagner’s algorithm ends with a success.

Proposition 15. We consider Wagner’s algorithm based on a levels, with parameters 0 <

u1 < ··· < ua−1 < ℓ and with initial lists of size L0 = 2v, with v ≤ k+ℓ

2a . We assume that

the cardinality of M′ is M =1+2n(1−(1−R) log2(q)), and that each vector in M′ is random

over {±1}. Then, the probability of finding a valid solution is

1 − (1 − 2v2a−k−ℓ−δ log2(q))M

,

with δ = ∑

a−1

i=1 ui2a−1−i.

Proof: Let x ∈ M′ be one of the solutions. First, Wagner’s algorithm searches a solution

over R0 ×···×R2a−1 ⊆ {±1}k+ℓ. It is clear that whenever x ∈ R0 ×···×R2a−1 then

x will never be included in the final list. Thus, the probability that x actually is among the

considered vectors is

( L0

2

k+ℓ

2a )2a

= 2v2a−k−ℓ.

Notice that, even when x is among the explored vectors, it may be filtered as a consequence

of lists merging. Indeed, let us divide x into 2a chunks, each formed by k+ℓ

2a

consecutive

entries, which we denote as xj, for j ∈ [0; 2a −1]. Let us consider the merge in the ith level:

x will not be filtered in this level if and only if

1. for j ∈ [0; 2a−i − 2], x2jH′′⊤

2j + x2j+1H′′⊤

2j+1 contains only zeros in the last ui − ui−1

positions;

2. x2a−i+1−2H′′⊤

2a−i+1−2

+ x2a−i+1−1H′′⊤

2a−i+1−1

− s′′ contains only zeros in the last ui − ui−1

positions.

24

Note that conditions 1 and 2 are actually not independent: indeed, it is easily seen that if

condition 1 is met, then condition 2 is met as well. Given that both H′′ and x are random, in

each merge, chunks x2j and x2j+1 will not be filtered out with probability q−ui+ui−1 . Given

that, for j ∈ [0; 2a−i −2], we perform 2a−i −1 merges, condition 1 is verified with probability

(q−ui+ui−1 )2a−i−1

= 2−(2a−i−1)(ui−ui−1) log2(q).

Hence, the above equation corresponds to the probability that x is not filtered in the ith level.

Thus, the probability of x surviving till the last level is

a−1

∏

i=1 (q−(ui−ui−1))2a−i−1

= 2− log2(q) ∑a−1

i=1 (2a−i−1)(ui−ui−1),

where u0 = 0. With simple further computations, the above probability can be expressed

as 2−δ log2(q), where δ is as in the claim. In the end, the probability that a particular x is i)

explored through the initial lists, and ii) not filtered, is

2v2a−k−ℓ−δ log2(q).

Since we assume that M′ contains M vectors, which are independent and random over {±1},

we easily derive the probability of finding at least one of them as the complementary of the

probability that we are not able to find any of these vectors.

Roughly speaking, the complexity of Wagner’s algorithm can be estimated with the max-

imum size of the produced lists. Indeed, in order to merge two lists of some size, one can

first join and sort the two lists and then proceed by finding pairs of vectors which sum up

to zero in some prescribed coordinates. Neglecting polynomial or logarithmic factors, the

complexity corresponds to the list size. Let us now derive an expression for the list size

growth in Wagner’s algorithm. In the initial level, we prepare lists of size L0 = 2v. In the

first level, i.e., for i = 1, the average size of the lists is given by L1 = L2

0/qu1 = 22v−u1 log2(q).

In the i-th level, for i ≥ 1, the average size of the lists L

(i)

j

is Li =

L2

i−1

qui−ui−1. Thus, for i ≥ 0

we have

Li = 2v2i−γ(i) log2(q), with γ(i) = 



0

if i = 0,

ui + ∑

i−1

m=1 2i−1−mum

otherwise.

(7)

Taking the maximum of these sizes, and dividing it by the probability that Wagner’s

algorithm finds a solution, we estimate its asymptotic complexity. As mentioned above, list

merging can be performed with a cost that (neglecting polynomial and logarithmic factors)

corresponds to the list size (see Appendix B for more details on how this cost can be estimated

25

in the finite regime). Hence, a rough estimate of Wagner’s algorithm complexity is as in the

next proposition.

Proposition 16. We consider Wagner’s algorithm based on a number of levels equal to a,

with parameters 0 < u1 < ··· < ua−1 < ℓ and with initial lists of size L0 = 2v, with

v ≤ k+ℓ

2a . We assume that the cardinality of M′ is M = 1+2n(1−(1−R) log2(q)), and that M′ is

uniformly distributed in {±1}k+ℓ. Then, neglecting polynomial and logarithmic factors, we

estimate the cost of Wagner’s algorithm as

maxi∈[1;a] {2v2i−γ(i) log2(q)}

1 − (1 − 2v2a−k−ℓ−δ log2(q))

M

,

where δ = ∑

a−1

i=1 ui2a−1−i. When M2v2a−k−ℓ−δ log2(q) is small, we have 1−(1 − 2v2a−k−ℓ−δ log2(q))M

≈

M2v2a−k−ℓ−δ log2(q), and the cost becomes

maxi∈[1;a] {2k+ℓ+log2(q)(δ−γ(i))−v(2a−2i)}

M

.

For all the cases we consider, the best setting for Wagner’s algorithm always results to be

that with a = 1. In order to provide a practical evidence of this fact, let us focus (as in [22])

on the case of amortised lists, i.e., the one in which all lists have the same average size,

corresponding to that of the initial ones (that is, 2v for some v ≤ k+ℓ

2a ). It is easy to see that

this happens if we choose ui = i v

log2(q)

, which leads to δ =

v(2a−1−1)

log2(q)

. Thus, we estimate the

cost of Wagner’s algorithm as

2v

M2v2a−k−ℓ−v(2a−1−1) =

2v

2v(2a−1+1)−k−ℓ+log2(M)

= 2k+ℓ−log2(M)−v2a−1

.

Let us compare this case with that of a = 1, with initial lists of sizes 2

k+ℓ

2

: in such a case,

the asymptotic complexity is 2

k+ℓ

2

. Wagner’s algorithm with more than one level will then

be more convenient if 2k+ℓ−log2(M)−v2a−1 < 2

k+ℓ

2

, that is

v >

k + ℓ

2a

− log2(M).

Remember that it must be v ≤ k+ℓ

2a : thus, unless M is very large, either there are no values

of v for which a > 1 becomes convenient or, even if they exist, they lead to a really limited

advantage in the algorithm cost. For instance, if the solution is unique (i.e., if M = 1), there

are no values of v for which a > 1 is convenient and the performance of Wagner’s algorithm

gets worse if a increases over 1.

We remark that the range of convenient values for v is actually thinner, since we are

neglecting polynomial factors which increase when a increases.

26

Based on the above considerations, we are ready to derive a closed formula for the

complexity of solving the initial R-SDP instance using Wagner’s algorithm on one level.

The whole procedure we consider is reported in Algorithm 2, and its cost is detailed in the

next proposition.

Algorithm 2: PGE+SS approach, using Wagner’s algorithm with a = 1.

Input: H ∈ F

(n−k)×n

q

, s ∈ Fn−k

q

, ℓ ∈ {1,...,n − k}, v ∈ N such that v ≤ k+ℓ

2

Output: A e ∈ {±1}n such that eH

⊤ = s

1 Pick π

$

←− Sn.

2 Use PGE to transform the initial instance as (s′, s′′) = sS and

SH = 



In−k−ℓ

H′

0ℓ×(n−k−ℓ)

H′′











; if it is not possible, restart from line 1.

3 Choose random subsets R0, R1 ⊆ {±1}(k+ℓ)/2, each of size 2v.

4 Build lists L0, L1, using the sub-matrix H′′, i.e.,

L0 = {(z = pH′′⊤

0 , p) | p ∈ R0},

L1 = {(z = pH′′⊤

1

− s′′, p) | p ∈ R1} .

5 for (z1, p1) ∈ L1 do

6

Search for (z0, p0) ∈ L0 such that z0 + z1 = 0. Store (p0, p1) in L.

7 for e′′ ∈ L do

8

compute e′ = s′ − e′′H′′⊤

9

if e′ ∈ {±1}n−k−ℓ then

10

return π−1([e′, e′′])

11 Restart from line 3.

Proposition 17. Let us consider an R-SDP instance given by a random H ∈ F

(n−k)×n

q

with

rank n−k and s

$

←− {eH⊤ | e ∈ {±1}n}. We assume that the R-SDP instance given by (H, s)

has M = 1+2n(1−(1−R) log2(q)) solutions. Then, Algorithm 2 finds one of these solutions with

the following cost

CPGE +

CList + NTestCTest

1 − (1 − 22v−k−ℓ)M

,

27

where

CPGE =

(n − k − ℓ)2(n − k + 1) ⌈log2(q)⌉

2

∏n−k

j=1 (1 − q−j)

, CTest =

q

q − 2

(k + ℓ)⌈log2(q)⌉,

CList = 2v+1 ((v + 1) + k + ℓ

2

ℓ ⌈log2(q)⌉) ,

NTest = (1 − 22v−k−ℓ)M

22v−ℓ log2(q) + (1 − (1 − 22v−k−ℓ)M )m′ + (22v − m′)q−ℓ

(1 + m′)

,

being

m′ = M

22v−k−ℓ

1 − (1 − 22v−k−ℓ)M

.

The proof is reported in Appendix B.

D. Considered scenario

In the next section we describe our adaptation of the CVE identification scheme to the R-

SDP problem, relying on the analysis of the previous sections to devise secure parameters. In

particular, we consider a code with length n and dimension k, defined over a finite field with

q ≥ 5 elements, (with q being a prime), described by a random H ∈ F

(n−k)×n

q

with rank n−k.

In the considered application, the matrix H is public, and the target syndrome is obtained

as s = eH⊤, where e is a randomly sampled vector from {±1}n. The vector e corresponds

to the secret key, while the syndrome s is the public key. Hence, the pair (H, s) represents

an R-SDP instance, and finding a solution to the problem is equivalent to determining either

the secret e or an equivalent vector. The security level of the scheme is given by the cost of

solving such an instance of the R-SDP, which allows designing parameters n, k, and q for a

given target security parameter λ.

In particular, we will use Proposition 13 to estimate the average number of solutions M,

and consider both the brute force and the PGE+SS approaches to estimate the hardness of

recovering the secret e from the public key. Notice that the brute force approach has better

performance when the code has small rate (roughly, significantly lower than 1/2), while for

large code rates the PGE+SS approach becomes more convenient. We will consider parameters

n, k and q such that k/n is quite larger than 1/2 (namely, around 0.8), and thus we will focus

on the PGE+SS approach to estimate the security level, whose complexity can be estimated

through Proposition 17. Obviously, we consider the cost corresponding to the best choice of

both parameters ℓ ∈ {1,...,n−k} and v ∈ {0,..., ℓ+k

2

} (i.e., the ones leading to the lowest

complexity).

28

Notice that the security of our scheme is based on the hardness of finding one out of

multiple solutions (which, in our case, are given by all vectors that multiplied by H⊤ result

in the public key s). A similar setting (which somehow resembles the Decoding One-Out

of Many problem [32]) is employed in other cryptosystems such as WAVE [14]. However,

as an important difference, in our case the expected number of existing solutions M is

extremely small. Indeed, we make use of Proposition 13 to estimate the number of such

equivalent solutions, but choose parameters for which M is only moderately larger than 1.

In other words, we consider the setting in which the R-SDP admits more than one solution

with rather high probability, but limit our interest to the case in which the number of such

solutions is quite small.

We finally remark that, when the finite field size q is some prime power q = pm, an R-SDP

instance may be be mapped into a new instance, defined over some subfield subcode of the

code described by H. Indeed, for an integer m′ | m, we have that Fpm can be seen as a

vector space over Fpm′

of dimension m/m′. Depending on a choice of basis, one can use

an isomorphism projecting each element of Fpm into a vector of length m/m′ and entries

over Fpm′ . By applying this on H and s, we obtain a new R-SDP instance with the inputs

H′ ∈ F

(n−k) m

m′

×n

pm′

and s′ ∈ F

(n−k) m

m′

pm′

. By considering such a subfield subcode, the dimension

of the initial code will reduce significantly and thus the new instance has a smaller complexity

to be solved.

In order to completely avoid such attacks, in the remaining sections we stick to the case

of prime fields Fp. In addition, we avoid finite fields of characteristic 2, for which −1=1

and, with the restriction of a full weight vector e, it follows that e is necessarily the all-one

vector.

VI. IDENTIFICATION SCHEMES BASED ON R-SDP

In this section we show how new instances of code-based ZK-ID schemes can be built

by exploiting the hardness of the R-SDP. In particular, we focus on the CVE scheme, and

revise it using the R-SDP introduced in this paper, as summarized in Fig. 4. For the sake

of clarity, we report the procedure for the case of a single round of communication, but we

remark that it is always possible to take advantage of the compression technique described

in detail in Fig. 1, when multiple rounds are considered.

In the protocol, we use again En,p,t to denote the sphere of vectors in {0, ±1}n with

restricted weight t, and we denote by ˜Mn ⊆ Mn the set of monomial transformations whose

29

Public Data Parameters p, n, k, t ∈ N, parity-check matrix H ∈ F

(n−k)×n

p

Private Key e ∈ En,p,t

Public Key

s = eH⊤ ∈ Fn−k

p

PROVER

VERIFIER

Choose u

$

←− Fn

p , τ

$

←− ˜

Mn

Set c0 = Hash(τ, uH⊤)

Set c1 = Hash(τ(u),τ(e))

(c0,c1)

−−−−→

Choose z

$

←− F∗

p

z

←−

Set y = τ(u + ze)

y

−→

Choose b

$

←− {0, 1}

b

←−

If b = 0, set f := τ

If b = 1, set f := e′ = τ(e)

f

−→

If b = 0, accept if

c0 = Hash(τ,τ−1(y)H⊤ − zs)

If b = 1, accept if ˜

wt(e′) = t

and c1 = Hash(y − ze′, e′)

Fig. 4. Adaptation of the CVE scheme to restricted error vectors.

scaling factors are only ±1.

Note that the only modifications, with respect to the CVE scheme, are in the fact that we

are restricting the secret key and the monomial transformations. By doing this, we base the

30

security of the protocol on the hardness of the R-SDP, which we have proven to be NP-

complete in Section IV-A. A formal security analysis of the proposed scheme is provided

next. When designing practical parameters, we suggest to choose t = n, since this choice

allows to reduce the communication cost.

A. Security

We now show that our protocol satisfies all properties required for a zero-knowledge

identification scheme. Note that our proofs are very similar to those in [20], from which our

scheme is adapted.

Completeness: It is easy to show that an honest prover is always successfully verified.

In fact, if b = 0, we have

τ−1(y)H⊤ − zs = (u + ze)H⊤ − zs = uH⊤,

and therefore

Hash(τ,τ−1(y)H⊤ − zs)

matches the commitment c0. Similarly, if b = 1, we have that

˜

wt(e′) = ˜

wt(τ(e)) = ˜

wt(e) = t

and

y − ze′ = τ(u) + zτ(e) − ze′ = τ(u).

It follows that Hash(y − ze′, e′) matches the commitment c1, and therefore both conditions

are verified.

Zero-Knowledge: To prove this property, we construct a simulator S, modelled as a

probabilistic polynomial-time algorithm, that uses a dishonest verifier A as a subroutine. The

goal of such a simulator is to produce a communication record that is indistinguishable from

one which would be obtained through an honest execution of the protocol. Note that, since

our scheme is a 5-pass protocol, A has two strategies for his attack, corresponding to the

two interactions with the prover. In the first strategy, which we call ST0, A takes as input

the prover’s commitments c0,c1 and produces a value z ∈ F∗

p. In the second strategy, which

we call ST1, A takes as input both the commitments c0,c1 and the first response y, and

generates a challenge b ∈ {0, 1}.

The simulator is constructed as follows. First, pick a random challenge b

$

←− {0, 1}, then:

31

• if b = 0, choose uniformly at random u and τ, then find a vector ê such that êH⊤ = s.

No limitation is placed on the restricted value of ê; so, this can be accomplished by

simple linear algebra. Generate the commitments by setting c0 = Hash(τ, uH⊤) and

picking c1 as a random string of the proper length. Call on A with input c0,c1; A will

apply ST0 and return a value z ∈ F∗

p. Compute y = τ(u+zê) and call on A again with

input c0,c1, y; this time, A will apply ST1 and respond with a bit b.

• if b = 1, choose again u and τ uniformly at random, then pick a random vector ê of the

correct restricted value t. Generate the commitments by picking c0 as a random string

of the proper length, and setting c1 = Hash(τ(u),τ(ê)). As before, call on A with input

c0,c1; A will apply ST0 and return z ∈ F∗

p. Compute again y = τ(u + zê) and call on

A with input c0,c1, y to obtain the bit b.

At this point, the simulator has two options. If

b

= b, the simulator halts and produces the

communication consisting of c0,c1, z, y,b and f; otherwise, it restarts the procedure. Note

that all the objects comprising the record are distributed uniformly at random. Therefore, on

an average of 2N rounds, the record produced by S is indistinguishable from one which

would be produced in an honest execution over N rounds, as we conjectured.

Soundness: We now analyze the cheating probability of an adversary, in this case a

dishonest prover A. We show that such an adversary has a cheating probability that is

asymptotically (in p) close to 1/2. To this end, we show that A can behave in one of

two ways, depending on what is the expected challenge value. In the first case, which we

call ST0, assume without loss of generality that A is preparing to receive the challenge

b = 0. Then A will choose u and τ uniformly at random, and find a vector ê such that

êH⊤ = s, without any limitation on the restricted value. Commitments are generated by

setting c0 = Hash(τ, uH⊤) and picking c1 as a random string of the proper length. Thus, A

is able to successfully answer the challenge b = 0, regardless of the value z chosen by the

verifier. In fact, the value y = τ(u+zê) and the response f = τ computed by A are enough

to pass the verification, since the restricted value of ê is not checked.

In the second case, which we call ST1, A is instead prepared to receive the challenge

b = 1. In this case, A will choose again u and τ uniformly at random, then he will pick a

random vector ê of the correct restricted weight t. Commitments are generated by picking c0

as a random string of the proper length, and setting c1 = Hash(τ(u),τ(ê)). Thus, A is able

to successfully answer the challenge b = 1, regardless of the value z chosen by the verifier.

In fact, the value y = τ(u + zê) and the response f = τ(ê) computed by A are enough to

32

pass the verification, since the same vector ê is used to calculate both objects, and ê has the

correct restricted value.

Note that the adversary’s strategy can be improved in both cases, by taking a guess z on

the value z chosen by the verifier, so that A is able to answer not only the challenge b = 0

regardless of z, but also the challenge b = 1 if z was guessed correctly – or viceversa. With

this improvement, we can calculate the probability of success of the adversary as follows,

where we model the values b and z as random variables:

Pr[A is accepted] =

1

∑

i=0

Pr[ST = STi](Pr[b = i] + Pr[b = 1 − i]Pr[z = z])

=

p

2(p − 1)

.

To conclude this section, we state the following theorem, relating the cheating probability

to the security of the hash function and finding the secret key in the scheme.

Theorem 18. Let V be an honest verifier, running N rounds of the protocol in Fig. 4 with

a dishonest prover A. If A is accepted with probability ( p

2(p−1)

)N + ǫ, where ǫ > 0, then it

is possible to devise an extractor algorithm E that is able to either recover the secret e, or

to find a collision for Hash.

The proof of Theorem 18 proceeds along the lines of that given in [20, Theorem 2], and

therefore we do not repeat it here for the sake of brevity.

B. Communication cost

In our scheme, the public matrix is the parity-check matrix of a linear code over Fp,

with length n and dimension k. To reduce the computational complexity of the protocol, we

can rely on the systematic form of such a matrix, i.e., we can choose H = [In−k P], where

P ∈ F

(n−k)×k

p

. Note that, since the code is chosen uniformly at random, its full representation

is provided by the associated seed.

The public key is the syndrome of the secret key through H, thus it is a vector of length

n − k over Fp; thus, its representation requires (n − k) ⌈log2(p)⌉ bits.

To properly calculate the communication cost of the scheme, we make the following

considerations:

- The vector y is random over Fn

p and is represented through n ⌈log2(p)⌉ bits.

- When b = 0, the monomial transformation can be represented through the associated

seed.

33

- When b = 1, e′ is a random vector over {0, ±1}n with restricted weight, or equivalently

Hamming weight, t. In particular, we will consider the worst case of t = n, in which

e′ can be efficiently represented by a binary string of length n.

Given these considerations, and assuming N rounds are performed with the compression

technique illustrated in Fig. 1, the average communication cost of our scheme is derived as

lHash + N( ⌈log2(p − 1)⌉ + n ⌈log2(p)⌉ +1+ lHash +

n + lSeed

2

).

For the maximal communication cost, we instead have

lHash + N( ⌈log2(p − 1)⌉ + n ⌈log2(p)⌉ +1+ lHash + max{n, lSeed}).

To reach a cheating probability not larger than 2−τ , the number of rounds is obtained as

N = 





−τ

log2 ( p

2(p−1) )









.

Note that, in practice, this means that the number of rounds is approximately equal to τ.

C. Practical instances

In this section we propose some practical instances of our scheme, and compare them with

other code-based identification schemes based on the Hamming metric, at the same security

level. We first briefly describe how secure parameters for the scheme can be designed, by

recalling the analysis in Section V-D. We consider parameters p, n, k for the public code

(i.e., the code defined by the public parity-check matrix H) such that solving the R-SDP

for an error vector of weight n requires at least 2λ operations, where λ is the security level

expressed in bits. As in Proposition 13, we estimate the number of solutions of the R-SDP

as M =1+2

n(1−(1−k/n) log2(p)), and rely on Proposition 17 to estimate the complexity of

attacks based on the PGE+SS approach.

In particular, we focus on those parameters for which the value of M is particularly small

and, de facto, only slightly larger than 1.

In order to provide a first and direct comparison with existing code-based identification

schemes, we consider the same setting as in [20]. Hence, we fix a security level equal

to λ = 87 bits and a target cheating probability equal to 2−16, using hashes and seeds

of length 128 and 160 bits, respectively. For the classical CVE scheme, we consider the

parameters provided in [20]. For the sake of comparison, in the appendix we also design

updated parameters for the AGS scheme, to target the same security level (the cheating

34

probability of a single round has been conservatively approximated to 1/2). For our variant

of the CVE scheme, we have p = 29, n = 167, k = 132, for which

- the expected number of solutions is M = 1.527;

- the PGE+SS attack is optimized by choosing ℓ = 15, v = 73, with a resulting cost of

287.126;

- the required number of rounds is N = 17.

Table I compares the performance of these three schemes, also taking into account the

compression technique. As we see, our scheme (denoted as Rest. CVE in the table) yields

TABLE I

COMPARISON BETWEEN ZK-ID SCHEMES, FOR A SECURITY PARAMETER λ = 87 AND A CHEATING PROBABILITY 2−16,

ASSUMING SEEDS AND HASHES OF, RESPECTIVELY, 128 AND 160 BITS.

CVE

AGS

Rest. CVE

Number of rounds

17

16

17

Public key size (bits)

512

1094

175

Total average comm. cost (kB) 3.472

3.463

2.389

Total max comm. cost (kB)

4.117

4.894

2.430

significant improvements in the communication cost. As another important advantage, the

size of the public key is strongly reduced as well.

Signatures: Signature schemes can be obtained, in the Random Oracle Model, by applying

the well-known Fiat-Shamir transform [33] to any ZK-ID. The transform is very intuitive for

3-pass schemes, in which the protocol is made non-interactive by generating the challenge bits

as the hash output of the commitment and the message. The idea can easily be generalized

to 5-pass schemes such as ours, as illustrated in [34]; in this case, the communication cost

roughly corresponds to the size of a signature. Some minor optimizations are possible, but,

especially for the case of 5-pass schemes, lead only to a very limited improvement. Thus, to

keep the analysis as simple as possible, we do not consider such optimizations. Note that,

for a signature scheme to be of practical interest, the requirements are higher in terms of

security with respect to those considered in the previous comparison. Thus, we provide below

parameters for λ = 128, corresponding to an authentication level of 2−128, and we update

the lengths of both seeds and hash digests, fixing lSeed = lHash = 256.

For our scheme, we recommend to choose p = 31, n = 256, k = 204, for which

35

- the expected number of solutions is M = 1.326;

- the PGE+SS attack is optimized by choosing ℓ = 22, v = 13, with a resulting cost of

2128.029;

- the required number of rounds is N = 135.

In Table II the features of our scheme are compared, again, with those of CVE and AGS.

TABLE II

COMPARISON BETWEEN SIGNATURE SCHEMES DERIVED FROM ZK-ID SCHEMES WITH 128-BIT SECURITY,

CONSIDERING SEEDS AND HASHES OF 256 BITS.

CVE

AGS

Rest. CVE

Number of rounds

129

128

135

Public key size (bits)

832

1574

260

Average sig. size (kB) 43.263

41.040

30.373

Max sig. size (kB)

51.261

56.992

30.373

We observe that, also in this case, our scheme achieves significant reductions in all the

considered sizes over alternative solutions.

To complete the picture, we comment about some schemes that appeared recently in

literature. First, we consider the work of [35], that is an adaptation of Veron’s scheme [27]

to the rank metric. For the instance denoted as cRVDC-125 in the paper, which reaches a

security of 125 bits, the average signature size is estimated as 22.482 kB and the public

key is 1212 bits long. Note that, despite a slightly larger security level, our scheme leads to

larger signature sizes than those of cRVDC-125, but it exhibits much more compact public

keys. Next, we consider Durandal [36], which is again obtained via Fiat-Shamir and also

uses the rank metric, but is based on a different ZK-ID that is an adaptation of the Schnorr-

Lyubashevsky approach [16]. The authors propose two sets of parameters: for the smallest of

the two, the public key size is 121961 bits and the signature size is 32514 bits, corresponding

to approximately 15 kB and 4 kB, respectively. It is immediate to notice that the main benefit

of this approach is the very short signature size, due to the absence of soundness error,

meaning that no repetitions of the protocol are necessary. However, this comes at the cost of

a considerably larger public key (as well as an ad-hoc security reduction and other similar

security concerns). LESS [37] is an innovative scheme based on an alternative approach,

which exploits the code equivalence problem rather than the hardness of decoding. The

36

scheme, after revising its parameters due to a drastic improvement of the known solvers [38],

presents similar sizes for both public keys and signatures, around the 15 kB mark. Thus,

similar to Durandal, the signature compares favorably to ours, but the public key is of a

much bigger scale. Finally, Wave [14] uses a completely different paradigm (hash-and-sign),

which is not based on ZK-ID. It follows that the differences in performance with our scheme

are even starker. In fact, the protocol uses random linear codes in the Hamming metric,

leading to a public key of O(n2) bits and a signature of O(n) bits, where n is the length

of the chosen linear code. The authors set this parameter at n = 8492, which leads to very

unbalanced sizes, roughly 3.2 MB for the public key, and about 1.6 kB for the signature.

D. Implementation aspects

Given that the prover and the verifier perform, besides hash function computation, only

basic linear algebra operations (i.e., sums, multiplications and monomial transformations),

we expect our protocol to be at least as fast as the other ZK-ID schemes we have considered.

In particular, with respect to the standard CVE scheme, it is very likely that our solution

can bring important benefits on the implementation side. In fact, our scheme uses codes with

essentially the same length and dimension, but in a finite field of smaller size: given that sums

and multiplications in Fp essentially cost O(⌈log2(p)⌉ ) and O(⌈log2(p)⌉

2 ), respectively, a

smaller finite field leads to a simplified and faster algebra.

Furthermore, restricted monomial transformations are easier to handle, with respect to

the general case of monomial transformations over Fp. In fact, multiplying by ±1 either

corresponds to doing nothing, or simply performing a sign change. Roughly speaking, scaling

according to a restricted transformation may cost as much as n sums, instead of n multiplica-

tions. Finally, note that computing the inverse of a restricted monomial transformation is also

easier: indeed, the inverse of ±1 is equal to itself (so, no actual inverse needs to be computed).

Given all these considerations, we believe that an optimized, ad-hoc implementation of our

scheme can achieve particularly favourable running times.

To provide some preliminary measure, we have implemented our scheme using Sagemath;

the corresponding code is open source and available online1. We have performed experiments

on an Intel(R) Core(TM) i7-8565U CPY, running at 1.80 GHz, for the instances reaching

128 bits of security.

1The proof-of-concept implementation of our scheme is available at https://re-zkid.github.io/.

37

We have averaged over 1000 runs, obtaining a time of 4.78 ms for a single round ver-

ification. For the sake of completeness, an implementation for the case of multiple rounds

is also publicly available, in which we have used the compression technique to reduce the

communication cost. We remark that these implementations may be strongly optimized and

there is still large room for improvements.

VII. CONCLUSION

In this paper we have studied generalizations of some decoding problems, and their

application to zero-knowledge code-based identification schemes. In particular, we have

introduced the R-SDP, a new decoding problem in which the searched error, corresponding to

the given syndrome, must have entries belonging to a restricted subset of the finite field. We

have shown that the decisional version of this new problem is NP-complete, via a reduction

from the Hamming version of the SDP, and have adapted classical arguments about random

codes (such as the Gilbert-Varshamov bound) to take into account error vectors with this

particular structure. We have assessed the complexity of solving the R-SDP adapting modern

techniques. We have provided an adaption of the CVE scheme to the case of restricted error

vectors and compared this proposal to the original CVE scheme and to the AGS scheme.

Finally, we have observed that using restricted error vectors we can achieve a reduction in

the communication cost of more than 25% over classical approaches, which coincides with

the achievable reduction in the signature size when these schemes are used as the basis for

digital signature schemes obtained through the Fiat-Shamir transform.

38

APPENDIX A

THE AGS SCHEME

The AGS scheme [25] is constructed upon quasi-cyclic codes over F2. Let us consider a

vector a ∈ F

jk

2 divided into j blocks of k entries each, that is,

a = [a

(0)

0 ,...,a

(0)

k−1| ...|a

(j−1)

0

,...,a

(j−1)

k−1 ].

We use ρ

(k)

i

to denote a function that performs a block-wise cyclic shift of a by i positions

towards right, i.e.,

ρ

(k)

i (a) = [a

(0)

−i mod k,...,a

(0)

k−1−i mod k| ...|a

(j−1)

−i mod k,...,a

(j−1)

k−1−i mod k] .

The AGS scheme is described in Fig. 5. In such a scheme, the cheating probability

asymptotically tends to 1

2

[25]. However, in [25] a direct expression for the actual cheating

probability is not provided, thus we conservatively assume that its value is 1

2

, which is optimal.

When performing N rounds, the average communication cost is

lHash + N( ⌈log2(k)⌉ +1+2lHash +

lSeed + k + n + ψ(n, ω, 2)

2

),

while the maximum communication cost is

lHash + N( ⌈log2(k)⌉ +1+2lHash + min{lSeed + k, n + ψ(n, ω, 2)}).

In [25], three parameters sets are proposed:

- n = 698, k = 349, ω = 70, for 81-bits security;

- n = 1094, k = 547, ω = 109, for 128-bits security.

Taking into account advances in binary ISD techniques [8], as well as the polynomial gain

due to the quasi-cyclic structure of the codes [32], the security level of this scheme can

be approximately estimated as ω − 1

2

log2(k) bits. Such a security level is below the one

originally estimated in [25]. Thus, we have updated the scheme parameters as follows, in

order to reach security levels that can directly be compared with those achieved by the CVE

scheme in [20]:

- n = 1094, k = 547, ω = 92, for 87-bits security;

- n = 1574, k = 787, ω = 133, for 128-bits security.

39

Public Data Parameters k, n, ω ∈ N, hash function Hash, generator matrix G ∈ Fk×n

2

Private Key m ∈ Fk

2, e ∈ SH

n,2,ω

Public Key x = mG + e ∈ Fn

2

PROVER

VERIFIER

Choose u

$

←− Fk

2, σ

$

←− Sn

Set c0 = Hash(σ)

Set c1 = Hash(σ(uG))

c0,c1

−−−→

Choose z

$

←− [0; k − 1]

z

←−

Set e′ = ρ

(k)

z (e).

Set c2 = Hash(σ(uG + e′))

c2

−→

Choose b

$

←− {0, 1}

b

←−

If b = 0, set f := {σ, u + ρ

(k)

z (m)}

If b = 1, set f := {σ(uG),σ(e′)}

f

−→

If b = 0, accept if c0 = Hash(σ) and

c2 = (u + ρ

(k)

z (m))G + ρ

(k)

z (x)

If b = 1, accept if wtH(e′) = ω

and c1 = Hash(σ(uG)) and

c2 = Hash(σ(uG) + σ(e′))

Fig. 5. The AGS scheme.

40

APPENDIX B

PROOF OF PROPOSITION 17

In this Appendix we derive the cost of Algorithm 2, used to solve a random R-SDP instance

represented by H ∈ F

(n−k)×n

q

with rank n − k and s

$

←− {eH⊤ | e ∈ {±1}n}.

1) First, the probability that the PGE step in line 2 is successful is given by ∏

n−k

j=1 (1 − q−j),

which is the probability for a matrix of size (n − k) × (n − k) to have full rank n − k.

We estimate the cost of performing the PGE step as (n − k − ℓ)2(n − k + 1) ⌈log2(q)⌉

2

,

hence, to execute the instructions in lines 1 and 2 in the algorithm, we have an average

cost of

CPGE =

(n − k − ℓ)2(n − k + 1) ⌈log2(q)⌉

2

∏n−k

j=1 (1 − q−j)

.

2) Remember that H′′ has dimensions ℓ×(k+ℓ), and that we split it into two sub matrices

H′′

0 and H′′

1, each with dimensions ℓ × k+ℓ

2

. To build L0 and L1, we generate L = 2v

random vectors p of length k+ℓ

2

and compute (and store) the corresponding z = pH′′⊤

0 ,

respectively z = pH′′⊤

1

− s′′. We assume that the cost to create each list element is

identical to that of computing z, which requires the addition of (k + ℓ)/2 vectors with

length ℓ and entries over Fq, and hence is given by k+ℓ

2

ℓ ⌈log2(q)⌉ binary operations.

Since |Li| = 2v, the overall cost of producing Li can be estimated as 2v k+ℓ

2

ℓ ⌈log2(q)⌉ .

In line 5 to 6 we search for all (z0, p0) ∈ L0 and (z1, p1) ∈ L1, such that z0+z1 = 0. We

can do this by joining and sorting the two lists, with a cost of 2Llog2(2L)=(v+1)2v+1

operations. The cost of finding pairs of vectors from both lists that sum to zero, i.e.,

elements in L, is negligible, since it can be done during sorting. Hence, both lists are

generated, sorted and merged with a cost of

CList = (v + 1)2v+1 + 2v+1 k + ℓ

2

ℓ ⌈log2(q)⌉ = 2v+1 (v +1+ k + ℓ

2

ℓ ⌈log2(q)⌉) .

Note that the list L1 can also be generated on the run, which leads to a polynomial

decrease in the complexity analysis by a factor between 1 and 2.

3) We rely on Proposition 15 to estimate the probability that the final list L contains at

least a vector leading to a solution for the initial R-SDP instance. In this case we have

δ = 0 (since we do not filter any of the candidates in R0, R1), hence we have a success

probability of

1 − (1 − 22v−k−ℓ)M

.

In particular, the reciprocal of the above corresponds to the average number of times

we repeat the instructions in lines 3–10.

41

4) We now call an element of L a valid solution if it leads to a solution of the initial

R-SDP. We observe the following: If (z0, p0) ∈ L0 and (z1, p1) ∈ L1 lead to a valid

solution, then (p0, p1) will be in the merged list L. Therefore, the probability that L

contains m valid solutions is equal to the probability that L0 × L1 contains m valid

solutions, which can be estimated as

(Mm)

(22v−k−ℓ)m (1 − 22v−k−ℓ)M−m

.

When there are m valid solutions, the number of elements of L that do not lead to a

solution for the initial R-SDP instance, can be derived as

22v − m

qℓ

,

hence the average size of L is given by m + 22v −m

qℓ

.

5) At this point, one of the following two conditions may occur:

a) if L does not contain any valid solution, one will test all the candidates in L before

restarting from line 3. This happens with probability Pr[m = 0] = (1 − 22v−k−ℓ)M

,

and the size of L can be estimated as 22v−ℓ log2(q).

b) if L contains m ≥ 1 valid vectors, when scanning the elements in L, we will at

some point find a solution to the initial R-SDP instance (i.e., a vector e′ satisfying

the requirement in Line 9 of the Algorithm). We can derive the expected number m′

of valid solutions, conditioned to the fact that m ≥ 1, as

m′ =

M22v−k−ℓ

Pr[m ≥ 1]

= M

22v−k−ℓ

1 − (1 − 22v−k−ℓ)M

.

Notice that, in this case, L contains on average m′ + (22v − m′)q−ℓ elements. Hence,

the number of tests before we find a valid solution can be estimated as

m′ + (22v − m′)q−ℓ

(1 + m′)

.

To resume, the average number of performed tests before one solution is found can be

obtained as

NTest = Pr[m = 0]22v−ℓ log2(q) + Pr[m ≥ 1]

m′ + (22v − m′)q−ℓ

(1 + m′)

.

For each test, we consider a cost given by CTest = q

q−2

(k + ℓ)⌈log2(q)⌉, due to early

abort. Since the success probability is given by Pr[m ≥ 1], we finally derive the cost

of instructions from line 3 to line 11 as

CList + NTestCTest

Pr[m ≥ 1]

.

42

REFERENCES

[1] E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems,” IEEE

Trans. Inf. Theory, vol. 24, no. 3, pp. 384–386, 1978.

[2] S. Barg, “Some new NP-complete coding problems,” Problemy Peredachi Informatsii, vol. 30, no. 3, pp. 23–28, 1994.

[3] E. Prange, “The use of information sets in decoding cyclic codes,” IRE Trans. Inf. Theory, vol. 8, no. 5, pp. 5–9,

1962.

[4] I. I. Dumer, “Two decoding algorithms for linear codes,” Problemy Peredachi Informatsii, vol. 25, no. 1, pp. 24–32,

1989.

[5] 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. Springer, 1988, pp. 275–280.

[6] J. S. Leon, “A probabilistic algorithm for computing minimum weights of large error-correcting codes,” IEEE Trans.

Inf. Theory, vol. 34, no. 5, pp. 1354–1359, 1988.

[7] J. Stern, “A method for finding codewords of small weight,” in International Colloquium on Coding Theory and

Applications. Springer, 1988, pp. 106–113.

[8] A. Becker, A. Joux, A. May, and A. Meurer, “Decoding random binary linear codes in 2n/20: How 1+1=0

improves information set decoding,” in Advances in Cryptology - EUROCRYPT 2012, ser. LNCS, D. Pointcheval

and T. Johansson, Eds., vol. 7237. Springer, 2012, pp. 520–536.

[9] A. May, A. Meurer, and E. Thomae, “Decoding random linear codes in O(20.054n),” in International Conference on

the Theory and Application of Cryptology and Information Security. Springer, 2011, pp. 107–124.

[10] D. J. Bernstein, T. Lange, and C. Peters, “Smaller decoding exponents: ball-collision decoding,” in Annual Cryptology

Conference. Springer, 2011, pp. 743–760.

[11] R. J. McEliece, “A public-key cryptosystem based on algebraic coding theory.” DSN Progress Report, pp. 114–116,

1978.

[12] N. Courtois, M. Finiasz, and N. Sendrier, “How to achieve a McEliece-based digital signature scheme,” in ASIACRYPT.

Springer, 2001, pp. 157–174.

[13] R. Bricout, A. Chailloux, T. Debris-Alazard, and M. Lequesne, “Ternary syndrome decoding with large weight,” in

International Conference on Selected Areas in Cryptography. Springer, 2019, pp. 437–466.

[14] T. Debris-Alazard, N. Sendrier, and J.-P. Tillich, “Wave: A new family of trapdoor one-way preimage sampleable

functions based on codes,” in ASIACRYPT. Springer, 2019, pp. 21–51.

[15] J. Stern, “A new identification scheme based on syndrome decoding,” in Advances in Cryptology — CRYPTO’ 93,

D. R. Stinson, Ed. Springer Berlin Heidelberg, 1994, pp. 13–21.

[16] V. Lyubashevsky, “Lattice signatures without trapdoors,” in Annual International Conference on the Theory and

Applications of Cryptographic Techniques. Springer, 2012, pp. 738–755.

[17] E. Persichetti, “Efficient one-time signatures from quasi-cyclic codes: A full treatment,” Cryptography, vol. 2, no.

4:30, 2018.

[18] P. Santini, M. Baldi, and F. Chiaraluce, “Cryptanalysis of a one-time code-based digital signature scheme,” in 2019

IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp. 2594–2598.

[19] J.-C. Deneuville and P. Gaborit, “Cryptanalysis of a code-based one-time signature,” Des. Codes Cryptogr., 2020.

[20] P.-L. Cayrel, P. Véron, and S. M. El Yousfi Alaoui, “A zero-knowledge identification scheme based on the q-ary

syndrome decoding problem,” in Selected Areas in Cryptography. Springer Berlin Heidelberg, 2011, pp. 171–186.

[21] S. M. El Yousfi Alaoui, P.-L. Cayrel, R. El Bansarkhani, and G. Hoffmann, “Code-based identification and signature

schemes in software,” in Security Engineering and Intelligence Informatics, A. Cuzzocrea, C. Kittl, D. E. Simos,

E. Weippl, and L. Xu, Eds. Springer Berlin Heidelberg, 2013, pp. 122–136.

43

[22] R. Bricout, A. Chailloux, T. Debris-Alazard, and M. Lequesne, “Ternary syndrome decoding with large weight,”

Cryptology ePrint Archive, Report 2019/304, 2019. [Online]. Available: https://eprint.iacr.org/2019/304

[23] E. Berlekamp, Algebraic Coding Theory. World Scientific, 1968.

[24] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Elsevier, 1977.

[25] C. Aguilar, P. Gaborit, and J. Schrek, “A new zero-knowledge code based identification scheme with reduced

communication,” in 2011 IEEE Information Theory Workshop (ITW), Paraty, Brazil, Oct 2011, pp. 648–652.

[26] S. D. Galbraith, C. Petit, and J. Silva, “Identification protocols and signature schemes based on supersingular isogeny

problems,” in ASIACRYPT. Springer, 2017, pp. 3–33.

[27] P. Véron, “Improved identification schemes based on error-correcting codes,” Applicable Algebra in Engineering,

Communication and Computing, vol. 8, no. 1, pp. 57–69, 1997.

[28] C. Peters, “Information-set decoding for linear codes over Fq,” in Post-Quantum Cryptography, N. Sendrier, Ed.

Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 81–94.

[29] C. Lee, “Some properties of nonbinary error-correcting codes,” IRE Transactions on Information Theory, vol. 4, no. 2,

pp. 77–82, 1958.

[30] V. Weger, P. Santini, M. Battaglioni, and A.-L. Horlemann-Trautmann, “NP-complete problems for Lee metric codes,”

arXiv preprint arXiv:2002.12785, 2020.

[31] D. Wagner, “A generalized birthday problem,” in Annual International Cryptology Conference. Springer, 2002, pp.

288–304.

[32] N. Sendrier, “Decoding one out of many,” in Post-Quantum Cryptography, B.-Y. Yang, Ed. Springer Berlin Heidelberg,

2011, pp. 51–67.

[33] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” in

CRYPTO. Springer, 1986, pp. 186–194.

[34] ¨O. Dagdelen, D. Galindo, P. Véron, S. M. E. Y. Alaoui, and P. Cayrel, “Extended security arguments for signature

schemes,” Des. Codes Cryptogr., vol. 78, no. 2, pp. 441–461, 2016.

[35] E. Bellini, F. Caullery, P. Gaborit, M. Manzano, and V. Mateu, “Improved Veron identification and signature schemes

in the rank metric,” in 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp.

1872–1876.

[36] 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, Y. Ishai and V. Rijmen, Eds. Cham: Springer International Publishing,

2019, pp. 728–758.

[37] J.-F. Biasse, G. Micheli, E. Persichetti, and P. Santini, “LESS is more: Code-based signatures without syndromes,”

in Progress in Cryptology - AFRICACRYPT 2020, A. Nitaj and A. Youssef, Eds. Cham: Springer International

Publishing, 2020, pp. 45–65.

[38] W. Beullens, “Not enough LESS: An improved algorithm for solving code quivalence problems over Fq,” 2020.

[Online]. Available: https://eprint.iacr.org/2020/801