11institutetext:  Technology Innovation Institute 22institutetext: University
of Limoges 33institutetext: INRIA

# Quasi-Cyclic Stern Proof of Knowledge

Loïc Bidoux 11 Philippe Gaborit 22 Nicolas Sendrier 33

###### Abstract

The 1993 Stern authentication protocol is a code-based zero-knowledge protocol
with cheating probability equal to 2/3 based on the syndrome decoding problem
which permits to obtain a proof of knowledge of a small weight vector. This
protocol was improved a few years later by Véron, who proposed a variation of
the scheme based on the general syndrome decoding problem which leads to
better results in term of communication. A few years later, the AGS protocol
introduced a variation of the Véron protocol based on quasi-cyclic matrices.
The AGS protocol permits to obtain an asymptotic cheating probability of 1/2
and a strong improvement in term of communications. In the present paper we
propose two new contributions. First, a Quasi-Cyclic Stern proof of knowledge
construction which constitutes an adaptation of the AGS scheme in a syndrome
decoding context. The main interest of this adaptation is that at the
difference of the regular (non quasi-cyclic) case, the Quasi-Cyclic Stern
protocol is better in terms of communication than its Véron counterpart (the
AGS protocol, which can be seen as a Quasi-Cyclic Véron protocol). The
difference comes from the fact that a seed related optimization is better for
QC-Stern than for QC-Véron. Secondly, we also propose a general new
optimization to handle random seeds in this type of protocol. Overall, the two
new optimizations we propose permit to gain about $17.5\%$ in the length of
communication compared to the previous best approach for this type of
protocols. Such optimizations are of great matter in the ongoing context where
a new signature call for proposals has been announced by the NIST and for
which such zero-knowledge approaches are a real alternative, as it was shown
in the first signature call for proposals of the NIST. At last, the paper also
sums up the different known optimizations for such protocols and explain how
our new approach can be adapted to other metrics.

###### Keywords:

Code-based Cryptography, Stern Protocol, Proof of Knowledge, Fiat-Shamir
Heuristic

##  1 Introduction

Post-quantum cryptography aims at providing cryptographic schemes that are
secure against adversaries that may use classical or quantum computers. Code-
based cryptography, which has been introduced in 1978 by McEliece [29], is one
of the main alternative to classical cryptography. This is illustrated by the
ongoing NIST Post-Quantum Cryptography standardization process whose round 3
features three code-based Key Encapsulation Mechanisms (KEM) [6, 3, 4].
Aditional KEM [8, 2, 5] were also considered during the round 2 of the
competition. Although there exists satisfactory code-based KEM, designing
signatures from coding theory has historically been challenging. Two
approaches have been used in the literature namely signatures from the hash-
and-sign paradigm and signatures based on identification. In the first
category, a construction was proposed in 2001 [20] although it is rather
inefficient. The recent Wave construction [22] follows the same paradigm and
features small signature sizes. For signatures based on identification, the
Schnorr-Lyubashevsky [31, 28] approach have been successfully used in Durandal
[7]. Hereafter, we focus on the Fiat-Shamir paradigm [23, 30] which relies on
zero-knowledge proofs of knowledge. In this approach, one transforms an
interactive proof of knowledge into a digital signature using the so called
Fiat-Shamir heuristic.

The first proof of knowledge constructed from codes was introduced by Stern in
1993 [34] and is based on the syndrome decoding ($\mathsf{SD}$) problem. In
1997, Véron showed that using the general decoding problem ($\mathsf{GSD}$),
one can design a protocol that is more efficient than the initial Stern
proposal [35]. The $\mathsf{SD}$ and $\mathsf{GSD}$ problems are equivalent
and differ only in the way used to represent the underlying code namely using
a parity-check matrix in the former and using a generator matrix in the
latter. Both protocols require 3 rounds to be executed and feature a soundness
error equal to 2/3. In 2011, the CVE [16] and AGS [1] proofs of knowledge
respectively improved the Stern and Véron protocols by lowering their
soundness error to 1/2 using 5 rounds of execution. The CVE protocol is based
on the q-ary $\mathsf{SD}$ problem while the AGS protocol relies on quasi-
cyclicity and the $\mathsf{QCGSD}$ problem. An issue with respect to the zero-
knowledge property of $\mathsf{GSD}$ based protocols (Véron and AGS) has been
identified in [26] and have been fixed in [13]. Some of these protocols have
also been adapted in the rank metric setting, see [18, 24, 11] for instance.

Amongst these constructions, AGS leads to the smallest signature size once the
Fiat-Shamir heuristic is applied. This is due to the fact that it features a
soundness of $1/2$ and relies on the $\mathsf{GSD}$ problem which allows to
substitute vectors of size $n$ to vectors of size $n/2$ in some parts of the
protocol. In this paper, we show that although this property is quite
desirable, one can actually design a more efficient protocol from the
$\mathsf{SD}$ problem. Indeed, we introduce an optimization for $\mathsf{SD}$
based protocols that allows to substitute a vector of size $n$ by a seed thus
outperforming the natural advantage of $\mathsf{GSD}$ based constructions.

Contributions. We introduce the Quasi-Cyclic Stern protocol which is a new
proof of knowledge for syndrome decoding as well as two new optimizations for
code-based proofs of knowledge. The first optimization is suitable for all
existing protocols while the second one can’t be applied to $\mathsf{GSD}$
based protocol such as AGS. In practice, our new protocol leads to a signature
scheme whose signature size is $17.5\%$ smaller than existing constructions.

Paper organization. We introduce some preliminaries on code-based proofs of
knowledge in Section 2. Then, we describe the Quasi-Cyclic Stern protocol as
well as new optimizations for code-based proof of knowledge in Section 3. We
give some parameters and depict resulting key sizes and signature sizes in
Section 4. We explain how to generalize our construction to other metrics in
Section 5. Finally, some concluding remarks are given in Section 6.

##  2 Preliminaries

We start by presenting some definitions related to code-based cryptography in
Section 2.1. Then, we introduce zero-knowledge proofs of knowledge and explain
how one can transform them into signatures in Section 2.2. Finally, we
describe the Stern protocol in Section 2.3.

Notations. Hereafter, we represent vectors (respectively matrices) using bold
lower-case (respectively upper-case) letters. We denote by
$w_{H}\big{(}\mathbf{x}\big{)}=w$ the Hamming weight of a vector $\mathbf{x}$
e.g. the number of its non-zero coordinates. For an integer $n>0$, we use
$S_{n}$ to denote the symmetric group of all permutations of $n$ elements. For
a finite set $S$, $x\overset{\;\$}{\longleftarrow}S$ denotes that $x$ is
sampled uniformly at random from $S$ while
$x\overset{\;\$,\theta}{\longleftarrow}$ denotes that $x$ is sampled uniformly
at random from $S$ using the seed $\theta$.

###  2.1 Code-based Cryptography

We start by defining linear codes and quasi-cyclic codes. Next, we describe
the syndrome decoding ($\mathsf{SD}$) and quasi-cyclic syndrome decoding
($\mathsf{QCSD}$) problems which are two difficult problems commomly used in
code-based cryptography. The $\mathsf{SD}$ problem has been proven NP-complete
in [12]. In addition, we also introduce the differential syndrome decoding
($\mathsf{DiffSD}$) problem that is related to the $\mathsf{QCSD}$ problem as
detailed in Section 3.

######  Definition 1 (Binary Linear Code)

Let $n$ and $k$ be positive integers such that $k<n$. A binary linear
$\mathcal{C}$ code (denoted $[n,k]$) is a $k$-dimensional subspace of
$\mathbb{F}_{2}^{n}$. $\mathcal{C}$ can be represented in two equivalent ways:
by a generator matrix $\mathbf{G}\in\mathbb{F}_{2}^{k\times n}$ such that
$\mathcal{C}=\\{\mathbf{mG}~{}|~{}\mathbf{m}\in\mathbb{F}_{2}^{k}\\}$ or by a
parity-check matrix $\mathbf{H}\in\mathbb{F}_{2}^{(n-k)\times n}$ such that
$\mathcal{C}=\\{\mathbf{x}\in\mathbb{F}_{2}^{n}~{}|~{}\mathbf{H}\mathbf{x}^{\top}=0\\}$.

######  Definition 2 (Systematic Quasi-Cyclic Code)

A systematic quasi-cyclic code of index $\ell$ and rate $1/\ell$ is a $[n=\ell
k,k]$ code with an $(\ell-1)k\times\ell k=(n-k)\times n$ parity check matrix
of the form:

$\mathbf{H}=\begin{bmatrix}\mathbf{I}_{k}&0&\cdots&0&\mathbf{A}_{0}\\\
0&\mathbf{I}_{k}&&&\mathbf{A}_{1}\\\ &&\ddots&&\vdots\\\
0&&\cdots&\mathbf{I}_{k}&\mathbf{A}_{\ell-2}\end{bmatrix}$

where $\mathbf{A}_{0},\ldots,\mathbf{A}_{\ell-2}$ are circulant $k\times k$
matrices.

######  Definition 3 ($\mathsf{SD}$ problem)

Given positive integers $n$, $k$, $w$, a random parity-check matrix
$\mathbf{H}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{(n-k)\times n}$, and
a syndrome $\mathbf{y}\in\mathbb{F}_{2}^{n-k}$ the syndrome decoding problem
$\mathsf{SD}(n,k,w)$ asks to find $\mathbf{x}\in\mathbb{F}_{2}^{n}$, such that
$\mathbf{Hx}^{\top}=\mathbf{y}^{\top}$ and $w_{H}\big{(}\mathbf{x}\big{)}=w$.

######  Definition 4 ($\mathsf{QCSD}$ problem)

Given positive integers $n,k,w$, with $n=\ell k$ for some $\ell$, a random
parity-check matrix of a quasi-cyclic code
$\mathbf{H}\overset{\;\$}{\longleftarrow}\mathcal{QC}(\mathbb{F}_{2}^{(n-k)\times
n})$, and a syndrome $\mathbf{y}\in\mathbb{F}_{2}^{(n-k)}$, the syndrome
decoding problem $\mathsf{QCSD}(n,k,w)$ asks to find
$\mathbf{x}\in\mathbb{F}_{2}^{n}$, such that
$\mathbf{Hx}^{\top}=\mathbf{y}^{\top}$ and $w_{H}\big{(}\mathbf{x}\big{)}=w$.

The quasi-cyclic codes we will consider hereafter will always have index
$\ell=2$.

###  2.2 Signatures from Zero-Knowledge Proof of Knowledge

We start by introducing commitment schemes as they are a building block used
to construct proofs of knowledge. We require such schemes to be
computationally hiding and computationally biding. The former property ensures
that adversaries can’t distinguish between two commitments generated from
different messages. The latter property ensures that adversaries can’t change
their committed messages after the commit step.

######  Definition 5 (Commitment Scheme)

A commitment scheme is a tuple of algorithms
$\mathsf{COM}=(\mathsf{Commit},\mathsf{Open})$ such that $\mathsf{Commit}(m)$
returns a commitment $c$ for the message $m$ and $\mathsf{Open}(c,m)$ returns
either $1$ ($\mathsf{accept}$) or $0$ ($\mathsf{reject}$). A commitment scheme
is said to be correct if:

$\mathsf{Pr}\left[b=1\
\middle|\begin{array}[]{l}c\leftarrow\mathsf{Commit}(m),~{}b\leftarrow\mathsf{Open}(c,m)\end{array}\right]=1.$

######  Definition 6 (Computationally Hiding)

Let $(m_{0},m_{1})$ be a pair of messages, the advantage of an adversary
$\mathcal{A}$ against the commitment hiding experiment be defined as:

$\mathsf{Adv}^{\mathsf{hiding}}_{\mathcal{A}}(1^{\lambda})=\Bigg{|}\,\mathsf{Pr}\left[\begin{array}[]{l}b=b^{\prime}\\\
\end{array}\ \middle|~{}\\\
\begin{array}[]{l}b\overset{\;\$}{\longleftarrow}\\{0,1\\},~{}c\longleftarrow\mathsf{Commit}(m_{b})\\\
b^{\prime}\longleftarrow\mathcal{A}.\mathsf{guess}(c)\end{array}\right]-\frac{1}{2}\,\Bigg{|}.$

A commitment scheme $\mathsf{COM}$ is computationally hiding if for all
probabilistic polynomial time adversaries $\mathcal{A}$ and every pair of
messages $(m_{0},m_{1})$,
$\mathsf{Adv}^{\mathsf{hiding}}_{\mathcal{A}}(1^{\lambda})$ is negligible in
$\lambda$.

######  Definition 7 (Computationally Binding)

Let the advantage of an adversary $\mathcal{A}$ against the commitment binding
experiment be defined as:

$\mathsf{Adv}^{\mathsf{binding}}_{\mathcal{A}}(1^{\lambda})=\mathsf{Pr}\left[\begin{array}[]{l}m_{0}\neq
m_{1}\\\ 1\longleftarrow\mathsf{Open}(c,m_{0})\\\
1\longleftarrow\mathsf{Open}(c,m_{1})\\\ \end{array}\ \middle|~{}\\\
\begin{array}[]{l}(c,m_{0},m_{1})\longleftarrow\mathcal{A}.\mathsf{choose}(1^{\lambda})\end{array}\right].$

A commitment scheme $\mathsf{COM}$ is computationally binding if for all
probabilistic polynomial time adversaries $\mathcal{A}$,
$\mathsf{Adv}^{\mathsf{binding}}_{\mathcal{A}}(1^{\lambda})$ is negligible in
$\lambda$.

We now describe proofs of knowledge along with their soundness and zero-
knowledge properties. Informally, a zero-knowledge proof of knowledge allows a
prover $\mathsf{P}$ to prove the knowledge of a secret to a verifier
$\mathsf{V}$ without revealing anything about it.

######  Definition 8 (Proof of Knowledge)

A $(2n+1)$-rounds proof of knowledge
$\mathsf{PoK}=(\mathsf{Setup},\allowbreak\mathsf{Keygen},\allowbreak\mathsf{P}_{1},\allowbreak\cdots,\allowbreak\mathsf{P}_{n+1},\allowbreak\mathsf{V}_{1},\allowbreak\cdots,\allowbreak\mathsf{V}_{n+1})$
is an interactive protocol between a prover $\mathsf{P}$ and a verifier
$\mathsf{V}$. We denote by
$\big{\langle}\mathsf{P}(\mathsf{param},\allowbreak\mathsf{\vphantom{p}sk},\allowbreak\mathsf{\vphantom{p}pk}),\allowbreak\mathsf{V}(\mathsf{param},\allowbreak\mathsf{\vphantom{p}pk})\big{\rangle}$
the transcript of a proof of knowledge between a prover $\mathsf{P}$ and a
verifier $\mathsf{V}$.

A proof of knowledge is correct if for all $\mathsf{param}$ returned by
$\mathsf{Setup}(1^{\lambda})$ and all
$(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})$ retuned by
$\mathsf{Keygen}(\mathsf{param})$:

$\mathsf{Pr}\left[\begin{array}[]{l}\textsf{accept}\leftarrow\big{\langle}\mathsf{P}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk}),\\\
\mathsf{V}(\mathsf{param},\mathsf{\vphantom{p}pk})\big{\rangle}\end{array}\
\middle|\\\
\begin{array}[]{l}\mathsf{param}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})\leftarrow\mathsf{Keygen}(\mathsf{param})\end{array}\right]=1.$

######  Definition 9 (Soundness)

A proof of knowledge is sound with soundness error $\epsilon$ if for all
$\mathsf{param}$ returned by $\mathsf{Setup}(1^{\lambda})$, all
$(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})$ returned by
$\mathsf{Keygen}(\mathsf{param})$ and all probabilistic polynomial time
$\mathsf{PPT}$ malicious prover $\tilde{\mathsf{P}}$:

$\mathsf{Pr}\left[\begin{array}[]{l}\textsf{accept}\leftarrow\big{\langle}\tilde{\mathsf{P}}(\mathsf{param},\mathsf{\vphantom{p}pk}),\\\
\mathsf{V}(\mathsf{param},\mathsf{\vphantom{p}pk})\big{\rangle}\end{array}\
\middle|\begin{array}[]{l}\mathsf{param}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})\leftarrow\mathsf{Keygen}(\mathsf{param})\end{array}\right]\leq\epsilon+\mathsf{negl}(\lambda).$

######  Definition 10 (Honest-Verifier Zero-Knowledge)

A proof of knowledge satisfies the honest-verifier zero-knowledge (HZVK)
property if there exists a $\mathsf{PPT}$ simulator $\mathsf{Sim}$ that given
as input $(\mathsf{param},\mathsf{\vphantom{p}pk})$, outputs a transcript
$\big{\langle}\mathsf{Sim}(\allowbreak\mathsf{param},\allowbreak\mathsf{\vphantom{p}pk}),\allowbreak\mathsf{V}(\mathsf{param},\allowbreak\mathsf{\vphantom{p}pk})\big{\rangle}$
that is computationally indistinguishable from the probability distribution of
transcripts of honest executions between a prover $\mathsf{P}$ with input
$(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})$ and
verifier $\mathsf{V}$ with input $(\mathsf{param},\mathsf{\vphantom{p}pk})$.

Zero-knowledge proofs of knowledge are of great interest as they can be
converted into digital signatures by using the Fiat-Shamir heuristic [23, 30,
21]. Indeed, if the verifier challenges are sampled uniformly at random within
their associated challenge spaces, then one can emulate the verifier behavior
using a hash function modeled as a random oracle. Doing this, one transform an
interactive proof of knowledge into a (non-interactive) signature.

###  2.3 Stern Protocol

In this section, we present the initial Stern protocol [34] and discuss
informally its correctness, soundness and zero-knowledge properties. Given a
public key $\mathsf{\vphantom{p}pk}=(\mathbf{H},\mathbf{y}^{\top})$, the Stern
protocol permits to prove the knowledge of
$\mathsf{\vphantom{p}sk}=(\mathbf{x})$ such that
$\mathbf{y}^{\top}=\mathbf{H}\mathbf{x}^{\top}$ and
$w_{H}\big{(}\mathbf{x}\big{)}=w$. As such, the Stern protocol constitutes a
proof of knowledge of a solution to an $\mathsf{SD}$ problem instance. The
idea of the protocol is to prove the knowledge of $\mathbf{x}$ using
$\mathbf{x}+\mathbf{u}$ for some random value $\mathbf{u}$ and to prove that
$w_{H}\big{(}\mathbf{x}\big{)}=w$ using $\pi[\mathbf{x}]$ for some random
permutation $\pi$.

The protocol (see Figure 1) is a 3-rounds construction in which the prover
$\mathsf{P}$ starts by generating three commitments $c_{1},c_{2},c_{3}$
related to $\pi,\mathbf{x}$ and $\mathbf{u}$. Then, the verifier $\mathsf{V}$
computes a challenge $\textsc{Ch}\overset{\;\$}{\longleftarrow}\\{0,1,2\\}$
and the prover $\mathsf{P}$ outputs a response Rsp. During the verification
step, the verifier $\mathsf{V}$ recomputes two out of three commitments
(depending on the value of the challenge Ch) using Rsp and either accept or
reject the proof. The correctness of the proof follows straighforwardly from
its description.

Regarding the soundness of the proof, one can see that a malicious prover
$\tilde{P}$ can always cheat in two out of three cases. Indeed, by chosing
$\mathbf{z}$ such that $\mathbf{H}\mathbf{z}=\mathbf{H}\mathbf{u}+\mathbf{y}$
(no constraint on the weight of $\mathbf{z}$) and computing
$c_{3}=\textsf{Commit}(\pi[\mathbf{z}])$ and $\textsc{Rsp}=(\pi,\mathbf{z})$
in the case $\textsc{Ch}=1$, the malicious prover $\tilde{\mathsf{P}}$ will be
accepted for both $\textsc{Ch}=0$ and $\textsc{Ch}=1$. Similarly, by chosing
$\tilde{\mathbf{x}}$ such that $w_{H}\big{(}\tilde{\mathbf{x}}\big{)}=w$ and
computing $c_{3}=\textsf{Commit}(\pi[\tilde{\mathbf{x}}+\mathbf{u}])$ and
$\textsc{Rsp}=(\pi[\tilde{\mathbf{x}}],\pi[\mathbf{u}])$ in the case
$\textsc{Ch}=2$, the malicious prover $\tilde{\mathsf{P}}$ will be accepted
for both $\textsc{Ch}=0$ and $\textsc{Ch}=2$. Finally, by chosing
$\tilde{\mathbf{x}}$ such that $w_{H}\big{(}\tilde{\mathbf{x}}\big{)}=w$ and
computing
$c_{1}=\textsf{Commit}(\mathbf{H}(\tilde{\mathbf{x}}+\mathbf{u})-\mathbf{y})$
and $c_{3}=\textsf{Commit}(\pi[\tilde{\mathbf{x}}+\mathbf{u}])$ as well as
$\textsc{Rsp}=(\pi,\tilde{\mathbf{x}}+\mathbf{u})$ in the case $\textsc{Ch}=1$
and $\textsc{Rsp}=(\pi[\tilde{\mathbf{x}}],\pi[\mathbf{u}])$ in the case
$\textsc{Ch}=2$, the malicious prover $\tilde{\mathsf{P}}$ will be accepted
for both $\textsc{Ch}=1$ and $\textsc{Ch}=2$. In addition, if a malicious
prover is able to cheat in the three cases, then one can build a knowledge
extractor solving an instance of the $\mathsf{SD}$ problem from its response.
This explains why this protocol has a soundness error equal to $2/3$. In
practice, one need to execute the protocol $\delta$ times to achieve a
negligible soundness error. This is not depicted in Figures 1 and 2 which
serve an illustrative purpose nonetheless these $\delta$ iterations are
depicted in Figure 3 which is used to describe a complete instantiation of our
new construction.

Regarding the zero-knowledge property of the proof, one can see that if
$\mathsf{COM}$ is a hiding commitment scheme, then Cmt does not reveal
anything on the secret $\mathbf{x}$. Moreover, the response of the prover
$\mathsf{P}$ only uses the secret through $\mathbf{u}+\mathbf{x}$ or
$\pi[\mathbf{x}]$ namely $\mathbf{x}$ is either masked by a random vector
$\mathbf{u}$ or random permutation $\pi$. Formally, one can build a simulator
that generates the view of an honest verifier with access to the public key
only.

##  3 Quasi-Cyclic Stern Proof of Knowledge

In this section and in the rest of the paper, we consider only quasi-cyclic
$[n,k]$ codes of index 2 (and rate $1/2$), that is $n=2k$. We present here a
new proof of knowledge for syndrome decoding based on the Stern protocol along
with quasi-cyclicity which shares similarities with the AGS proposal [1].
While one may think that Véron based protocols such as AGS would inherently be
more efficient than Stern based ones, we prove this belief to be erroneous
using some optimizations that can’t be applied to Véron based protocols. We
introduce the Quasi-Cyclic Stern protocol without optimization in Section 3.1.
Then, we present existing optimizations from the literature and introduce two
new optimizations in Section 3.2. Finally, we describe the new protocol along
with all the aforementionned optimizations in Section 3.3

$\displaystyle\underline{\mathsf{Setup}(1^{\lambda})~{}\&~{}\mathsf{Keygen}(\mathsf{param})}$
$\displaystyle\mathsf{param}=(n,k,w)\longleftarrow\mathsf{Setup}(1^{\lambda})$
$\displaystyle\mathbf{x}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{n}\text{
such that }w_{H}\big{(}\mathbf{x}\big{)}=w$
$\displaystyle\mathbf{H}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{(n-k)\times
n},~{}\mathbf{y}^{\top}=\mathbf{H}\mathbf{x}^{\top}$
$\displaystyle(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})=(\mathbf{x},(\mathbf{H},\mathbf{y}))$
$\displaystyle\underline{\mathsf{P}_{1}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})}$
$\displaystyle\pi\overset{\;\$}{\longleftarrow}S_{n},~{}\mathbf{u}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{n}$
$\displaystyle c_{1}=\textsf{Commit}(\pi\,||\,\mathbf{H}\mathbf{u})$
$\displaystyle c_{2}=\textsf{Commit}(\pi[\mathbf{u}])$ $\displaystyle
c_{3}=\textsf{Commit}(\pi[\mathbf{u}+\mathbf{x}])$
$\displaystyle\textsc{Cmt}=(c_{1},c_{2},c_{3})$
$\displaystyle\underline{\mathsf{V}_{1}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt})}$
$\displaystyle\textsc{Ch}\overset{\;\$}{\longleftarrow}\\{0,1,2\\}$
$\displaystyle\underline{\mathsf{P}_{2}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk},\textsc{Cmt},\textsc{Ch})}$
$\displaystyle\mathbf{if}\ \textsc{Ch}=0\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\textsc{Rsp}=\big{(}\pi,\,\mathbf{u}\big{)}$
$\displaystyle\mathbf{if}\ \textsc{Ch}=1\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\textsc{Rsp}=\big{(}\pi,\,\mathbf{u}+\mathbf{x}\big{)}$
$\displaystyle\mathbf{if}\ \textsc{Ch}=2\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\textsc{Rsp}=\big{(}\pi[\mathbf{u}],\,\pi[\mathbf{x}]\big{)}$

$\displaystyle\underline{\mathsf{V}_{2}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt},\textsc{Ch},\textsc{Rsp})}$
$\displaystyle\mathbf{if}\ \textsc{Ch}=0\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\bar{c}_{1}=\textsf{Commit}(\pi\,||\,\mathbf{H}\mathbf{u})$
$\displaystyle\mathmakebox{}\bar{c}_{2}=\textsf{Commit}(\pi[\mathbf{u}])$
$\displaystyle\mathmakebox{}\mathbf{if}\
c_{1}\neq\bar{c}_{1}~{}\textbf{or}~{}c_{2}\neq\bar{c}_{2}\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{return}\ \textsf{reject}$
$\displaystyle\mathbf{if}\ \textsc{Ch}=1\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\bar{c}_{1}=\textsf{Commit}(\pi\,||\,\mathbf{H}(\mathbf{u}+\mathbf{x})-\mathbf{y})$
$\displaystyle\mathmakebox{}\bar{c}_{3}=\textsf{Commit}(\pi[\mathbf{u}+\mathbf{x}])$
$\displaystyle\mathmakebox{}\mathbf{if}\
c_{1}\neq\bar{c}_{1}~{}\textbf{or}~{}c_{3}\neq\bar{c}_{3}\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{return}\ \textsf{reject}$
$\displaystyle\mathbf{if}\ \textsc{Ch}=2\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\bar{c}_{2}=\textsf{Commit}(\pi[\mathbf{u}])$
$\displaystyle\mathmakebox{}\bar{c}_{3}=\textsf{Commit}(\pi[\mathbf{u}]+\pi[\mathbf{x}])$
$\displaystyle\mathmakebox{}\mathbf{if}\
c_{2}\neq\bar{c}_{2}~{}\textbf{or}~{}c_{3}\neq\bar{c}_{3}~{}\textbf{or}~{}w_{H}\big{(}\pi[\mathbf{x}]\big{)}\neq
w\ \mathbf{then}\ $ $\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{return}\
\textsf{reject}$ $\displaystyle\mathbf{return}\ \textsf{accept}$

Figure 1: Stern Protocol

###  3.1 Quasi-Cyclic Stern Protocol Description

Our new zero-knowledge proof of knowledge is described in Figure 2. One can
see it as a Stern-like construction with additional structure. Indeed, we rely
on the $\mathsf{QCSD}$ problem rather than the $\mathsf{SD}$ problem in the
same spirit to what is done in [1]. Thanks to quasi-cyclicity, we can
introduce a new kind of challenge therefore designing an efficient 5-rounds
protocol achieving soundness error approximately equal to $1/2$. Let
$\mathbf{x}=(x_{0},\cdots,x_{k-1})\in\mathbb{F}_{2}^{k}$, we define the
$\textbf{rot}()$ operator as
$\textbf{rot}_{r}(\mathbf{x}):=(x_{k-r+1},\cdots,x_{k-r})$. For
$\mathbf{y}=(\mathbf{y}_{1},\mathbf{y}_{2})\in\mathbb{F}_{2}^{2k}$, we
slightly abuse notations and define
$\textbf{rot}_{r}(\mathbf{y}):=(\textbf{rot}_{r}(\mathbf{y}_{1}),\textbf{rot}_{r}(\mathbf{y}_{2}))$.
As we are now considering random parity-check matrices of quasi-cyclic codes
$\mathbf{H}\overset{\;\$}{\longleftarrow}\mathcal{QC}(\mathbb{F}_{2}^{k\times
2k})$, one can see that
$\mathbf{y}^{\top}=\mathbf{H}\mathbf{x}^{\top}\Leftrightarrow\textbf{rot}_{r}(\mathbf{y})^{\top}=\mathbf{H}\,\textbf{rot}_{r}(\mathbf{x})^{\top}$.
This implies that one can prove the knowledge of the secret $\mathbf{x}$
associated to the public value $\mathbf{y}$ using $k$ different equations.
This property allows to design a proof of knowledge with soundness error
approximately equal to $1/2$ thus bringing an improvement over the initial
Stern protocol which features a soundness error equal to $2/3$. Without our
new optimization described in Section 3.2, the protocol depicted in Figure 2
does not outperform existing constructions therefore we don’t provide its
correctness, soundness and zero-knowledge proofs. Instead, we defer the reader
to Section 3.3 where a construction including all the optimizations along with
all the aforementioned proofs can be found.

$\displaystyle\underline{\mathsf{Setup}(1^{\lambda})~{}\&~{}\mathsf{Keygen}(\mathsf{param})}$
$\displaystyle\mathsf{param}=(k,w)\longleftarrow\mathsf{Setup}(1^{\lambda})$
$\displaystyle\mathbf{x}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{2k}\text{
such that }w_{H}\big{(}\mathbf{x}\big{)}=w$
$\displaystyle\mathbf{H}\overset{\;\$}{\longleftarrow}\mathcal{QC}(\mathbb{F}_{2}^{k\times
2k}),~{}\mathbf{y}^{\top}=\mathbf{H}\mathbf{x}^{\top}$
$\displaystyle(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})=(\mathbf{x},(\mathbf{H},\mathbf{y}))$
$\displaystyle\underline{\mathsf{P}_{1}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})}$
$\displaystyle\pi\overset{\;\$}{\longleftarrow}S_{2k},~{}\mathbf{u}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{2k}$
$\displaystyle
c_{1}=\textsf{Commit}(\pi\,||\,\mathbf{H}\mathbf{u}),~{}c_{2}=\textsf{Commit}(\pi[\mathbf{u}])$
$\displaystyle\textsc{Cmt}_{1}=(c_{1},c_{2})$
$\displaystyle\underline{\mathsf{V}_{1}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1})}$
$\displaystyle r\overset{\;\$}{\longleftarrow}[0,k-1]$
$\displaystyle\textsc{Ch}_{1}=r$
$\displaystyle\underline{\mathsf{P}_{2}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1})}$
$\displaystyle\mathbf{x}_{r}=\textbf{rot}_{r}(\mathbf{x})$ $\displaystyle
c_{3}=\textsf{Commit}(\pi[\mathbf{u}+\mathbf{x}_{r}])$
$\displaystyle\textsc{Cmt}_{2}=c_{3}$
$\displaystyle\underline{\mathsf{V}_{2}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2})}$
$\displaystyle\textsc{Ch}_{2}\overset{\;\$}{\longleftarrow}\\{0,1\\}$

$\displaystyle\underline{\mathsf{P}_{3}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2},\textsc{Ch}_{2})}$
$\displaystyle\mathbf{if}\ \textsc{Ch}_{2}=0\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\textsc{Rsp}=\big{(}\pi,\,\mathbf{u}+\mathbf{x}_{r}\big{)}$
$\displaystyle\mathbf{if}\ \textsc{Ch}_{2}=1\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\textsc{Rsp}=\big{(}\pi[\mathbf{u}],\,\pi[\mathbf{x}_{r}]\big{)}$
$\displaystyle\underline{\mathsf{V}_{3}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2},\textsc{Ch}_{2},\textsc{Rsp})}$
$\displaystyle\mathbf{if}\ \textsc{Ch}_{2}=0\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\bar{c}_{1}=\textsf{Commit}(\pi\,||\,\mathbf{H}(\mathbf{u}+\mathbf{x}_{r})-\textbf{rot}_{r}(\mathbf{y}))$
$\displaystyle\mathmakebox{}\bar{c}_{3}=\textsf{Commit}(\pi[\mathbf{u}+\mathbf{x}_{r}])$
$\displaystyle\mathmakebox{}\mathbf{if}\
c_{1}\neq\bar{c}_{1}~{}\textbf{or}~{}c_{3}\neq\bar{c}_{3}\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{return}\ \textsf{reject}$
$\displaystyle\mathbf{if}\ \textsc{Ch}_{2}=1\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\bar{c}_{2}=\textsf{Commit}(\pi[\mathbf{u}])$
$\displaystyle\mathmakebox{}\bar{c}_{3}=\textsf{Commit}(\pi[\mathbf{u}]+\pi[\mathbf{x}_{r}])$
$\displaystyle\mathmakebox{}\mathbf{if}\
c_{2}\neq\bar{c}_{2}~{}\textbf{or}~{}c_{3}\neq\bar{c}_{3}~{}\textbf{or}~{}w_{H}\big{(}\pi[\mathbf{x}_{r}]\big{)}\neq
w\ \mathbf{then}\ $ $\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{return}\
\textsf{reject}$ $\displaystyle\mathbf{return}\ \textsf{accept}$

Figure 2: Quasi-Cyclic Stern Protocol (one iteration, without optimization)

###  3.2 Existing Improvements and New Optimizations

In this section, we recall three optimizations from the literature (commitment
compression, small weight vector compression and a mitigation against an
existing attack) and introduce two new optimizations (additional vector
compression from seeds for Stern based protocol and seed compression). One
should note that our first optimization can’t be applied to the AGS protocol
which is the most efficient construction to date. Using this optimization, we
are able to design a proof of knowledge for syndrome decoding that outperforms
existing protocols.

Commitment compression [1]. We recall that code-based proofs of knowledge
generally feature a soundness error of $2/3$ or $1/2$ therefore one need to
perform $\delta$ iterations of these protocols to get a negligible soundness
error. Using Figure 2 as an illustrative example, the idea is to compress the
commitments over all the iterations so that only two initial commitments
$\textsc{Cmt}_{1}=(c_{1,1}||c_{1,2}||\cdots||c_{\delta,1}||c_{\delta,2})$ and
$\textsc{Cmt}_{2}=(c_{1,3}||\cdots||c_{\delta,3})$ need to be sent. As the
verifier is only able to reconstruct 2 out of 3 commitments himself, the
prover must send him the missing commitment at the end of each iteration.
Overall, this reduces the number of commitments to be sent from $3\delta$ to
$2+\delta$.

Small weight vector compression [1]. The prover must reveal a permutation of a
small weight vector $\pi[\mathbf{x}_{r}]$ to answer some challenges.
Leveraging the small weight of $\mathbf{x}_{r}$, one may use a compression
algorithm before sending $\pi[\mathbf{x}_{r}]$ thus reducing the cost of
sending small weight vectors from $n$ to approximately $n-k$.

Mitigation of an attack against 5-rounds protocols [13]. An attack against
5-rounds identification schemes that rely on parallel repetitions was recently
described in [27]. Although it is targeting the MQDSS scheme, this attack is
also relevant for both AGS and our construction. One have to increase the
number of iterations $\delta$ of the underlying proof of knowledge in order
for the signature to remain secure which increase its size. One way to
mitigate this attack is to consider several instances of the $\mathsf{SD}$
problem within the keypair namely using
$\mathsf{\vphantom{p}sk}=(\mathbf{x}^{i})_{i\in[1,s]}$ and
$\mathsf{\vphantom{p}pk}=(\mathbf{H},(\mathbf{y}^{i})^{\top}=\mathbf{H}(\mathbf{x}^{i})^{\top})_{i\in[1,s]}$.
Doing so, the first challenge space size is increased from $k$ to $s\times k$
which makes the attack less efficient so that $\delta$ won’t need to be
increased as much as initially thought. In practice, this introduces a trade-
off between key size and signature size.

Additional vector compression from seeds. Starting from the initial Stern
proposal, all constructions suggest to use seeds in order to improve the
efficiency of the scheme. Using Figure 2 for illustrative purposes, one can
use a seed $\theta$ to compute $\pi$ and then substitute $\pi$ by $\theta$ in
the prover’s response. We now introduce an additional vector compression that
is only applicable to $\mathsf{SD}$ based protocols. One can go one step
further and use a seed $\xi$ to generate a random value
$\mathbf{v}\overset{\;\$,\xi}{\longleftarrow}\mathbb{F}_{2}^{n}$ and then
compute the value $\mathbf{u}=\pi^{-1}[\mathbf{v}]$. When the prover is
required to send $\pi[\mathbf{u}]$, he now needs to send $\mathbf{v}$ which
can be subtituted by $\xi$. Instead of sending a vector of size $n$, the
prover only sends a seed which greatly reduces the communication cost. We now
explain why this optimization can’t be applied to the AGS protocol thus
explaning why the proof of knowledge presented in Section 3.3 outperforms the
AGS construction. Under the $\mathsf{GSD}$ representation, the prover need to
send $\pi[\mathbf{uG}]$ rather than $\pi[\mathbf{u}]$ whenever
$\textsc{Ch}_{2}=1$. Therefore, one would need to have
$\mathbf{uG}=\pi^{-1}[\mathbf{v}]$ with $\mathbf{v}$ random in order to apply
the aforementioned optimization. However, the probability of finding
$\mathbf{u}$ satisfying this condition given a random $\mathbf{v}$ is
negligible as $\mathbf{uG}$ is a codeword.

Seed compression. Using the previous optimization, one can see that the prover
sends one seed during each iteration either $\theta$ from which $\pi$ can be
recomputed or $\xi$ from which $\pi[\mathbf{u}]$ can be recomputed. Let us
consider two consecutive iterations of the protocol, the prover will have to
send one of the following tuple of seeds:
$(\theta_{1},\theta_{2}),(\theta_{1},\xi_{2}),(\xi_{1},\theta_{2}),(\xi_{1},\xi_{2})$.
If master seeds $\theta$ (respectively $\xi$) are used to generate
$\theta_{1}$ and $\theta_{2}$ (respectively $\xi_{1}$ and $\xi_{2}$), then the
prover will have to send one of the following values:
$\theta,(\theta_{1},\xi_{2}),(\xi_{1},\theta_{2}),\xi$. By using such a
technique, one reduces the average communication cost associated to seeds by
$25$%.

###  3.3 Optimized Quasi-Cyclic Stern Protocol Description

In this section, we apply all the optimizations from Section 3.2 on the
protocol described in Section 3.1. The resulting proof of knowledge is
depicted in Figure 3. We discuss the correctness, soundness and zero-knowledge
properties of this protocol using Theorems 3.1, 3.3 and 3.4 as well as their
associated proofs. The soundness of the construction relies on a reduction
from the $\mathsf{QCSD}$ problem to the $\mathsf{DiffSD}$ problem ; see
Definition 11 and Theorem 3.2. Hereafter, we denote by
$(\mathsf{Compress},\mathsf{Decompress})$ the compression / decompression
algorithm that take as input the response Rsp of the prover $\mathsf{P}$ and
applies the small weight vector compression and seed compression optimizations
from Section 3.2. Doing so, we slightly abuse notations as the seed
compression should be done when the seeds are generated rather than at the
response step. However, this simplifies the description of the protocol while
not being related to its security.

$\displaystyle\underline{\mathsf{Setup}(1^{\lambda})~{}\&~{}\mathsf{Keygen}(\mathsf{param})}$
$\displaystyle\mathsf{param}=(k,w,\delta,s,|\mathsf{seed}|)\longleftarrow\mathsf{Setup}(1^{\lambda})$
$\displaystyle\phi_{1}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{|\mathsf{seed}|},\phi_{2}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{|\mathsf{seed}|}$
$\displaystyle\mathbf{H}\overset{\;\$,\phi_{2}}{\longleftarrow}\mathcal{QC}(\mathbb{F}_{2}^{k\times
2k})$ $\displaystyle\mathbf{for}\ i\in[1\;..\;s]\ \mathbf{do}$
$\displaystyle\mathmakebox{}\mathbf{x}^{i}\overset{\;\$,\phi_{1}}{\longleftarrow}\mathbb{F}_{2}^{2k}\text{},~{}(\mathbf{y}^{i})^{\top}=\mathbf{H}(\mathbf{x}^{i})^{\top}$
$\displaystyle(\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})=(\phi_{1},(\phi_{2},\mathbf{y}^{1},\cdots,\mathbf{y}^{s}))$
$\displaystyle\underline{\mathsf{P}_{1}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk})}$
$\displaystyle\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}\theta_{i}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{|\mathsf{seed}|},~{}\pi_{i}\overset{\;\$,\theta_{i}}{\longleftarrow}S_{2k}$
$\displaystyle\mathmakebox{}\xi_{i}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{|\mathsf{seed}|},~{}\mathbf{v}_{i}\overset{\;\$,\xi_{i}}{\longleftarrow}\mathbb{F}_{2}^{2k},~{}\mathbf{u}_{i}=\pi^{-1}[\mathbf{v}_{i}]$
$\displaystyle\mathmakebox{}c_{i,1}=\textsf{Commit}(\pi_{i}\,||\,\mathbf{H}\mathbf{u}_{i}),~{}c_{i,2}=\textsf{Commit}(\pi_{i}[\mathbf{u}_{i}])$
$\displaystyle\textsc{Cmt}_{1}=\textsf{Commit}(c_{1,1}||c_{1,2}||\cdots||c_{\delta,1}||c_{\delta,2})$
$\displaystyle\underline{\mathsf{V}_{1}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1})}$
$\displaystyle\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}s_{i}\overset{\;\$}{\longleftarrow}[0,s-1],~{}r_{i}\overset{\;\$}{\longleftarrow}[0,k-1]$
$\displaystyle\textsc{Ch}_{1}=((s_{1},r_{1}),\cdots,(s_{\delta},r_{\delta}))$
$\displaystyle\underline{\mathsf{P}_{2}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1})}$
$\displaystyle\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}\mathbf{x}^{s_{i}}_{r_{i}}=\textbf{rot}_{r_{i}}(\mathbf{x}^{s_{i}})$
$\displaystyle\mathmakebox{}c_{i,3}=\textsf{Commit}(\pi_{i}[\mathbf{u}_{i}+\mathbf{x}^{s_{i}}_{r_{i}}])$
$\displaystyle\textsc{Cmt}_{2}=\textsf{Commit}(c_{1,3}||\cdots||c_{\delta,3})$
$\displaystyle\underline{\mathsf{V}_{2}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2})}$
$\displaystyle\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}b_{i}\overset{\;\$}{\longleftarrow}\\{0,1\\}$
$\displaystyle\textsc{Ch}_{2}=(b_{1},\cdots,b_{\delta})$

$\displaystyle\underline{\mathsf{P}_{3}(\mathsf{param},\mathsf{\vphantom{p}sk},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2},\textsc{Ch}_{2})}$
$\displaystyle\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}\mathbf{if}\ b_{i}=0\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}d_{i}=\big{(}\theta_{i},\,\mathbf{u}_{i}+\mathbf{x}^{s_{i}}_{r_{i}},\,c_{i,2}\big{)}$
$\displaystyle\mathmakebox{}\mathbf{if}\ b_{i}=1\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}d_{i}=\big{(}\xi_{i},\,\pi_{i}[\mathbf{x}^{s_{i}}_{r_{i}}],\,c_{i,1}\big{)}$
$\displaystyle\textsc{Rsp}=\mathsf{Compress}(d_{1},\cdots,d_{\delta})$
$\displaystyle\underline{\mathsf{V}_{3}(\mathsf{param},\mathsf{\vphantom{p}pk},\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2},\textsc{Ch}_{2},\textsc{Rsp})}$
$\displaystyle(d_{1},\cdots,d_{\delta})=\mathsf{Decompress}(\textsc{Rsp})$
$\displaystyle\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}\mathbf{if}\ b_{i}=0\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}\pi_{i}\overset{\;\$,\theta_{i}}{\longleftarrow}S_{2k}$
$\displaystyle\mathmakebox{}\mathmakebox{}\bar{c}_{i,1}=\textsf{Commit}(\pi_{i}\,||\,\mathbf{H}(\mathbf{u}_{i}+\mathbf{x}^{s_{i}}_{r_{i}})-\textbf{rot}_{r_{i}}(\mathbf{y}^{s_{i}}))$
$\displaystyle\mathmakebox{}\mathmakebox{}\bar{c}_{i,2}=c_{i,2}$
$\displaystyle\mathmakebox{}\mathmakebox{}\bar{c}_{i,3}=\textsf{Commit}(\pi_{i}[\mathbf{u}_{i}+\mathbf{x}^{s_{i}}_{r_{i}}])$
$\displaystyle\mathmakebox{}\mathbf{if}\ b_{i}=1\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{v}_{i}\overset{\;\$,\xi_{i}}{\longleftarrow}\mathbb{F}_{2}^{2k}$
$\displaystyle\mathmakebox{}\mathmakebox{}\bar{c}_{i,1}=c_{i,1}$
$\displaystyle\mathmakebox{}\mathmakebox{}\bar{c}_{i,2}=\textsf{Commit}(\mathbf{v}_{i})$
$\displaystyle\mathmakebox{}\mathmakebox{}\bar{c}_{i,3}=\textsf{Commit}(\mathbf{v}_{i}+\pi_{i}[\mathbf{x}^{s_{i}}_{r_{i}}])$
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{if}\
w_{H}\big{(}\pi_{i}[\mathbf{x}^{s_{i}}_{r_{i}}]\big{)}\neq w\ \mathbf{then}\ $
$\displaystyle\mathmakebox{}\mathmakebox{}\mathmakebox{}\mathbf{return}\
\textsf{reject}$ $\displaystyle\mathbf{if}\
\mathsf{Open}(\textsc{Cmt}_{1},\,\bar{c}_{1,1}||\bar{c}_{1,2}||\cdots||\bar{c}_{\delta,1}||\bar{c}_{\delta,2})\neq
1\ \mathbf{then}\ $ $\displaystyle\mathmakebox{}\mathbf{return}\
\textsf{reject}$ $\displaystyle\mathbf{if}\
\mathsf{Open}(\textsc{Cmt}_{2},\,\bar{c}_{1,3}||\cdots||\bar{c}_{\delta,3})\neq
1\ \mathbf{then}\ $ $\displaystyle\mathmakebox{}\mathbf{return}\
\textsf{reject}$ $\displaystyle\mathbf{return}\ \textsf{accept}$

Figure 3: Quasi-Cyclic Stern Protocol (with optimizations)

######  Theorem 3.1 (Correctness)

The proof of knowledge depicted in Figure 3 satisfies the correctness
property.

###### Proof

The correctness follows straightforwardly from the protocol description.

######  Definition 11 ($\mathsf{DiffSD}$ problem)

Given positive integers ($n=2k$), $k$, $w$, $\alpha$, a random parity-check
matrix of a quasi-cyclic code
$\mathbf{H}\overset{\;\$}{\longleftarrow}\mathcal{QC}(\mathbb{F}_{2}^{k\times
2k})$ and a syndrome $\mathbf{y}\in\mathbb{F}_{2}^{k}$ such that
$\mathbf{Hx}^{\top}=\mathbf{y}^{\top}$ where
$\mathbf{x}\in\mathbb{F}_{2}^{2k}$ and $w_{H}\big{(}\mathbf{x}\big{)}=w$. The
differential syndrome decoding problem $\mathsf{DiffSD}(n,k,w,\alpha)$ asks to
find a set of vectors
$(\mathbf{c},(\mathbf{z}_{1},\cdots,\mathbf{z}_{\alpha}))\in\mathbb{F}_{2}^{k}\times(\mathbb{F}_{2}^{2k})^{\alpha}$
and a set of distinct indices $r_{1},\ldots{},r_{\alpha}$ such that for each
$i\in[1\;..\;\alpha]$,
$\mathbf{H}\,\mathsf{\mathbf{rot}}_{r_{i}}(\mathbf{x}^{\top})=\mathbf{c}+\mathbf{H}\mathbf{z}_{i}^{\top}$
with $w_{H}\big{(}\mathbf{z}_{i}\big{)}=w$.

######  Theorem 3.2 (Reduction from $\mathsf{QCSD}$ to $\mathsf{DiffSD}$)

If there exists a $\mathsf{PPT}$ algorithm solving the
$\mathsf{DiffSD}(n,k,w,\alpha)$ problem, then there exists a $\mathsf{PPT}$
algorithm solving the $\mathsf{QCSD}(n,k,w)$ problem.

###### Proof

The proof of Theorem 3.2 can be found in [1, 32].

######  Theorem 3.3 (Soundness)

Let $k$ and $\delta$ be public parameters denoting respectively the dimension
of a $[n=2k,k]$ quasi-cyclic code and the number of iterations within the
protocol. If $\mathsf{COM}$ is a binding commitment scheme, then the proof of
knowledge depicted in Figure 3 is sound with soundness error
$(\frac{sk+\alpha-1}{2sk})^{\delta}$ for some parameters $\alpha$ and $s$
under the $\mathsf{QCSD}$ assumption.

Remark. A natural question that arises is how one choose $\alpha$, $s$, $k$
and $\delta$ ? One can prove that if an adversary is able to successfully
answer to $sk+\alpha$ challenges out of all the $2sk$ possible challenges,
then he can solve the differential syndrome decoding problem $\mathsf{DiffSD}$
for some parameter $\alpha$. When $\alpha$ is large enough, there exists a
reduction from the $\mathsf{DiffSD}$ problem to the $\mathsf{QCSD}$ problem.
Once $\alpha$ and $k$ have been chosen so that this reduction exists and leads
to a difficult $\mathsf{QCSD}$ instance, one only need to pick $s$ and
$\delta$ so that $(\frac{sk+\alpha-1}{2sk})^{\delta}$ is negligible and the
cost of the attack from [27] is superior to $2^{\lambda}$.

###### Proof

We first prove that if there is an adversary $\mathcal{A}$ that is able to
cheat with probability greater than $(\frac{sk+\alpha-1}{2sk})^{\delta}$ then
one can build a knowledge extractor $\mathsf{Ext}$ that solve the
$\mathsf{DiffSD}(n,k,w,\alpha)$ problem. Such an adversary is able to cheat
with probability at least $(\frac{sk+\alpha}{2sk})$ in a given iteration $i$
where $i\in[1,\delta]$. Within this specific iteration (we ommit the index $i$
for simplicity hereafter), the adversary $\mathcal{A}$ is able to sucessfully
answer $sk+\alpha$ challenges. This implies that there are
$((s_{1},r_{1}),\cdots,(s_{\alpha},r_{\alpha}))$ challenges for which the
adversary $\mathcal{A}$ is able to produce successfull responses for both the
cases $b=0$ and $b=1$. Let
$d^{\,r_{j},b}=(d^{\,r_{j},b}_{1},d^{\,r_{j},b}_{2},d^{\,r_{j},b}_{3})_{j\in[1,\alpha],b\in\\{0,1\\}}$
denote the responses of the adversary $\mathcal{A}$ (after using the
$\mathsf{Decompress}$ algorithm) to these challenges, one can build a
knowledge extractor $\mathsf{Ext}$ as follows:

$\displaystyle\vphantom{\rule[1.93748pt]{0.0pt}{0.0pt}}\text{1. Let
}\bar{\theta}^{j}=d^{\,r_{j},0}_{1},\text{ compute
}\bar{d}^{\,r_{j},0}_{1}\overset{\;\$,\bar{\theta}^{j}}{\longleftarrow}S_{n}\text{
for all }j\in[1,\alpha]$ $\displaystyle\text{2. Let
}\bar{\xi}^{j}=d^{\,r_{j},1}_{1},\text{ compute
}\bar{d}^{\,r_{j},1}_{1}\overset{\;\$,\bar{\xi}^{j}}{\longleftarrow}\mathbb{F}_{2}^{n}\text{
for all }j\in[1,\alpha]$ $\displaystyle\text{3. Compute
}\mathbf{c}_{1}=\bar{d}^{\,r_{1},1}_{1}=\cdots=\bar{d}^{\,r_{\alpha},1}_{1}$
$\displaystyle\text{4. Compute
}\pi=\bar{d}^{\,r_{1},0}_{1}=\cdots=\bar{d}^{\,r_{\alpha},0}_{1}$
$\displaystyle\text{5. Compute
}\mathbf{c}_{2}=\mathbf{H}d^{\,r_{1},0}_{2}-\textbf{rot}_{r_{1}}(\mathbf{y})=\cdots=\mathbf{H}d^{\,r_{\alpha},0}_{2}-\textbf{rot}_{r_{\alpha}}(\mathbf{y})$
$\displaystyle\text{6. Compute
}\mathbf{c}_{3}=\mathbf{H}(\pi^{-1}[\mathbf{c}_{1}])-\mathbf{c}_{2}$
$\displaystyle\text{7. Compute
}\mathbf{z}_{j}=\pi^{-1}[d^{\,r_{j},1}_{2}]\text{ for all }j\in[1,\alpha]$
$\displaystyle\text{8. Output
}(\mathbf{c}_{3},\mathbf{z}_{1},\cdots,\mathbf{z}_{\alpha})$

We now prove that $(\mathbf{c}_{3},\mathbf{z}_{1},\cdots,\mathbf{z}_{\alpha})$
is a solution to the $\mathsf{DiffSD}(n,k,w,\alpha)$ problem. If
$\mathsf{COM}$ is a binding commitment scheme, one can compute
$\mathbf{c}_{1}$ as all the $\bar{d}^{\,r_{j},1}_{1}$ values are equals due to
commitment $c_{2}$. Likewise, one can compute $\pi$ and $\mathbf{c}_{2}$ as
all the values $\bar{d}^{\,r_{j},0}_{1}$ and
$\mathbf{H}d^{\,r_{j},0}_{2}-\textbf{rot}_{r_{j}}(\mathbf{y})$ are equals due
to commitment $c_{1}$. Using the same argument for commitment $c_{3}$, one has
$\pi[d^{\,r_{j},0}_{2}]=\mathbf{c}_{1}+d^{\,r_{j},1}_{2}$ hence
$d^{\,r_{j},0}_{2}=\pi^{-1}[\mathbf{c}_{1}]+\pi^{-1}[d^{\,r_{j},1}_{2}]$ for
all $j\in[1,\alpha]$. From commitment $c_{1}$, one deduces that
$\mathbf{c}_{2}=\mathbf{H}(\pi^{-1}[\mathbf{c}_{1}])+\mathbf{H}(\pi^{-1}[d^{\,r_{j},1}_{2}])-\textbf{rot}_{r_{j}}(\mathbf{y})$
for all $j\in[1,\alpha]$. Using quasi-cyclic codes, one gets
$\textbf{rot}_{r_{j}}(\mathbf{y})=\mathbf{H}\,\textbf{rot}_{r_{j}}(\mathbf{x})$
which gives
$\mathbf{H}\,\textbf{rot}_{r_{j}}(\mathbf{x})=\mathbf{c}_{3}+\mathbf{H}\mathbf{z}_{j}$
for all $j\in[1,\alpha]$. In addition, one have
$w_{H}\big{(}\mathbf{z}_{j}\big{)}=w$ as
$w_{H}\big{(}d^{\,r_{j},1}_{2}\big{)}=w$ for all $j\in[1,\alpha]$. Therefore
$(\mathbf{c}_{3},\mathbf{z}_{1},\cdots,\mathbf{z}_{\alpha})$ is a solution to
the $\mathsf{DiffSD}(n,k,w,\alpha)$ problem. Using Theorem 3.2 completes the
proof as there exists a reduction from $\mathsf{QCSD}(n,k,w)$ to
$\mathsf{DiffSD}(n,k,w,\alpha)$ for an appropriate choice of $\alpha$.

######  Theorem 3.4 (Honest Verifier Zero-Knowledge)

If $\mathsf{COM}$ is a hiding commitment scheme, then the proof of knowledge
depicted in Figure 3 satisfies the Honest-Verifier Zero-Knowledge property.

###### Proof

We build a $\mathsf{PPT}$ simulator $\mathsf{Sim}$ that generates the view of
an honest verifier with access to the public key
$\mathsf{\vphantom{p}pk}=(\phi_{2},\mathbf{y}^{1},\cdots,\mathbf{y}^{s})$
only:
$\displaystyle\vphantom{\rule[1.93748pt]{0.0pt}{0.0pt}}\text{1.
}\mathsf{Sim}\text{ samples
}G_{1}=((s_{1},r_{1}),\cdots,(s_{\delta},r_{\delta}))\overset{\;\$}{\longleftarrow}([0,s-1]\times[0,k-1])^{\delta}\text{
and computes}$ $\displaystyle\mathmakebox{}\mathbf{for}\ i\in[1\;..\;\delta]\
\mathbf{do}$
$\displaystyle\mathmakebox{}\mathmakebox{}\theta_{i}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{|\mathsf{seed}|},~{}\pi_{i}\overset{\;\$,\theta_{i}}{\longleftarrow}S_{n},~{}\xi_{i}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{|\mathsf{seed}|},~{}\mathbf{v}_{i}\overset{\;\$,\xi_{i}}{\longleftarrow}\mathbb{F}_{2}^{2k},~{}\mathbf{u}_{i}=\pi_{i}^{-1}[\mathbf{v}_{i}]$
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{H}\overset{\;\$,\phi_{2}}{\longleftarrow}\mathcal{QC}(\mathbb{F}_{2}^{k\times
2k}),~{}c_{i,1}=\textsf{Commit}(\pi_{i}\,||\,\mathbf{H}\mathbf{u}_{i}),~{}c_{i,2}=\textsf{Commit}(\pi_{i}[\mathbf{u}_{i}])$
$\displaystyle\text{2. }\mathsf{Sim}\text{ sends
}\textsc{Cmt}_{1}=\textsf{Commit}(c_{1,1}||c_{1,2}||\cdots||c_{\delta,1}||c_{\delta,2})\text{
to }\mathcal{A}$ $\displaystyle\text{3. }\mathcal{A}\text{ answers
}\textsc{Ch}_{1}=((s_{1},r_{1}),\cdots,(s_{\delta},r_{\delta}))\text{ to
}\mathsf{Sim}$ $\displaystyle\text{4. }\text{If
}G_{1}\neq\textsc{Ch}_{1}\text{, rewind to step 1}$

$\displaystyle\vphantom{\rule[1.93748pt]{0.0pt}{0.0pt}}\text{5.
}\mathsf{Sim}\text{ samples
}G_{2}=(b_{1},\cdots,b_{\delta})^{\delta}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\delta}\text{
and computes}$ $\displaystyle\mathmakebox{}\mathbf{for}\ i\in[1\;..\;\delta]\
\mathbf{do}$ $\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{if}\ b_{i}=0\
\mathbf{then}\ \text{ compute }\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}\text{ such
that
}\mathbf{H}\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}=\textbf{rot}_{r_{i}}(\mathbf{y}^{s_{i}})\text{
(no weight constraint) }$
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{if}\ b_{i}=1\ \mathbf{then}\
\text{ compute
}\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}\overset{\;\$}{\longleftarrow}\mathbb{F}_{2}^{n}\text{
such that }w_{H}\big{(}\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}\big{)}=w$
$\displaystyle\mathmakebox{}\mathmakebox{}c_{i,3}=\textsf{Commit}(\pi_{i}[\mathbf{u}_{i}+\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}])$
$\displaystyle\text{6. }\mathsf{Sim}\text{ sends
}\textsc{Cmt}_{2}=\textsf{Commit}(c_{1,3}||\cdots||c_{\delta,3})\text{ to
}\mathcal{A}.$ $\displaystyle\text{7. }\mathcal{A}\text{ answers
}\textsc{Ch}_{2}=(b_{1},\cdots,b_{\delta})\text{ to }\mathsf{Sim}.$
$\displaystyle\text{8. }\text{If }G_{2}\neq\textsc{Ch}_{2}\text{, rewind to
step 5}$ $\displaystyle\text{9. }\mathsf{Sim}\text{ computes }$
$\displaystyle\mathmakebox{}\mathbf{for}\ i\in[1\;..\;\delta]\ \mathbf{do}$
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{if}\ b_{i}=0\ \mathbf{then}\
~{}d_{i}=\big{(}\theta_{i},\,\mathbf{u}_{i}+\mathbf{\tilde{x}}^{s_{i}}_{r_{i}},\,c_{i,2}\big{)}$
$\displaystyle\mathmakebox{}\mathmakebox{}\mathbf{if}\ b_{i}=1\ \mathbf{then}\
~{}d_{i}=\big{(}\xi_{i},\,\pi_{i}[\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}],\,c_{i,1}\big{)}$
$\displaystyle\text{10. }\mathsf{Sim}\text{ sends
}\textsc{Rsp}=\mathsf{Compress}(d_{1},\cdots,d_{\delta})\text{ to
}\mathcal{A}.$

The view generated by $\mathsf{Sim}$ is
$(\textsc{Cmt}_{1},\textsc{Ch}_{1},\textsc{Cmt}_{2},\textsc{Ch}_{2},\textsc{Rsp})$.
If $\mathsf{COM}$ is an hiding commitment scheme, then $\textsc{Cmt}_{1}$ and
$\textsc{Cmt}_{2}$ are indistinguishable in the simulation and during the real
execution. In the honest verifier setting, $\textsc{Ch}_{1}$ and
$\textsc{Ch}_{2}$ are generated similarly in the simulation and in the real
execution. Thus, one only needs to check Rsp. The simulator $\mathsf{Sim}$
behaves exactly as an honest prover $\mathsf{P}$ except with respect to the
values $(\mathbf{u}_{i}+\mathbf{\tilde{x}}^{s_{i}}_{r_{i}})$ and
$\pi_{i}[\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}]$. One can see that
$(\mathbf{u}_{i}+\mathbf{x}^{s_{i}}_{r_{i}})$ and
$(\mathbf{u}_{i}+\mathbf{\tilde{x}}^{s_{i}}_{r_{i}})$ follow the same
probability distribution as $\mathbf{u}_{i}$ is sampled uniformly at random
from $\mathbb{F}_{2}^{n}$. In addition, $\pi_{i}[\mathbf{x}^{s_{i}}_{r_{i}}]$
and $\pi_{i}[\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}]$ follow the same probability
distribution as (i) $\mathbf{\tilde{x}}^{s_{i}}_{r_{i}}$ and
$\mathbf{x}^{s_{i}}$ are sampled uniformly at random from the same
distribution and (ii) $\mathbf{x}^{s_{i}}$ and $\mathbf{x}^{s_{i}}_{r_{i}}$
follow the same probability distribution. Finally, one can see that the
simulator runs in polynomial time with $2\times s\times k\times\delta$
expected rewinds.

##  4 Parameters and Resulting Sizes

The system parameters $(n,k,w,s,\delta)$ must be such that all known attacks
cost more than $2^{\lambda}$ elementary operations where $\lambda$ is the
security parameter. Applying the attacks below provides the parameters given
in Table 1. The table also provides a comparison with other schemes rescaled
to offer the same security.

Decoding attack. We consider the BJMM generic decoder [10] with estimates from
[25]. The parameters $(n,k,w)$ will be chosen such that decoding $w$ errors in
a binary quasi-cyclic $[n,k]$ code costs at least $2^{\lambda}$. The attacker
has access to $N=sk$ syndromes (the $k$ rotations of the $s$ public keys) and
is successful by decoding only one of them. As shown in [33], this multiple
targets attack reduces the complexity by a factor $\sqrt{N}$. This factor is
taken into account in Table 1.

Soundness error. Following [1], for given $(n,k,w)$, solving
$\mathsf{DiffSD}(n,k,w,\alpha)$ provides a solution to $\mathsf{QCSD}(n,k,w)$
with probability $1-\varepsilon(\alpha)$ where
$\varepsilon(\alpha)\approx{n\choose w}^{\alpha-1}/2^{(n-k)(\alpha-2)}$. The
soundness error for one iteration cannot exceed
$\pi^{*}=\frac{sk+\alpha^{*}-1}{2sk}$ where $\alpha^{*}$ is the largest
integer such that $\varepsilon(\alpha^{*})\leq 2^{-\lambda}$. The soundness
error for $\delta$ iterations is $(\pi^{*})^{\delta}$ and it is lower than
$2^{-\lambda}$ if $\delta\geq\frac{-\lambda}{\log_{2}\pi^{*}}$.

Attack against 5-rounds protocols. The attack of [27] can be adapted from
MQDSS to the 5-rounds Stern ZK protocol. For $\delta$ iterations of the
protocol, the attacker will find the value of $\tau^{*}$ (the number of second
challenges to guess) which minimizes the attack cost
$P^{-1}+2^{\delta-\tau^{*}}$ where
$P=\sum_{\tau\geq\tau^{*}}{\delta\choose\tau}\left(\frac{1}{sk}\right)^{\tau}\left(\frac{sk-1}{sk}\right)^{\delta-\tau}$.
The choice of $\delta$ must be such that this cost is $\geq 2^{\lambda}$.

Table 1: Parameters and signature sizes in bytes for $\lambda=128$ | $n$ | $k$ | $w$ | $\delta$ | $s$ |  $\mathsf{\vphantom{p}sk}$ size |  $\mathsf{\vphantom{p}pk}$ size |  $\sigma$ size
---|---|---|---|---|---|---|---|---
Stern [34] | 1190 | 595 | 131 | 219 | - | 16 B | 165 B | 37.6 kB
Véron [35, 13] | 1190 | 595 | 131 | 219 | - | 16 B | 165 B | 32.2 kB
AGS [1, 13] | 1306 | 653 | 137 | 151 | 1 | 16 B | 179 B | 30.5 kB
145 | 4 | 16 B | 669 B | 29.3 kB
141 | 20 | 16 B | 3.3 kB | 28.5 kB
This Paper |  1306 |  653 |  137 | 151 | 1 | 16 B | 179 B | 25.2 kB
145 | 4 | 16 B | 669 B | 24.2 kB
141 |  20 |  16 B |  3.3 kB |  23.5 kB

Signature length and scalability. The signature consists of the outputs of
$\mathsf{P}_{1},\mathsf{P}_{2},\mathsf{P}_{3}$: two commitments and all the
$d_{i}$ (see Figure 3). Each response $d_{i}$ consists of a seed, a
commitment, and a word of $\mathbb{F}_{2}^{n}$ with no particular structure if
$b_{i}=0$ and of weight $w$ if $b_{i}=1$. The commitments are taken of length
$2\lambda$ and the seeds of length $\lambda$ as in MQDSS. The words of weight
$w$ can be compressed to $n-k$ bits. Finally the seeds can be structured
pairwise, as explained in Section 3.2, allowing to save one seed every 4
iterations on average. For codes of rate $1/2$ ($k=n/2$) the average length of
the signature is $|\sigma|=4\lambda+\delta(2.75\lambda+0.75n)$. Both $\delta$
and $n$ will grow linearly with the security parameters $\lambda$ and thus the
signature length grows as $\lambda^{2}$, roughly we have here $|\sigma|\approx
11\lambda^{2}$.

Comparison with other schemes. There exist many post-quantum signature schemes
based on the Fiat-Shamir transform, some of them were submitted to the NIST
standardization process [17, 19] and some other have been published recently
[14, 9]. All these schemes reduce independently to a given difficult problem
like for instance the MQ, PKP or $\mathsf{SD}$ problems. The scheme proposed
in [9] is based on the hardness of the code equivalence problem, which is not
NP-complete but relates to the syndrome decoding problem. For 128 bits of
security, depending on these different post-quantum ZK signature schemes, the
size of the signature may vary (also depending on chosen tradeoffs) between
12kB for [14] and 40kB for MQDSS [19]. Hence our results for signature lengths
compare well to other schemes and achieve the best signature lengths for ZK
schemes solely based on the syndrome decoding problem. A strong feature of the
syndrome decoding problem being that the problem has been used for a long
time, the attacks are well understood, and thus significant speedups are
unlikely to occur.

##  5 Generalization to Additional Metrics

The protocol described in this paper can be generalized to other type of
weight through the use of Full Domain Linear Isometries such as Hamming weight
(classical or large) over $\mathbb{F}_{q}$ or rank weight. We define a Full
Domain Linear Isometry (FDLI) as a set of linear isometries which has the
property that given a random element $f$ of this set, the image by $f$ of a
random word $\mathbf{x}$ of weight $w$ is a random word $\mathbf{y}$ of weight
$w$. Hereafter, we give some examples:

  * $\bullet$

Hamming weight and words over $\mathbb{F}_{2}^{n}$ (the case of this paper):
consider the set of permutations $S_{n}$ ;

  * $\bullet$

Hamming weight and words over $\mathbb{F}_{q}^{n}$: consider the set of
monomial matrices (a permutation matrix times a diagonal matrix with non null
elements of $\mathbb{F}_{q}$ on its diagonal). It can work for classical
Hamming weight but also for more recent large weight [15] ;

  * $\bullet$

Rank weight and vectors over $\mathbb{F}_{q^{m}}^{n}$: consider the function
(originally defined in [24]) which associate to a word $\mathbf{x}$ of
$\mathbb{F}_{q^{m}}^{n}$ a $m\times n$ matrix $\mathbf{X}$ by writing elements
of $\mathbb{F}_{q^{m}}$ as vectors of $\mathbb{F}_{q}^{m}$ through a basis
$\beta$ of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$. Then multiply
$\mathbf{X}$ by two random invertible matrices $\mathbf{P}$ and $\mathbf{Q}$
over $\mathbb{F}_{q}$ of respective sizes $m\times m$ and $n\times n$ such
that $\mathbf{X}\rightarrow\mathbf{PXQ}$. Finally, rewrite $\mathbf{PXQ}$ as
an element of $\mathbb{F}_{q^{m}}^{n}$ through the basis $\beta$. $\mathbf{P}$
permits to associate a support (a vector space) of weight $w$ to any other
support of weight $w$ and the matrix $\mathbf{Q}$ permits to associate words
with the same support.

When considering such FDLI functions the protocol described in this paper can
directly be adapted for a given weight, simply by changing the weight and
replacing the function $\pi$ in the protocol by a random element of a FDLI
set. The proof are straightforward and are the same than in the binary Hamming
case described in this paper; we omit them in this short version of the paper.
The notion of linearity and isometry permits to prove the correctness and the
soundness of the adapted protocol while the full domain property permits to
prove the zero-knowledge property. Interestingly enough, there was an
adaptation of the Stern protocol in [18] where the author had kept
permutations but in a rank metric context. In this case, the support of the
secret vector was not modified and led to a (unseen at that time) break of
zero-knowledge and ultimately a break of the whole protocol as described in
[24].

##  6 Conclusion

In this paper we have proposed a new optimized version of the Stern proof of
knowledge protocol, we proposed both a new protocol and a new optimization on
the handling of the seeds. Our optimized version decreases by 17.5% the length
of the associated signature compared to best know variations of the Stern
protocol. Finding such optimizations is really meaningful at a time when a
second call for proposal for post-quantum signatures has been announced by the
NIST.

## References

  * [1] Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: IEEE Information Theory Workshop (2011)
  * [2] Aguilar Melchor, C., Aragon, N., Bardet, M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Otmani, A., Ruatta, O., Tillich, J.P., Zémor, G.: ROLLO - Rank-Ouroboros, LAKE & LOCKER. NIST Post-Quantum Cryptography Standardization Project (Round 2), https://pqc-rollo.org (2020)
  * [3] Aguilar Melchor, C., Aragon, N., Barreto, P., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Ghosh, S., Gueron, S., Güneysu, T., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J.P., Vasseur, V., Zémor, G.: BIKE: Bit Flipping Key Encapsulation. NIST Post-Quantum Cryptography Standardization Project (Round 3), https://bikesuite.org (2020)
  * [4] Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Bos, J., Deneuville, J.C., Dion, A., Gaborit, P., Lacan, J., Persichetti, E., Robert, J.M., Véron, P., Zémor, G.: Hamming Quasi-Cyclic (HQC). NIST Post-Quantum Cryptography Standardization Project (Round 3), https://pqc-hqc.org (2020)
  * [5] Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Bros, M., Couvreur, A., Deneuville, J.C., Gaborit, P., Hauteville, A., Zémor, G.: Rank Quasi-Cyclic (RQC). NIST Post-Quantum Cryptography Standardization Project (Round 2), https://pqc-rqc.org (2020)
  * [6] Albrecht, M.R., Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., Patterson, K.G., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Tjhai, C.J., Tomlinson, M., Wang, W.: Classic McEliece. NIST Post-Quantum Cryptography Standardization Project (Round 3), https://classic.mceliece.org (2020)
  * [7] Aragon, N., Blazy, O., Gaborit, P., Hauteville, A., Zémor, G.: Durandal: a rank metric based signature scheme. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2019)
  * [8] Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., Santini, P.: LEDAcrypt. NIST Post-Quantum Cryptography Standardization Project (Round 2), https://ledacrypt.org (2020)
  * [9] Barenghi, A., Biasse, J.F., Persichetti, E., Santini, P.: LESS-FM: Fine-tuning Signatures from a Code-based Cryptographic Group Action. In: International Workshop on Post-Quantum Cryptography (PQCrypto) (2021)
  * [10] Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) Eurocrypt 2012. LNCS, vol. 7237, pp. 520–536. Springer (2012)
  * [11] Bellini, E., Caullery, F., Gaborit, P., Manzano, M., Mateu, V.: Improved Véron Identification and Signature Schemes in the rank metric. In: IEEE International Symposium on Information Theory (ISIT) (2019)
  * [12] Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory 24(3) (1978)
  * [13] Bettaieb, S., Bidoux, L., Blazy, O., Gaborit, P.: Zero-Knowledge Reparation of the Véron and AGS Code-based Identification Schemes. In: IEEE International Symposium on Information Theory (ISIT) (2021)
  * [14] Beullens, W.: Sigma Protocols for MQ, PKP and SIS, and Fishy Signature Schemes. International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2020)
  * [15] Bricout, R., Chailloux, A., Debris-Alazard, T., Lequesne, M.: Ternary syndrome decoding with large weight. In: International Conference on Selected Areas in Cryptography (SAC) (2019)
  * [16] Cayrel, P.L., Véron, P., El Yousfi Alaoui, S.M.: A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem. In: International Conference on Selected Areas in Cryptography (SAC) (2011)
  * [17] Chase, M., Derler, D., Goldfeder, S., Kales, D., Katz, J., Kolesnikov, V., Orlandi, C., Ramacher, S., Rechberger, C., Slamanig, D., Xiao, W., Zaverucha, G.: The Picnic Signature Algorithm. NIST Post-Quantum Cryptography Standardization Project (Round 3), https://microsoft.github.io/Picnic/ (2020)
  * [18] Chen, K.: A new identification algorithm. In: International Conference on Cryptography: Policy and Algorithms (1995)
  * [19] Chen, M.S., Hülsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: MQDSS specifications. NIST Post-Quantum Cryptography Standardization Project (Round 2), http://mqdss.org (2020)
  * [20] Courtois, N., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2001)
  * [21] Dagdelen, Ö., Galindo, D., Véron, P., Alaoui, S.M.E.Y., Cayrel, P.L.: Extended security arguments for signature schemes. Designs, Codes and Cryptography 78(2) (2016)
  * [22] Debris-Alazard, T., Sendrier, N., Tillich, J.P.: Wave: A new family of trapdoor one-way preimage sampleable functions based on codes. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2019)
  * [23] Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Advances in Cryptology (CRYPTO) (1986)
  * [24] Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the Chen identification protocol. In: International Workshop on Post-Quantum Cryptography (PQCrypto) (2011)
  * [25] Hamdaoui, Y., Sendrier, N.: A non asymptotic analysis of information set decoding. Cryptology ePrint Archive, Report 2013/162 (2013), http://eprint.iacr.org/2013/162
  * [26] Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2012)
  * [27] Kales, D., Zaverucha, G.: An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes. In: International Conference on Cryptology and Network Security (CANS) (2020)
  * [28] Lyubashevsky, V.: Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2009)
  * [29] McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Coding Thv 4244 (1978)
  * [30] Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (1996)
  * [31] Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology (1991)
  * [32] Schrek, J.: Signatures et authentications pour les cryptosystèmes basés sur les codes correcteurs en métrique de Hamming et en métrique rang. Ph.D. thesis, University of Limoges (2013)
  * [33] Sendrier, N.: Decoding one out of many. In: Yang, B.Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 51–67 (2011)
  * [34] Stern, J.: A new identification scheme based on syndrome decoding. In: Annual International Cryptology Conference (CRYPTO) (1993)
  * [35] Véron, P.: Improved identification schemes based on error-correcting codes. Applicable Algebra in Engineering, Communication and Computing (1997)