thesis/chap-GS-LWE.tex

In this chapter, we present the first dynamic group signature scheme based on lattice assumptions.
This construction relies on a signature scheme with efficient protocols as in~\cref{ch:sigmasig}, which is used in a similar manner.
As a consequence, it is possible to design lattice-based anonymous credentials from this building block.
The group signature scheme relies on the Gentry, Peikert and Vaikuntanathan identity-based encryption~\cite{GPV08} with the Canetti, Halevi and Katz~\cite{CHK04} transform to obtain a CCA2-secure public key encryption scheme which will be used to provide full-anonymity.

The group signature is proven secure in the \ROM under the \SIS and \LWE assumptions, which are fixed-size and well-studied assumptions.
As of the security parameter $\lambda$ and groups of up to $\Ngs$ members, the scheme features public key size $\softO(\lambda^2) \cdot \log \Ngs$, user's secret key size $\softO(\lambda)$ and signature size $\softO(\lambda) \cdot \log \Ngs$.
Our scheme thus achieves a level of efficiency comparable to recent proposals based on standard (i.e. non-ideal) lattices~\cite{LLLS13,NZZ15,LNW15,LLNW16} in the static setting as depicted in \cref{table:lattice-gs-comparison}.
In particular, the cost of moving to dynamic group is reasonable: while using the scheme from~\cite{LNW15} as a building block, our construction lengthens the signature size only by a (small) constant factor.

\begin{table}[t]
  \scriptsize \centering
  \begin{tabular}{|c||c|c|c|c|c|c|c|}
    \hline
   % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
    Scheme  & \cite{LLLS13} & \cite{NZZ15} &  \cite{LNW15} & \cite{LLNW16} & Ours \\
    \hline
    \rule{0pt}{3ex}
    Group PK  & $\widetilde{\mathcal{O}}(\lambda^2)\cdot \log N_\mathsf{gs}$ & $\widetilde{\mathcal{O}}(\lambda^2)$ & $\widetilde{\mathcal{O}}(\lambda^2)\cdot \log N_\mathsf{gs}$ &  $\widetilde{\mathcal{O}}(\lambda^2)$&  $\widetilde{\mathcal{O}}(\lambda^2)\cdot  \log N_\mathsf{gs}$ \\
    \hline
    \rule{0pt}{3ex}
    User's SK  & $\widetilde{\mathcal{O}}(\lambda^2)$ & $\widetilde{\mathcal{O}}(\lambda^2)$ & $\widetilde{\mathcal{O}}(\lambda)$ &$\widetilde{\mathcal{O}}(\lambda)\cdot \log N_\mathsf{gs} $ &    $\widetilde{\mathcal{O}}(\lambda)$ \\
    \hline
    \rule{0pt}{3ex}
    Signature  & $\widetilde{\mathcal{O}}(\lambda)\cdot  \log N_\mathsf{gs}$ & $\widetilde{\mathcal{O}}(\lambda + \log^2 N_\mathsf{gs})$ & $\widetilde{\mathcal{O}}(\lambda)\cdot  \log N_\mathsf{gs}$ & $\widetilde{\mathcal{O}}(\lambda)\cdot \log N_\mathsf{gs}$ &  $ \widetilde{\mathcal{O}}(\lambda)\cdot  \log N_\mathsf{gs}$ \\
    \hline
  \end{tabular}
  \caption[Comparison between recent lattice-based group signatures]{Efficiency comparison among recent lattice-based group signatures for static groups and our dynamic scheme. The evaluation is done with respect to $2$ governing parameters: security parameter $\lambda$ and the maximum expected group size $N_\mathsf{gs}$. We do not include the earlier schemes~\cite{GKV10,CNR12} that have signature size $\widetilde{\mathcal{O}}(\lambda^2)\cdot N_\mathsf{gs}$.}
  \label{table:lattice-gs-comparison}
\end{table}

The signature scheme with efficient protocols is built upon the $\SIS$-based signature of Böhl \textit{et al.}~\cite{BHJ+15}, which is itself a variant of Boyen's signature~\cite{Boy10}.
The latter scheme involves a public key containing matrices $\mathbf{A}, \mathbf{A}_0, \ldots, \mathbf{A}_\ell \in \Zq^{n \times m}$ and signs an $\ell$-bit message $\mathfrak m \in \bit^\ell$ by computing a short vector $\mathbf{v} \in \ZZ^{2m}_{}$ such that ${[\mathbf{A} \mid \mathbf{A}_0 + \sum_{j=1}^\ell \mathfrak m[j] \mathbf{A}_j ]} \cdot \mathbf{v} = \mathbf 0^n \bmod q$.
The variant proposed by Böhl \textit{et al.} only uses a constant number of matrices $\mathbf{A}, \mathbf{A}_0, \mathbf{A}_1 \in \Zq^{n \times m}$ where each signature is assigned with a single-use tag $\tau$ and the public key involves an extra matrix $\mathbf{D} \in \Zq^{n \times m}$ and a vector $\mathbf{u} \in \Zq^n$.
A message $\mathfrak m$ is then signed by first applying a chameleon hash function $\mathbf{h} = \mathcal{H}(\mathfrak m, \mathbf{s}) \in \bit^m_{}$ and signing $\mathbf{h}$ by computing a short $\mathbf{v} \in \ZZ^{2m}_{}$ such that ${[\mathbf{A} \mid \mathbf{A}_0 + \tau \mathbf{A}_1 ]} \cdot \mathbf{v} = \mathbf{u} + \mathbf{D} \cdot \mathbf{h} \bmod q$.

Our scheme extends~\cite{BHJ+15} so that an $N$-block message $(\mathfrak m_1, \ldots, \mathfrak m_N) \in (\bit^L)^N$, for some $L \in \NN$, is signed by outputting a tag $\tau \in \bit^\ell$ and a short $\mathbf{v} \in \ZZ^{2m}$ such that ${[\mathbf{A} \mid \mathbf{A}_0 + \sum_{j=1}^\ell \tau[j] \mathbf{A}_j ]} \cdot \mathbf{v} = \mathbf{u} + \mathbf{D} \cdot \mathcal{H}(\mathfrak{m}_1, \ldots, \mathfrak{m}_N, \mathbf s) \bmod q$, where the chameleon hash function computes $\mathbf{c}_M = \mathbf D_0 \cdot \mathbf s + \sum_{k=1}^{N} \mathbf D_k \cdot \mathfrak{m}_k \bmod q$, for some short vector $\mathbf s$, before re-encoding $\mathbf c_M$ so as to enable multiplication by $\mathbf D$.

In order to obtain a signature scheme that possesses efficient protocols akin to Camenish and Lysyanskaya~\cite{CL02}, our idea is to have the tag $\tau \in \bit^\ell$ play the same role as the prime exponent in Strong-RSA-based schemes~\cite{CL02a}.
To adapt this idea in the context of signatures with efficient protocols, we have to overcome several difficulties.
The first one is to map $\mathbf c_M$ back in the domain of the chameleon hash function while preserving the compatibility with ZK proofs.
To solve this issue, we extend a technique used in~\cite{LLNW16} in order to build a ``zero-knowledge-friendly'' chameleon hash function.
This function hashes the message by outputting the coordinate-wise binary decomposition $\mathbf w$ of $\mathbf D_0 \cdot \mathbf s + \sum_{k=1}^{N} \mathbf D_k \cdot \mathfrak{m}_k$. Using the ``power-of-two'' matrix $\mathbf H = \mathbf I \otimes [ 1 \mid 2 \mid \cdots \mid 2^{\lceil \log q\rceil} ]$, we can prove that $\mathbf w = \mathcal{H}(\mathfrak{m}_1, \ldots, \mathfrak{m}_N, \mathbf s)$ by demonstrating the knowledge of short vectors $(\mathfrak{m}_1, \ldots, \mathfrak{m}_N, \mathbf s, \mathbf w)$ that verifies $\mathbf H \cdot \mathbf w = \mathbf D_0 \cdot \mathbf s + \sum_{k=1}^{N} \mathbf D_k \cdot \mathfrak{m}_k \bmod q$ which can be proven using the ZKAoK of \cref{sse:stern}.

The second problem is to prove knowledge of $(\tau,\mathbf{v},\mathbf{s})$ and $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$ satisfying $[\mathbf{A} \mid \mathbf{A}_0 + \sum_{j=1}^\ell
\tau[j]  \cdot \mathbf{A}_j ] \cdot \mathbf{v} = \mathbf{u} + \mathbf{D} \cdot \mathsf{CMHash}(\mathfrak{m}_1,\ldots,\mathfrak{m}_N,\mathbf{s})$, without revealing any of the witnesses.  To
this end,  we provide a framework for  proving all the involved statement (and many other relations that naturally arise in lattice-based cryptography) as
special cases.  We  reduce the statements  to asserting that a short integer vector $\mathbf{x}$ satisfies an equation   of the form $\mathbf{P} \cdot \mathbf{x} = \mathbf{v}
\bmod q$, for some public matrix $\mathbf{P}$ and vector~$\mathbf{v}$, and belongs to a set $\mathsf{VALID}$ of short vectors with a particular structure.  While the
small-norm property of $\mathbf{x}$ is provable using standard techniques (e.g., \cite{Lyu08}), we argue its membership of $\mathsf{VALID}$ by leveraging
the   properties of Stern-like   protocols \cite{Ste96,KTX08,LNSW13}. In particular, we rely on the fact that their underlying permutations interact well with
combinatorial statements pertaining to  $\mathbf{x}$, especially $\mathbf{x}$ being a bitstring with a specific pattern.  We believe our framework to be of  independent
interest  as it provides a blueprint for proving many other intricate relations in a modular manner.

When we extend the scheme with a protocol for signing committed messages, we need the signer to  re-randomize the user's commitment before signing the hidden
messages. This is indeed necessary to provide the reduction with a backdoor allowing to correctly answer the $i^\dagger$-th  query by ``programming'' the
randomness  of the commitment.  Since we work with integers vectors, a straightforward simulation incurs a non-negligible statistical distance between the
simulated distributions of  re-randomization  coins and the real one (which both have a discrete Gaussian distribution).   Camenisch and Lysyanskaya \cite{CL02}
address a  similar problem by choosing the signer's randomness to be  exponentially larger than that of the user's commitment so as to statistically ``drown''
the aforementioned discrepancy.  Here,  the same idea would  require to work with an exponentially large  modulus~$q$. Instead, we adopt a more efficient
solution, inspired by  Bai \textit{et al.} \cite{BLL+15}, which  is to apply an analysis based on the R\'enyi divergence rather than the statistical distance. In
short,  the R\'enyi divergence's properties tell us that, if some event~$E$ occurs with noticeable probability in some probability space~$P$, so does it in a
different probability space~$Q$ for which the second order divergence $R_2(P||Q)$ is sufficiently small. In our setting, $R_2(P||Q)$ is precisely polynomially
bounded since the two probability spaces only diverge in one signing query.

Our dynamic group signature scheme avoids these difficulties because  the group manager only signs known messages: instead of signing the user's secret key as
in anonymous credentials, it creates a membership certificate by signing the user's public key.  Our zero-knowledge arguments accommodate the requirements of
the scheme in the following way.  In the joining protocol that dynamically introduces new group members, the  user $i$ chooses a membership secret consisting of
a short discrete Gaussian vector $\mathbf{z}_i  $.  This user generates a public syndrome $\mathbf{v}_i = \mathbf{F} \cdot \mathbf{z}_i \mod q$, for some public matrix
$\mathbf{F}$,  which constitutes his public key. In order to certify  $\mathbf{v}_i$, the group manager computes the coordinate-wise binary expansion
$\mathsf{bin}(\mathbf{v}_i) $ of $\mathbf{v}_i$. The vector $\mathsf{bin}(\mathbf{v}_i) $ is then signed using our  signature scheme.  Using the resulting signature
$(\tau,\mathbf{v},\mathbf{s}) $ as a membership certificate, the group member is able to sign a message by proving that: (i) He holds a valid signature
$(\tau,\mathbf{v},\mathbf{s})$ on some secret binary message $\mathsf{bin}(\mathbf{v}_i) $; (ii) The latter vector  $\mathsf{bin}(\mathbf{v}_i) $ is  the binary expansion of
some syndrome $\mathbf{v}_i$ of which he knows a GPV pre-image $\mathbf{z}_i $. We remark that condition (ii)  can be proved by providing evidence that we have $
\mathbf{v}_i = \mathbf{H} \cdot \textsf{bin}(\mathbf{v}_i)    = \mathbf{F} \cdot \mathbf{z}_i \bmod q$, for some short integer vector $\mathbf{z}_i $ and some binary $\mathsf{bin}(\mathbf{v}_i) $,
where $\mathbf{H}$ is the ``powers-of-$2$'' matrix.  Our  abstraction of Stern-like protocols \cite{Ste96,KTX08,LNSW13} allows us to efficiently argue such
statements.  The fact that the underlying chameleon hash function smoothly interacts with Stern-like zero-knowledge arguments is  the property that maintains
the user's capability of efficiently proving knowledge of the underlying secret key.


Given the state of $\NIZK$ proofs in the lattice setting, it seems hard to provide group signature schemes in the standard model.


In the forthcoming sections, we first provide the description of our signature with efficient protocols; then a description of our dynamic group signature will be given and finally, we will explain how to use the Stern abstraction of \cref{sse:stern} to provide the required zero-knowledge arguments.

\section{A Lattice-Based Signature  with Efficient Protocols} \label{se:gs-lwe-sigep}

Our scheme can be seen as a variant of the B\"ohl \textit{et al.} signature \cite{BHJ+15}, where
each signature is a triple $(\tau,\mathbf{v},\mathbf{s})$, made of a tag $\tau \in \{0,1\}^\ell$ and   integer vectors $(\mathbf{v},\mathbf{s})$ satisfying
 $[\mathbf{A} \mid \mathbf{A}_0 + \sum_{j=1}^\ell  \tau[j]  \cdot \mathbf{A}_j ] \cdot \mathbf{v} = \mathbf{u} + \mathbf{D} \cdot \mathbf{h} \bmod q$,
 where matrices $\mathbf{A}, \mathbf{A}_0, \ldots, \mathbf{A}_\ell, \mathbf{D} \in \Zq^{n \times m}$
are public random matrices and $\mathbf{h} \in \{0,1\}^m$ is a chameleon hash of the message which is computed using randomness $\mathbf{s}$.
A difference is that, while \cite{BHJ+15} uses a short single-use tag $\tau \in \Zq$,
we need the tag to be an $\ell$-bit string $\tau \in \{0,1\}^{\ell}$ which will assume the same role as the prime exponent of Camenisch-Lysyanskaya signatures
\cite{CL02a} in the security proof.

We show that a suitable chameleon hash function makes the scheme compatible with Stern-like zero-knowledge arguments \cite{LNSW13,LNW15} for arguing possession of a valid message-signature pair. \cref{sse:stern} shows how to translate such a statement into asserting that a short  witness vector $\mathbf{x}$ with a particular structure satisfies
 a relation of the form
$\mathbf{P} \cdot \mathbf{x} = \mathbf{v} \bmod q$, for some public matrix $\mathbf{P}$ and vector~$\mathbf{v}$.
The underlying chameleon hash can be seen as a composition of the chameleon hash of \cite[Se. 4.1]{CHKP10} with
a technique used in \cite{PSTY13,LLNW16}: on input of a message $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$, it outputs the binary decomposition of
$\mathbf{D}_0 \cdot \mathbf{s} + \sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k$,  for some discrete Gaussian vector $\mathbf{s}$.

\subsection{Description} \label{desc-sig-protoc}

 We assume that   messages are  vectors of $N$ blocks $\mathsf{Msg}=(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$, where  each
block is a $2m$-bit string $\mathfrak{m}_k = \mathfrak{m}_k[1] \ldots \mathfrak{m}_k[2m] \in \{0,1\}^{2m}$ for $k \in \{1,\ldots, N\}$.

For each vector $\mathbf{v} \in \Zq^L$, we denote by $\textsf{bin}(\mathbf{v}) \in \{0,1\}^{L \lceil \log q \rceil}$ the vector obtained by replacing each
coordinate of $\mathbf{v}$ by its binary representation.



\begin{description}
  \item[\textsf{Keygen}$(1^\lambda,1^N)$:] Given a security parameter $\lambda>0$  and the   number of  blocks $N = \mathsf{poly}(\lambda)$, choose the following parameters: $n = \bigO(\lambda)$; a prime modulus $q = \widetilde{\bigO}(N\cdot n^{4})$; dimension  $m =2n \lceil \log q \rceil $; an integer $\ell = \Theta(\lambda)$; and  Gaussian parameters $\sigma = \Omega(\sqrt{n\log q}\log n)$,  $\sigma_0 = 2\sqrt{2}(N+1) \sigma m^{3/2}$, and $\sigma_1 = \sqrt{\sigma_0^2 + \sigma^2}$. Define the message space as $(\{0,1\}^{2m})^N$.
    \smallskip   
    \begin{itemize}
      \item[1.] Run $\TrapGen(1^n,1^m,q)$ to get~$\mathbf{A} \in
        \Zq^{n \times m}$ and a short basis $\mathbf{T}_{\mathbf{A}}$ of
        $\Lambda_q^{\perp}(\mathbf{A}).$  This basis allows computing short vectors in $\Lambda_q^{\perp}(\mathbf{A})$ with a Gaussian parameter $\sigma$.
        Next, choose $\ell+1$ random   $\mathbf{A}_0,\mathbf{A}_1,\ldots,\mathbf{A}_{\ell} \sample \U(\Zq^{n \times m})$. %, where $\ell = \Theta(\lambda)$.
      \item[2.]  Choose  random matrices $\mathbf{D} \sample \U(\Zq^{n \times m})$, $\mathbf{D}_0,\mathbf{D}_1,\ldots,\mathbf{D}_{N} \sample \U(\Zq^{2n \times 2m})$ as well as a random     vector
        $\mathbf{u} \sample \U(\Zq^n)$. \smallskip
    \end{itemize}
    The  private key consists of $SK \coloneqq \mathbf{T}_{\mathbf{A}} \in \ZZ^{m \times m}$ and the public key is
    $${PK}\coloneqq \big( \mathbf{A}, ~ \{\mathbf{A}_j \}_{j=0}^{\ell},  ~ \{\mathbf{D}_k\}_{k=0}^{N},~\mathbf{D}, ~\mathbf{u} \big).$$
  % \smallskip
  \item[\textsf{Sign}$\big(SK, \mathsf{Msg} \big)$:] To sign an $N$-block message
    $\mathsf{Msg}=\left(\mathfrak{m}_1,\ldots,\mathfrak{m}_N \right) \in \left(\{0,1\}^{2m} \right)^N$,    
    \begin{enumerate}[1.]
      \item Choose a   random  string $\tau \sample \U(\{0,1\}^\ell )$. Then, using  $SK\coloneqq 
        \mathbf{T}_{\mathbf{A}}$, compute with $\ExtBasis$ a short delegated basis $\mathbf{T}_\tau  \in \ZZ^{2m \times 2m}$
        for the matrix
        \begin{eqnarray} \label{tau-matrix}
          \mathbf{A}_{\tau}=
          [ \mathbf{A} \mid  \mathbf{A}_0 +
            \sum_{j=1}^\ell \tau[j] \mathbf{A}_j
          ] \in  \Zq^{ n  \times 2m}.
        \end{eqnarray}
      \item Sample a     vector $\mathbf{s} \sample D_{\ZZ^{2m},\sigma_1 }$. Compute   $\mathbf{c}_M \in \Zq^{2n}$ as a chameleon hash of $\left(\mathfrak{m}_1,\ldots,\mathfrak{m}_N \right)$: i.e., compute
         $\mathbf{c}_M =       \mathbf{D}_{0} \cdot \mathbf{s}   + \sum_{k=1}^N   \mathbf{D}_k \cdot \mathfrak{m}_k \in \mathbb{Z}_q^{2n} ,$ 
        which is used to define  $\mathbf{u}_M=\mathbf{u} + \mathbf{D} \cdot \textsf{bin}( \mathbf{c}_M) \in \Zq^n .$
        Then,
        using the delegated basis $\mathbf{T}_\tau \in \ZZ^{2m \times 2m}$, sample  a short vector $\mathbf{v} \in \ZZ^{2m}$ in $D_{\Lambda_q^{\mathbf{u}_M}(\mathbf{A}_\tau), \sigma}$.
    \end{enumerate}
    Output the signature $sig=(\tau,\mathbf{v},\mathbf{s}) \in \{0,1\}^\ell \times  \ZZ^{2m} \times \ZZ^{2m}$. \smallskip
  \item[\textsf{Verify}$\big(PK,\mathsf{Msg},sig\big)$:] Given  $PK$, a message $\mathsf{Msg}=(\mathfrak{m}_1,\ldots,\mathfrak{m}_N) \in (\{0,1\}^{2m})^N$ and a purported
    signature $sig=(\tau,\mathbf{v},\mathbf{s}) \in \{0,1\}^\ell \times  \ZZ^{2m} \times \ZZ^{2m}$,
    return $1$ if
    \begin{eqnarray} \label{ver-eq-block}
      \mathbf{A}_{\tau} \cdot \mathbf{v} &=& \mathbf{u} +  \mathbf{D} \cdot \textsf{bin}(  \mathbf{D}_0 \cdot \mathbf{s} + \sum_{k=1}^N     \mathbf{D}_k \cdot \mathfrak{m}_k ) \bmod q.
    \end{eqnarray}
    and $\| \mathbf{v} \| < \sigma \sqrt{2m}$, $\| \mathbf{s} \| <  \sigma_1 \sqrt{2m}$.
\end{description}
When the scheme is used for obliviously signing committed messages,
the security proof follows Bai \textit{et al.} \cite{BLL+15} in that it applies an argument based on the R\'enyi divergence  in   one signing query. This argument requires
 to sample $\mathbf{s}$ from a Gaussian distribution whose  standard deviation $\sigma_1$ is polynomially larger than $\sigma$.

We note that, instead of being included in the public key, the matrices $ \{\mathbf{D}_k\}_{k=0}^{N}$ can be part of common public parameters shared by many signers. Indeed,
 only the matrices $(\mathbf{A},\{\mathbf{A}_i\}_{i=0}^\ell)$ should be specific to the user who holds the secret key $SK=\mathbf{T}_{\mathbf{A}}$. In Section \ref{commit-sig}, we use a variant where  $ \{\mathbf{D}_k\}_{k=0}^{N}$
belong to public parameters.


\subsection{Security Analysis}
The security analysis in Theorem  \ref{th:gs-lwe-security-cma-sig} requires that   $q>\ell$.


\begin{theorem} \label{th:gs-lwe-security-cma-sig}
The signature scheme is secure under chosen-message attacks under the $\SIS$ assumption.
\end{theorem}

\begin{proof}
To prove the result, we will distinguish three kinds of attacks:
\begin{description}
\item[Type I attacks]  are attacks where, in the adversary's forgery $sig^\star=(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star)$, $\tau^\star$ did not appear in any output
of the signing oracle.
\item[Type II attacks]  are such that, in the adversary's forgery $sig^\star=(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star)$, $\tau^\star$ is recycled from an output
 $sig^{(i^\star)}=(\tau^{(i^\star)},\mathbf{v}^{(i^\star)},\mathbf{s}^{(i^\star)})$ of the signing oracle, for some index $i^\star \in \{1,\ldots,Q\}$. However,
if $\mathsf{Msg}^\star=(\mathfrak{m}_1^\star,\ldots,\mathfrak{m}_N^\star)$ and $\mathsf{Msg}^{(i^\star)}=(\mathfrak{m}_1^{(i^\star)},\ldots,\mathfrak{m}_N^{(i^\star)})$ denote the forgery
message and the $i^\star$-th signing query, respectively, we have
$\mathbf{D}_0 \cdot \mathbf{s}^\star + \sum_{k=1}^N \mathbf{D}_k   \cdot \mathfrak{m}_k^\star \neq  \mathbf{D}_0 \cdot \mathbf{s}^{(i^\star)} + \sum_{k=1}^N \mathbf{D}_k  \cdot \mathfrak{m}_k^{(i^\star)}. $
\item[Type III attacks]  are those where the adversary's forgery $sig^\star=(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star)$ recycles $\tau^\star $ from an output
 $sig^{(i^\star)}=(\tau^{(i^\star)},\mathbf{v}^{(i^\star)},\mathbf{s}^{(i^\star)})$ of the signing oracle (i.e.,
$\tau^{(i^\star)}= \tau^\star$  for some index $i^\star \in \{1,\ldots,Q\}$) and  we have the collision
\begin{eqnarray} \label{collision}
\mathbf{D}_0 \cdot \mathbf{s}^\star + \sum_{k=1}^N \mathbf{D}_k   \cdot \mathfrak{m}_k^\star =  \mathbf{D}_0 \cdot \mathbf{s}^{(i^\star)} + \sum_{k=1}^N \mathbf{D}_k  \cdot \mathfrak{m}_k^{(i^\star)}.
\end{eqnarray}
\end{description}
Type III attacks   imply a collision for the  chameleon hash function of Kawachi \textit{et al.} \cite{KTX08}: if (\ref{collision}) holds,
  a short vector
of $\Lambda_q^{\perp}([ \mathbf{D}_0 \mid \mathbf{D}_1 \mid \ldots \mid \mathbf{D}_N])$ is obtained as
  $$\big({\mathbf{s}^\star}^T- {\mathbf{s}^{(i^\star)}}^T \mid {\mathfrak{m}_1^\star }^T - {\mathfrak{m}_1^{(i^\star)} }^T \mid \ldots \mid {\mathfrak{m}_N^\star }^T - {\mathfrak{m}_N^{(i^\star)} }^T \big)^T,$$   so that a collision breaks  the $\mathsf{SIS}$ assumption.

The security against Type I attacks is proved by \cref{le:lwe-gs-type-I-attacks} which applies the same technique  as in \cite{Boy10,MP12}. In particular, the prefix guessing technique
of \cite{HW09} allows keeping the modulus smaller than the number $Q$ of adversarial queries as in \cite{MP12}.
 In order to deal with Type II attacks, we can leverage the technique of~\cite{BHJ+15}. In \cref{le:lwe-gs-type-II-attacks}, we prove that Type II attack would also contradict   $\mathsf{SIS}$.
\end{proof}

\begin{lemma} \label{le:lwe-gs-type-I-attacks}
The scheme is secure against Type I attacks if the $\mathsf{SIS}_{n,m,q,\beta'}$ assumption holds for $\beta' = m^{3/2} \sigma^2 ( \ell+3) + m^{1/2} \sigma_1 $
\end{lemma}

\begin{proof}
 Let $\adv$ be a $\ppt$ adversary that can mount a Type I attack with non-negligible success probability $\varepsilon$. We construct a $\ppt$
   algorithm $\bdv$ that uses $\adv$ to break the~$\SIS_{n,m,q,\beta'}$ assumption.  It takes as input~$\bar{\mathbf{A}} \in
   \Zq^{n \times m}$ and computes  $\mathbf{v} \in
   \Lambda_q^{\perp}(\bar{\mathbf{A}})$ with~$0 < \|\mathbf{v}\| \leq \beta'$.

		Algorithm~$\bdv$ first chooses the $\ell$-bit strings $\tau^{(1)},\ldots,\tau^{(Q)} \sample \U(\{0,1\}^\ell)$ to be used in signing queries. As in \cite{HW09}, it
		guesses the shortest prefix such that the string $\tau^\star$ contained in $\adv$'s forgery differs from all prefixes of  $\tau^{(1)},\ldots,\tau^{(Q)}$. To this
		end, $\bdv$ chooses $i^\dagger \sample \U(\{1,\ldots, Q\})$ and $t^\dagger \sample \U(\{1,\ldots,\ell\})$ so that, with probability $1/(Q \cdot \ell)$, the longest
		common prefix between $\tau^\star$ and one of the $\left\{\tau^{(i)} \right\}_{i=1}^Q$ is the string
		$\tau^\star[1] \ldots \tau^\star[t^\dagger-1] =\tau^{(i^\dagger)}[1] \ldots \tau^{(i^\dagger)}[t^\dagger-1]  \in \{0,1\}^{t^\dagger -1}$ comprised of the
		first $(t^\dagger-1)$-th bits of $\tau^\star \in \{0,1\}^\ell$. We define $ \tau^\dagger \in \{0,1\}^{t^\dagger}$ as the $t^\dagger$-bit string  $\tau^\dagger=\tau^\star[1] \ldots \tau^\star[t^\dagger] $. By construction, with probability $1/(Q \cdot \ell)$, we have $\tau^\dagger \not \in \left\{\tau^{(1)}_{|{t^\dagger}}, \ldots ,\tau^{(Q)}_{|{t^\dagger}} \right\}$, where $\tau^{(i)}_{|{t^\dagger}}$ denotes
		the $t^\dagger$-th prefix of $\tau^{(i)}$ for each $i\in \{1,\ldots,Q\}$.

				Then, $\bdv$  runs
   $\TrapGen(1^n,1^m,q)$ to obtain $\mathbf{C} \in \Zq^{n \times m}$ and a
   basis $\mathbf{T}_{\mathbf{C}}$ of~$\Lambda_q^{\perp}(\mathbf{C})$ with
   $\|\widetilde{\mathbf{T}_{\mathbf{C}}}\| \leq \bigO(\sqrt{n \log q})$. Then,
   it picks~$\ell+1$ matrices~$\mathbf{Q}_0,\ldots, \mathbf{Q}_{\ell} \in \ZZ^{m \times m}$, where
   each matrix $\mathbf{Q}_i$ has its columns  sampled independently from~$D_{\ZZ^m, \sigma}$.   The
   reduction $\bdv$ defines the matrices $\{ \mathbf{A}_j\}_{j=0}^{\ell}$ as
 \begin{eqnarray*}
 \left\{
 \begin{array}{ll}
  \mathbf{A}_0 =  \bar{\mathbf{A}} \cdot \mathbf{Q}_0 +  (\sum_{j=1}^{t^\dagger} {\tau^\star[j]}) \cdot
   \mathbf{C} \\
 \mathbf{A}_j =  \bar{\mathbf{A}} \cdot \mathbf{Q}_j  + (-1)^{\tau^\star[j]} \cdot
   \mathbf{C}, \qquad \quad \text{ for  }  j \in
   [1,t^\dagger] \\
	\mathbf{A}_j =  \bar{\mathbf{A}} \cdot \mathbf{Q}_j , \qquad \quad \qquad \quad~~ \qquad \quad \text{ for  }  j \in
   [t^\dagger+1,\ell]
 \end{array}
  \right.
 \end{eqnarray*}
 It also sets $\mathbf{A}=\bar{\mathbf{A}}$.
  We note that  we have
 \begin{eqnarray*}
   \mathbf{A}_{\tau^{(i)}} &=& \left[ \begin{array}{c|c} \bar{\mathbf{A}}  &   \mathbf{A}_0 +
 \sum_{j=1}^\ell   \tau^{(i)}[j] \mathbf{A}_j
 \end{array} \right] \\
 & = & \left[
\begin{array}{c|c}
	 \bar{\mathbf{A}} ~ & ~  \bar{\mathbf{A}} \cdot (\mathbf{Q}_0 +
   \sum_{j=1}^{\ell}  \tau^{(i)}[j] \mathbf{Q}_j) + (
   \sum_{j=1}^{t^\dagger}  \tau^\star[j]  +(-1)^{\tau^\star[j]}  \tau^{(i)}[j])\cdot  \mathbf{C}
\end{array} \right]
\\
 &=&
\left[
\begin{array}{c|c}
 \bar{\mathbf{A}} ~ & ~ \bar{\mathbf{A}} \cdot  (\mathbf{Q}_0 +
   \sum_{j=1}^{\ell} \tau^{(i)}[j] \mathbf{Q}_j) +  h_{\tau^{(i)}} \cdot \mathbf{C}
 \end{array} \right]
 \end{eqnarray*}
 where $  h_{\tau^{(i)}} \in [1,t^\dagger] \subset [1,\ell]$ stands for the Hamming distance between
 $\tau^{(i)}_{|t^\dagger}$ and $\tau^\star_{|t^\dagger}$. Note that, with probability $1/(Q \cdot \ell)$ and since $q>\ell$, we have
 $  h_{\tau^{(i)}} \neq 0 \bmod q$ whenever $\tau^{(i)}_{|t^\dagger} \neq \tau^\star_{|t^\dagger}$.

 Next, $\bdv$ chooses the matrices $\mathbf{D}_k \sample \U(\Zq^{2n  \times 2m})$ uniformly at random for each $k \in [0,N]$. Then, it picks a random short matrix $\mathbf{R}  \in \ZZ^{m \times m}$ which  has its columns independently sampled from $D_{\ZZ^m,\sigma}$
 and computes
\begin{eqnarray*}
\mathbf{D} &=&   \bar{\mathbf{A}} \cdot \mathbf{R}. % \qquad \qquad \qquad \quad~ \forall k \in \{0,\ldots,N\}.
\end{eqnarray*}
Finally, $\bdv$ samples a short vector $\mathbf{e}_u \sample D_{\ZZ^m,\sigma_1}$  and computes the vector   $\mathbf{u} \in \Zq^n$
as    $\mathbf{u} =      \bar{\mathbf{A}} \cdot \mathbf{e}_u  \in \Zq^n$. The public key  $${PK}\coloneqq \big( \mathbf{A}, ~
  \{\mathbf{A}_j \}_{j=0}^{\ell},  ~ \{\mathbf{D}_k\}_{k=0}^{N},~\mathbf{D}, ~\mathbf{u} \big)$$
is given to $\adv$.

At the $i$-th signing query $\mathsf{Msg}^{(i)}=(\mathfrak{m}_1^{(i)},\ldots,\mathfrak{m}_N^{(i)}) \in (\{0,1\}^{2m})^N$,  $\bdv$ can use the trapdoor $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$ to generate a signature.
To do this, $\bdv$ first samples    $\mathbf{s}^{(i)} \sample D_{\ZZ^{2m},\sigma_1}$ and computes a vector $\mathbf{u}_M \in \Zq^m$ as
 $$\mathbf{u}_M  = \mathbf{u}  +  \mathbf{D} \cdot \bit \bigl( \sum_{k=1}^N    \mathbf{D}_k  \cdot {\mathfrak{m}_k^{(i)} }  +   \mathbf{D}_{0} \cdot {\mathbf{s}^{(i)} } \bigr)    ~~  \bmod q.$$
 Using $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$, $\bdv$ can then sample  a short vector $\mathbf{v}^{(i)} \in \ZZ^{2m}$ in $D^{\mathbf{u}_M}_{\Lambda^{\perp}(\mathbf{A}_{\tau^{(i)}}), \sigma}$ such
that $\big(\tau^{(i)},\mathbf{v}^{(i)},\mathbf{s}^{(i)} \big)$ satisfies the verification equation (\ref{ver-eq-block}).

When $\adv$ halts, it outputs a valid signature $sig^\star=\big(\tau^{(i^\dagger)},\mathbf{v}^\star,\mathbf{s}^\star \big)$ on a
message $\mathsf{Msg}^\star=(\mathfrak{m}_1^\star,\ldots,\mathfrak{m}_N^\star)$ with $\| \mathbf{v}^\star \| \leq \sigma \sqrt{2m}$ and $\| \mathbf{s}^\star \| \leq \sigma_1 \sqrt{2m}$.
At this point, $\bdv$ aborts and declares failure if it was unfortunate in its choice of $i^\dagger \in \{1,\ldots,Q\}$ and $t^\dagger \in \{1,\ldots,\ell\}$. Otherwise,
with probability $1/(Q \cdot \ell)$, $\bdv$ correctly guessed $i^\dagger \in \{1,\ldots,Q\}$ and $t^\dagger \in \{1,\ldots,\ell\}$, in which case it can solve the given $\mathsf{SIS}$ instance as follows.

If we parse $\mathbf{v}^\star \in \ZZ^{2m}$ as $({\mathbf{v}_1^\star }^T \mid {\mathbf{v}_2^\star }^T )^T$ with $\mathbf{v}_1^\star,\mathbf{v}_2^\star \in \ZZ^m$, we have the equality
 \begin{align*}
   &\left[ \begin{array}{c|c} \bar{\mathbf{A}} ~&~  \bar{\mathbf{A}}    \cdot  (\mathbf{Q}_0 +
       \sum_{j=1}^{\ell}  \tau^\star[j] \mathbf{Q}_j)
   \end{array} \right] \cdot 
   \left[\begin{array}{c} {\mathbf{v}_1^\star } \\ \hline {\mathbf{v}_2^\star } \end{array} \right] \\
   & \hspace{3cm}=   \mathbf{u} +  \mathbf{D} \cdot \bit \bigl( \mathbf{D}_0 \cdot {\mathbf{s}^{\star} } +
   \sum_{k=1}^N \mathbf{D}_k \cdot  {\mathfrak{m}_k^{\star} } \bigr) \bmod q \\
   & \hspace{3cm}=  \bar{\mathbf{A}} \cdot \Bigl( \mathbf{e}_u +    \mathbf{R}  \cdot \bit \bigl( \mathbf{D}_0 \cdot {\mathbf{s}^{\star} } +
   \sum_{k=1}^N \mathbf{D}_k \cdot  {\mathfrak{m}_k^{\star} } \bigr)  \Bigr)   \bmod q ,
 \end{align*}
which implies that the vector
\begin{eqnarray*}
\mathbf{w}  &=& {\mathbf{v}_1^\star }  +        (\mathbf{Q}_0 +
   \sum_{j=1}^{\ell}  \tau^\star[j] \mathbf{Q}_j) \cdot {\mathbf{v}_2^\star } - \mathbf{e}_u -     \mathbf{R}  \cdot \bit \bigl( \mathbf{D}_0 \cdot {\mathbf{s}^{\star} } +
  \sum_{k=1}^N \mathbf{D}_k \cdot  {\mathfrak{m}_k^{\star} } \bigr)  \in \ZZ^m
\end{eqnarray*}
is in $\Lambda_q^{\perp}(\bar{\mathbf{A}})$. Moreover, with overwhelming probability, this vector is non-zero since, in $\adv$'s view, the distribution of
 $\mathbf{e}_u \in \ZZ^m$ is $D_{\Lambda_q^{\mathbf{u}}(\bar{\mathbf{A}}),\sigma_1}$, which ensures that $\mathbf{e}_u$ is  statistically hidden by
the syndrome $\mathbf{u}  =   \bar{\mathbf{A}}  \cdot  \mathbf{e}_u $. Finally, the norm of $\mathbf{w}$ is smaller than
$\beta' = m^{3/2} \sigma^2 ( \ell+3) + m^{1/2} \sigma_1 $
 which yields a valid solution of the given $\mathsf{SIS}_{n,m,q,\beta'}$ instance
 with overwhelming probability.
\end{proof}

\begin{lemma} \label{le:lwe-gs-type-II-attacks}
The scheme is secure against Type II attacks if the $\mathsf{SIS}_{n,m,q,\beta''}$ assumption holds for $\beta'' = \sqrt{2}   (\ell+2)   \sigma^2  m^{3/2} + m^{1/2} $.
\end{lemma}

\begin{proof}
We prove the result using a sequence of games. For each $i$, we denote by $W_i$ the event that the adversary wins by outputting a Type II forgery in \textsf{Game}   $i$.
\medskip

\begin{description}
  \item[\textsf{Game} 0:] This is the real game where, at the $i$-th signing query $\mathsf{Msg}^{(i)}=(\mathfrak{m}_1^{(i)},\ldots,\mathfrak{m}_N^{(i)})$,
    the adversary obtains a signature $sig^{(i)}=(\tau^{(i)},\mathbf{v}^{(i)},\mathbf{s}^{(i)})$ for each $i \in \{1,\ldots,Q\}$ from the signing oracle. At the end of the game, the adversary
    outputs a forgery  $sig^\star=(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star)$ on a message $\mathsf{Msg}^{\star}=(\mathfrak{m}_1^{\star},\ldots,\mathfrak{m}_N^{\star})$.
    By hypothesis, the adversary's advantage is $\varepsilon = \Pr[W_0]$. We assume without loss of generality that the random $\ell$-bit strings $\tau^{(1)}, \ldots, \tau^{(Q)}$ are chosen
    at the very beginning of the game.
    Since $(\mathsf{Msg}^\star,sig^\star)$ is a Type II forgery, there exists an index $i^\star \in \{1,\ldots,Q\}$ such that $\tau^\star =\tau^{(i^\star)} $.

  \item[\textsf{Game} 1:] This game is identical to \textsf{Game} $0$ with the difference that the reduction aborts the experiment in the unlikely event that, in the adversary's forgery
    $sig^\star=(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star)$, $\tau^\star$ coincides with more than one of the random $\ell$-bit strings $\tau^{(1)}, \ldots, \tau^{(Q)}$
    used by the challenger. If we call $F_1$ the latter event, we have $\Pr[F_1]  < Q^2/2^\ell$ since we are guaranteed to have $\neg F_1$ as long as no two $\tau^{(i)}$, $\tau^{(i')}$ collide.
    Given that  \textsf{Game} $1$ is identical to \textsf{Game} $0$ until $F_1$ occurs, we have $|\Pr[W_1]-\Pr[W_0]| \leq \Pr[F_1] < Q^2/2^\ell$.

  \item[\textsf{Game} 2:] This game is like  \textsf{Game} $1$ with the following difference. At the outset of the game, the challenger $\bdv$ chooses a random index
    $i^\dagger \sample (\{1,\ldots,Q\})$ as a guess that $\adv$'s forgery will  recycle the $\ell$-bit string $\tau^{(i^\dagger)} \in \{0,1\}^\ell$ of the $i^\dagger$-th signing query.
    When $\adv$ outputs its Type II forgery  $sig^\star=(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star)$,  the challenger aborts
    in the event that   $\tau^{(i^\dagger)} \neq \tau^\star$ (i.e., $i^\dagger \neq i^\star$). Since the choice of $i^\dagger $ in $\{1,\ldots,Q\}$  is  independent of $\adv$'s view, we
    have $\Pr[W_2]=\Pr[W_1]/Q$.

  \item[\textsf{Game} 3:] In this game, we modify the key generation phase and the way to answer signing queries.
    First, the challenger $\bdv$ randomly picks $h_0,h_1,\ldots,h_\ell \in \Zq$ subject to the constraints
    \begin{eqnarray*}
      h_0 + \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot h_j &=& 0 \bmod q  \\
      h_0 + \sum_{j=1}^\ell \tau^{(i)}[j] \cdot h_j & \neq & 0 \bmod q   \qquad \qquad i \in \{1,\ldots,Q\} \setminus \{i^\dagger\}
    \end{eqnarray*}
    It   runs $(\mathbf{C},\mathbf{T}_{\mathbf{C}}) \leftarrow \mathsf{TrapGen}(1^n,1^m,q)$,
    $(\mathbf{D}_0,\mathbf{T}_{\mathbf{D}_0}) \leftarrow \mathsf{TrapGen}(1^{2n},1^{2m},q)$ so as to obtain  statistically random matrices $\mathbf{C} \in \Zq^{n \times m} $, $\mathbf{D}_0 \in \Zq^{2n \times 2m}$ with
    trapdoors $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$,  $\mathbf{T}_{\mathbf{D}_0}  \in \ZZ^{2m \times 2m}$ consisting of  short bases of $\Lambda_q^{\perp}(\mathbf{C})$ and $\Lambda_q^{\perp}(\mathbf{D}_0)$, respectively. Then,
    $\bdv$
    chooses
    a uniformly random  $\mathbf{D} \sample (\Zq^{n \times m})$ and re-randomizes it using short matrices
    $\mathbf{S},\mathbf{S}_0,\mathbf{S}_1,\ldots,\mathbf{S}_{\ell} \sample \ZZ^{m \times m}$, which are obtained
    by sampling their columns from the distribution $D_{\ZZ^m,\sigma}$. Namely, from  $\mathbf{D}  \in \Zq^{n \times m}$, $\bdv$
    defines
    \begin{eqnarray} \nonumber
      \mathbf{A} &=&  \mathbf{D} \cdot \mathbf{S} \\ \label{setup-sig3}
      \mathbf{A}_0 &=&  \mathbf{D} \cdot \mathbf{S}_0 + h_0 \cdot \mathbf{C} \\ \nonumber
      \mathbf{A}_j &=&  \mathbf{D} \cdot \mathbf{S}_j + h_j \cdot \mathbf{C} \qquad \qquad \forall j \in \{1,\ldots,\ell\} %\\ \nonumber
    \end{eqnarray}
    In addition, $\bdv$ picks random matrices $\mathbf{D}_1,\ldots,\mathbf{D}_N \sample (\Zq^{2n \times 2m})$ and a random vector $\mathbf{c}_M \sample (\Zq^{2n})$. It samples
    short vectors $\mathbf{v}_1 ,\mathbf{v}_2 \sample D_{\ZZ^m,\sigma}$ and computes $\mathbf{u} \in \Zq^n$
    as    $\mathbf{u}  =     \mathbf{A}_{\tau^{(i^\dagger)}} \cdot
    \left[
      \begin{array}{c}
        \mathbf{v}_1 \\ \hline \mathbf{v}_2
    \end{array} \right]
    -  \mathbf{D}  \cdot \textsf{bin}( \mathbf{c}_M )  \bmod q$, where
    \begin{eqnarray*}
      \mathbf{A}_{\tau^{(i^\dagger)}} &=&  \left[
        \begin{array}{c|c}   \mathbf{A} ~ & ~ \mathbf{A}_0 +
          \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{A}_j
      \end{array} \right]    \\ &=&     \left[
        \begin{array}{c|c}    \mathbf{D} \cdot \mathbf{S} ~  & ~  \mathbf{D}\cdot (\mathbf{S}_0 +
          \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{S}_j)
      \end{array} \right]  .
    \end{eqnarray*}
    The adversary's signing queries are then answered as follows.
    \begin{itemize}
      \item At the $i$-th signing query $ (\mathfrak{m}_1^{(i)},\ldots,\mathfrak{m}_N^{(i)})$, whenever $i \neq i^\dagger$, we have
        \begin{eqnarray*}
          \mathbf{A}_{\tau^{(i)}} &=&  \left[
            \begin{array}{c|c} \mathbf{A} ~& ~    \mathbf{A}_0 +
              \sum_{j=1}^\ell \tau^{(i)}[j] \cdot \mathbf{A}_j
          \end{array} \right]  \\
          &=&   \left[
            \begin{array}{c|c}  \mathbf{A} ~ &    ~   \mathbf{D} \cdot (\mathbf{S}_0 +
              \sum_{j=1}^\ell \tau^{(i)}[j] \cdot \mathbf{S}_j) + h_{\tau^{(i)}} \cdot \mathbf{C}
          \end{array} \right]
          \in  \Zq^{ n  \times 2m},
        \end{eqnarray*}
        with $h_{\tau^{(i)}} = h_0 + \sum_{j=1}^\ell \tau^{(i)}[j] \cdot h_j \neq 0$. This implies that $\bdv$ can use the trapdoor $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$ to generate a signature.
        To this end, $\bdv$ first samples  a discrete Gaussian vector $\vec{s}^{(i)} \sample D_{\ZZ^{2m},\sigma_1}$ and computes  $\mathbf{u}_M \in \Zq^n$ as
        $$\mathbf{u}_M  = \mathbf{u}  + \mathbf{D} \cdot \textsf{bin}( \sum_{k=1}^N   \mathbf{D}_k \cdot {\mathfrak{m}_k^{(i)} }  +   \mathbf{D}_{0} \cdot {\mathbf{s}^{(i)} } ) ~~  \bmod q.$$ Then,
        using $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$, it samples  a short vector $\mathbf{v}^{(i)} \in \ZZ^{2m}$ in $D^{\mathbf{u}_M}_{\Lambda^{\perp}(\mathbf{A}_{\tau^{(i)}}), \sigma}$ such
        that $(\tau^{(i)},\mathbf{v}^{(i)},\mathbf{s}^{(i)})$ satisfies (\ref{ver-eq-block}).
      \item At the $i^\dagger$-th signing query $ (\mathfrak{m}_1^{(i^\dagger)},\ldots,\mathfrak{m}_N^{(i^\dagger)})$, we have
        \begin{eqnarray} \nonumber
          \mathbf{A}_{\tau^{(i^\dagger)}} &=&   \left[
            \begin{array}{c|c}   \mathbf{A} ~& ~    \mathbf{A}_0 +
              \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{A}_j
          \end{array} \right] \\
          \label{i-mat} &=&   \left[
            \begin{array}{c|c}  \mathbf{D} \cdot  \mathbf{S}  ~&~     \mathbf{D}   \cdot (\mathbf{S}_0 +
              \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{S}_j)
          \end{array} \right]
          \in  \Zq^{ n \times 2m} \quad
        \end{eqnarray}
        due to the constraint $h_0 + \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot h_j = 0 \bmod q $.
        To answer the query, $\bdv$ uses the trapdoor $\mathbf{T}_{\mathbf{D}_0} \in \ZZ^{2m \times 2m}$ of $\Lambda_q^{\perp}(\mathbf{D}_0)$ to sample a short vector
        $\mathbf{s}^{(i^\dagger)} \in D_{\Lambda_q^{\mathbf{c}'_M} (\mathbf{D}_0), \sigma_1}$, where $\mathbf{c}'_M = \mathbf{c}_M - \sum_{k=1}^N \mathbf{D}_k  \cdot  {\mathfrak{m}_k^{(i^\dagger)} } \in \Zq^{2n}$.
        The obtained vector $\mathbf{s}^{(i^\dagger)} \in \ZZ^{2m}$ thus verifies

        \begin{eqnarray} \label{sim-s}
          \mathbf{D}_0 \cdot {\mathbf{s}^{(i^\dagger)} }  &=&
          \mathbf{c}_M - \sum_{k=1}^N \mathbf{D}_k  \cdot  {\mathfrak{m}_k^{(i^\dagger)} } ~\bmod q,
          \quad
        \end{eqnarray}
        and $\adv$ receives $sig^{(i^\dagger)}=(\tau^{(i^\dagger)},\mathbf{v}^{(i^\dagger)},\mathbf{s}^{(i^\dagger)})$, where $ \mathbf{v}^{(i^\dagger)} = (\mathbf{v}_1^T \mid \mathbf{v}_2^T)^T $.
        By construction, the returned signature $sig^{(i^\dagger)}$ satisfies
        \begin{eqnarray*}
          \mathbf{A}_{\tau^{(i^\dagger)}}
          \cdot \left[ \begin{array}{c}
          \mathbf{v}_1 \\ \hline  \mathbf{v}_2 \end{array} \right]
          &=& \mathbf{u} +  \mathbf{D} \cdot \bit \bigl( \mathbf{D}_0 \cdot  {\mathbf{s}^{(i^\dagger)} }  + \sum_{k=1}^N  \mathbf{D}_k \cdot {\mathfrak{m}_k^{(i^\dagger)} } \bigr) \quad \bmod q,
        \end{eqnarray*}
        and the distribution of $(\tau^{(i^\dagger)},\mathbf{v}^{(i^\dagger)},\mathbf{s}^{(i^\dagger)})$ is statistically the same as in \textsf{Game} $2$.
    \end{itemize}
\end{description}
We   conclude that  $\Pr[W_2]$ is negligibly far apart from  $\Pr[W_3]$ since, by the  Leftover Hash Lemma (see \cite[Le. 13]{ABB10}), the public key $PK$ in \textsf{Game} $3$ is statistically close to its distribution in \textsf{Game} $2$.
\medskip

In \textsf{Game} $3$, we claim that the challenger $\bdv$ can use $\adv$ to solve the $\mathsf{SIS}$ problem by finding a short vector of $\Lambda_q^\perp(\mathbf{D})$ with probability $\Pr[W_3]$. Indeed,
  with proba\-bility $\Pr[W_3]$,  the adversary outputs a valid signature $sig^\star=(\tau^{(i^\dagger)},\mathbf{v}^\star,\mathbf{s}^\star)$ on a message $\mathsf{Msg}^\star=(\mathfrak{m}_1^\star,\ldots,\mathfrak{m}_N^\star)$ with $\| \mathbf{v}^\star \| \leq \sigma \sqrt{2m}$ and $\| \mathbf{s}^\star \| \leq \sigma_1 \sqrt{2m}$.
If we parse $\mathbf{v}^\star \in \ZZ^{2m}$ as $({\mathbf{v}_1^\star }^T \mid {\mathbf{v}_2^\star }^T )^T$ with $\mathbf{v}_1^\star,\mathbf{v}_2^\star \in \ZZ^m$, we have
the equality
\begin{eqnarray} \label{first-sol}
  \mathbf{A}_{\tau^{(i^\dagger)}} \cdot \left[ \begin{array}{c}
 \mathbf{v}_1^\star  \\ \hline    \mathbf{v}_2^\star
\end{array} \right]
 &=& \mathbf{u} + \mathbf{D} \cdot \textsf{bin}(  \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} } ) \quad \bmod q.
\end{eqnarray}

Due to the way $\mathbf{u} \in \Zq^n$ was defined at the outset of the game,  $\bdv$ also knows short vectors $\mathbf{v}^{(i^\dagger)}=(\mathbf{v}_1^T \mid \mathbf{v}_2^T)^T \in \ZZ^{2m}$
such that
\begin{eqnarray} \label{second-sol}    \mathbf{A}_{\tau^{(i^\dagger)}} \cdot
  \left[\begin{array}{c}
 \mathbf{v}_1 \\ \hline \mathbf{v}_2
\end{array} \right] = \mathbf{u} +  \mathbf{D}  \cdot \textsf{bin}( \mathbf{c}_M )  \bmod q. \end{eqnarray}
 Relation (\ref{sim-s}) implies that  $ \mathbf{c}_M \neq \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} }  \bmod q$ by hypothesis. It follows  that  $\textsf{bin}(\mathbf{c}_M) - \textsf{bin}(   \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} } )  $ is a non-zero vector in $\{-1,0,1\}^m$. Subtracting (\ref{second-sol}) from (\ref{first-sol}), we get
\begin{eqnarray*}
  \mathbf{A}_{\tau^{(i^\dagger)}} \cdot \left[\begin{array}{c}
 \mathbf{v}_1^\star - \mathbf{v}_1  \\ \hline    \mathbf{v}_2^\star - \mathbf{v}_1
\end{array} \right]
 &=&  \mathbf{D} \cdot \bigl(  \textsf{bin}(\mathbf{c}_M) - \textsf{bin}(   \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} } ) \bigr)  \mod q,
\end{eqnarray*}
which implies
\begin{multline} \label{eq-un}
    \left[
\begin{array}{c|c}  \mathbf{D} \cdot  \mathbf{S}  ~ &~   \mathbf{D} \cdot (\mathbf{S}_0 +
\sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{S}_j)
\end{array} \right]  \cdot  \left[ \begin{array}{c}  {\mathbf{v}_1^\star -\mathbf{v}_1 } \\ \hline   {\mathbf{v}_2^\star - \mathbf{v}_2 } \end{array} \right] \\ =  \mathbf{D} \cdot \bigl(  \textsf{bin}(\mathbf{c}_M) - \textsf{bin}(   \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} } ) \bigr)  \mod q .
\end{multline}
  The above implies that the vector
\begin{eqnarray} \nonumber
  \mathbf{w} &=&
  \mathbf{S}  \cdot (\mathbf{v}_1^\star - \mathbf{v}_1) + (\mathbf{S}_0  + \sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{S}_j ) \cdot (\mathbf{v}_2^\star - \mathbf{v}_2)  \\
  \nonumber && \hspace{2.75cm} ~+ \bit \big(   \mathbf{D}_0 \cdot {\mathbf{s}^{\star} } + \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} }  \big) -  \textsf{bin}(\mathbf{c}_M)
\end{eqnarray}
is a short integer vector of $\Lambda_q^{\perp}(\mathbf{D})$. Indeed,   its  norm can be bounded as  $\| \mathbf{w} \| \leq \beta'' = \sqrt{2}   (\ell+2)   \sigma^2  m^{3/2} + m^{1/2} $. We argue that it is non-zero with overwhelming probability. We already observed that
$ \textsf{bin}(   \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} } ) - \textsf{bin}(\mathbf{c}_M)$ is a non-zero vector of $\{-1,0,1\}^m$, which rules out the event that
 $({\mathbf{v}_1^\star}, {\mathbf{v}_2^\star} ) =({\mathbf{v}_1} , {\mathbf{v}_2}) $. Hence, we can only have $\mathbf{w}=\mathbf{0}^m$ when the equality
\begin{multline} \label{final-eq}
 \mathbf{S}  \cdot (\mathbf{v}_1^\star - \mathbf{v}_1) + (\mathbf{S}_0  +
\sum_{j=1}^\ell \tau^{(i^\dagger)}[j] \cdot \mathbf{S}_j ) \cdot (\mathbf{v}_2^\star - \mathbf{v}_2) \\ = \textsf{bin}(\mathbf{c}_M)  -  \bit \big(   \mathbf{D}_0 \cdot {\mathbf{s}^{\star} }
+ \sum_{k=1}^N   \mathbf{D}_k  \cdot {\mathfrak{m}_k^{\star} }  \big) \qquad
\end{multline}
holds over $\ZZ$. However, as long as either $\mathbf{v}_1^\star \neq \mathbf{v}_1$ or $\mathbf{v}_2^\star \ne \mathbf{v}_2$, the left-hand-side member of (\ref{final-eq})
 	is information theoretically unpredictable since the columns of matrices $\mathbf{S}$ and $\{\mathbf{S}_j\}_{j=0}^\ell$ are statistically hidden in the view of $\adv$.
 Indeed, conditionally on  the public key, each column of  $\mathbf{S}$ and $\{\mathbf{S}_j\}_{j=0}^\ell$ has at least $n$ bits
 of min-entropy, as shown by, e.g., \cite[Le. 2.7]{MP12}.
\end{proof}


\subsection{Protocols for Signing a Committed Value and Proving Possession of a Signature} \label{commit-sig}



We first show  a two-party protocol  whereby a user can interact with the signer in order to obtain a signature on a committed message.

In order to prove that the scheme still guarantees unforgeability for obliviously signed messages,
 we will assume that each message block $\mathfrak{m}_k \in \{0,1\}^{2m}$ is obtained by encoding
the actual message $M_k =M_k[1] \ldots M_k[m] \in \{0,1\}^m$ as $\mathfrak{m}_k= \mathsf{Encode}(M_k)=( \bar{M}_k[1] , M_k[1],\ldots, \bar{M}_k[m] , M_k[m] ) $. Namely,
each $0$ (respectively each $1$) is encoded as a pair $(1,0)$ (resp. $(0,1)$). The reason for this encoding is that the proof of   Theorem \ref{commit-thm} requires that at least one block
$\mathfrak{m}_k^\star $ of the forgery message is $1$ while the same bit is $0$ at some specific signing query. We will show (see \cref{se:gs-lwe-stern}) that the correctness of this encoding can
be efficiently proved using Stern-like~\cite{Ste96} protocols.

To sign committed messages, a first idea is exploit the fact that our signature of Section  \ref{desc-sig-protoc} blends well with the $\mathsf{SIS}$-based commitment scheme suggested by Kawachi \textit{et al.}~\cite{KTX08}.
  In the latter scheme, the commitment key consists of matrices $(\mathbf{D}_0,\mathbf{D}_1) \in \Zq^{2n \times 2m} \times \Zq^{2n \times 2m}$, so that    message
	$\mathfrak{m} \in \{0,1\}^{2m}$ can be committed to by sampling a   Gaussian vector $\mathbf{s} \sample D_{\ZZ^{2m},\sigma}$ and computing
	$\mathbf{C}=  \mathbf{D}_0 \cdot \mathbf{s} + \mathbf{D}_1 \cdot \mathfrak{m}  \in \Zq^{2n}$. This scheme  extends to commit to multiple messages $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$ at once by computing
$\mathbf{C}=\mathbf{D}_0 \cdot \mathbf{s} + \sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k  \in \Zq^{2n}$ using a longer
 commitment key $(\mathbf{D}_0,\mathbf{D}_1,\ldots,\mathbf{D}_N) \in (\Zq^{2n \times 2m})^{N+1} $. It is easy to see that the resulting commitment remains statistically hiding and computationally
 binding under the $\mathsf{SIS}$ assumption.

In order to make our construction usable in  the definitional framework of Camenisch \textit{et al.} \cite{CKL+15}, we   assume common public parameters
 (i.e., a common reference string) and encrypt all witnesses of which knowledge is being proved under a public key included in the common reference string. The resulting ciphertexts thus serve as statistically binding commitments
 to the witnesses.
 To enable this,  the common public parameters   comprise public keys $\mathbf{G}_0 \in \Zq^{n \times \ell}$, $\mathbf{G}_1 \in \Zq^{n \times 2m}$
for multi-bit variants of the dual Regev cryptosystem \cite{GPV08} and  all parties are denied access to the underlying private keys. The flexibility of Stern-like protocols allows us to prove that  the content of a perfectly hiding commitment $ \mathbf{c}_{\mathfrak{m}}$ is consistent with
encrypted values.%, the protocols of Ling \textit{et al.} \cite{LNW15} come in handy.


\begin{description}
\item[\textsf{Global}\textrm{-}\textsf{Setup}:] Let $B = \sqrt{n} \omega(\log n)$ and let $\chi$ be a $B$-bounded distribution.
Let $p = \sigma \cdot \omega(\sqrt{m})$ upper-bound  entries of vectors sampled from the distribution~$D_{\ZZ^{2m},\sigma}$.
    Generate two public  keys  for the dual Regev encryption scheme
    in its multi-bit variant. These keys consists of a public random matrix
    $\mathbf{B} \sample (\Zq^{n \times m})$ and  random matrices $\mathbf{G}_0 = \mathbf{B} \cdot \mathbf{E}_0 \in \Zq^{n \times \ell }$, $\mathbf{G}_1  = \mathbf{B} \cdot \mathbf{E}_1  \in \Zq^{n \times 2m}$,
		 where $\mathbf{E}_0 \in \ZZ^{ m \times \ell}$ and $\mathbf{E}_1 \in \ZZ^{m \times 2m}$ are short Gaussian matrices with columns sampled from $D_{\ZZ^{m},\sigma}$. These matrices  will be
		used to encrypt integer vectors of dimension $\ell$ and $2m$, respectively.  Finally, generate public parameters $CK\coloneqq \{ \mathbf{D}_k \}_{k=0}^N$ consisting of uniformly
		random matrices $\mathbf{D}_k \sample (\Zq^{2n \times 2m})$ for a statistically hiding commitment
			to vectors in $(\{0,1\}^{2m})^N$.
		Return public parameters consisting of
    \[ \mathsf{par}\coloneqq  \{ \mathbf{B} \in \Zq^{n \times m} ,\mathbf{G}_0 \in \Zq^{n \times \ell},\mathbf{G}_1 \in \Zq^{n \times 2m},CK  \}. \]

\item[\textsf{Issue} $\leftrightarrow$ \textsf{Obtain} :]  The signer $S$, who holds a key pair $PK\coloneqq \{ \mathbf{A} , ~\{\mathbf{A}_j\}_{j=0}^\ell,~\mathbf{D},~\mathbf{u} \}$, $SK\coloneqq \mathbf{T}_{\mathbf{A}}$, interacts with the user $U$
 who has a message $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$, in the following interactive protocol. \smallskip
\begin{itemize}
\item[1.] $U$ samples  $\mathbf{s}' \sample D_{\ZZ^{2m},\sigma} $ and computes $ \mathbf{c}_{\mathfrak{m}} = \mathbf{D}_0 \cdot \mathbf{s}' + \sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k \in \mathbb{Z}_q^{2n}$
 which is sent to $S$ as a commitment to $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$. In addition, $U$ encrypts  $\{\mathfrak{m}_k\}_{k=1}^N$ and $\mathbf{s}'$ under the dual-Regev public key $(\mathbf{B},\mathbf{G}_1)$
   by computing for all $k \in \{1,\ldots,N\}$:
\begin{align} \label{enc-Mk} \nonumber
\mathbf{c}_{k} & = (\mathbf{c}_{k,1},\mathbf{c}_{k,2}) \\
               & =   \big( \mathbf{B}^T \cdot \mathbf{s}_{k} + \mathbf{e}_{k,1} ,~  \mathbf{G}_1^T \cdot \mathbf{s}_{k} + \mathbf{e}_{k,2} + \mathfrak{m}_k \cdot \lfloor q/2 \rfloor  \big) \in \Zq^m \times \Zq^{2m}
\end{align}
for  randomly chosen $\mathbf{s}_{k} \sample \chi^n$, $\mathbf{e}_{k,1} \sample \chi^m$, $\mathbf{e}_{k,2} \sample  \chi^{2m}$,
and
\begin{align} \label{enc-s} \nonumber
\mathbf{c}_{s'} & = (\mathbf{c}_{s',1},\mathbf{c}_{s',2}) \\
                & = \big( \mathbf{B}^T \cdot \mathbf{s}_{0} + \mathbf{e}_{0,1} ,~  \mathbf{G}_1^T \cdot \mathbf{s}_{0} + \mathbf{e}_{0,2} + \mathbf{s}' \cdot \lfloor q/p \rfloor  \big)  \in \Zq^m \times \Zq^{2m}
\end{align}
where $\mathbf{s}_{0} \sample \chi^n$, $\mathbf{e}_{0,1} \sample \chi^m$, $\mathbf{e}_{0,2} \sample  \chi^{2m}$.  The ciphertexts $\{\mathbf{c}_k\}_{k=1}^N$ and $\mathbf{c}_{s'}$ are
sent to $S$ along with $\mathbf{c}_{\mathfrak{m}}$.

Then, $U$ generates an interactive zero-knowledge argument to convince~$S$ that
$ \mathbf{c}_{\mathfrak{m}}$ is a commitment to $(\mathfrak{m}_1, \ldots, \mathfrak{m}_N)$ with the randomness   $\mathbf{s}'$  such that $\{\mathfrak{m}_k\}_{k=1}^N$ and
  $\mathbf{s}'$   were honestly encrypted to $\{ \mathbf{c}_{k} \}_{i=1}^N$ and $\mathbf{c}_{s'}$, as in~(\ref{enc-Mk}) and~(\ref{enc-s}).
For convenience, this argument system will be described in Section~\ref{subsection:zk-for-commitments}, where we demonstrate that, together with other zero-knowledge protocols used in this work, it can be derived from a Stern-like~\cite{Ste96} protocol constructed in \cref{se:gs-lwe-stern}.

\item[2.]  If the argument of step 1 properly verifies, $S$ samples $\mathbf{s}'' \sample D_{\ZZ^{2m},\sigma_0}$ and computes
 a vector $\mathbf{u}_{\mathfrak{m}}= \mathbf{u} + \mathbf{D} \cdot \bit \bigl( \mathbf{c}_{\mathfrak{m}} + \mathbf{D}_0 \cdot \mathbf{s}'' \bigr) \in \Zq^n$.
Next, $S$ randomly picks  $\tau \sample \{0,1\}^\ell$ and
 uses $\mathbf{T}_{\mathbf{A}}$ to compute a delegated basis $\mathbf{T}_{\tau} \in \ZZ^{2m \times 2m}$ for the matrix $\mathbf{A}_{\tau} \in \Zq^{n \times 2m}$ of (\ref{tau-matrix}).
Using  $\mathbf{T}_\tau \in \ZZ^{2m \times 2m}$, $S$ samples  a short vector $\mathbf{v} \in \ZZ^{2m}$ in $D^{\mathbf{u}_M}_{\Lambda^{\perp}(\mathbf{A}_\tau), \sigma}$.  It returns
the vector $( \tau,\mathbf{v},\mathbf{s}'') \in \{0,1\}^\ell \times  \ZZ^{2m} \times  \ZZ^{2m} $  to $U$.
\item[3.] $U$ computes $\mathbf{s} = \mathbf{s}'+\mathbf{s}''$ over $\ZZ$ and verifies that $$\mathbf{A}_{\tau} \cdot \mathbf{v} = \mathbf{u} + \mathbf{D} \cdot \bit
\bigl( \mathbf{D}_0 \cdot \mathbf{s} + \sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k \bigr) \bmod q.$$ If so, it outputs $(\tau,\mathbf{v},\mathbf{s})$. Otherwise, it outputs $\perp$.
 \end{itemize}
\end{description}
Note that, if both parties faithfully run the protocol, the user obtains a valid signature $(\tau,\mathbf{v},\mathbf{s})$ for which the distribution of $\mathbf{s}$ is $D_{\ZZ^{2m},\sigma_1}$,
where $\sigma_1=\sqrt{\sigma^2 + \sigma_0^2}$.

The following protocol allows proving possession of a message-signature pair.

\begin{description}
\item[\textsf{Prove}:] On input of a signature $(\tau,\mathbf{v}=(\mathbf{v}_1^T \mid \mathbf{v}_2^T)^T,\mathbf{s}) \in \{0,1\}^\ell \times \ZZ^{2m} \times \ZZ^{2m}$ on the message $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$, the user
does the following. \smallskip \smallskip
\begin{itemize}
\item[1.] Using  $(\mathbf{B},\mathbf{G}_0)$ and $(\mathbf{B},\mathbf{G}_1)$   generate perfectly binding commitments to $\tau \in \{0,1\}^\ell$, $\{\mathfrak{m}_k \}_{k=1}^N$,
 $\mathbf{v}_1,\mathbf{v}_2 \in \ZZ^m$ and $\mathbf{s} \in \ZZ^{2m}$.  Namely, compute
\begin{align*}
  \mathbf{c}_{\tau} & = (\mathbf{c}_{\tau,1},\mathbf{c}_{\tau,2}) \\
                    & =  \big( \mathbf{B}^T \cdot \mathbf{s}_{\tau} + \mathbf{e}_{\tau,1} ,~  \mathbf{G}_0^T \cdot \mathbf{s}_{\tau} + \mathbf{e}_{\tau,2} + \tau
  \cdot \lfloor q/2 \rfloor  \big)  \in \Zq^m \times \Zq^\ell, \\
%
  \mathbf{c}_{k}   & = (\mathbf{c}_{k,1},\mathbf{c}_{k,2}) \\
                   & = \big( \mathbf{B}^T \cdot \mathbf{s}_{k} + \mathbf{e}_{k,1} ,~  \mathbf{G}_1^T \cdot \mathbf{s}_{k} + \mathbf{e}_{k,2} + \mathfrak{m}_k \cdot \lfloor q/2 \rfloor  \big) \in \Zq^m \times \Zq^{2m} \\
                   & \hspace{7.6cm} \forall k\in \{1,\ldots,N\}
\end{align*}
where $\mathbf{s}_{\tau}, \mathbf{s}_{k}  \sample \chi^n$, $\mathbf{e}_{\tau,1} , \mathbf{e}_{k,1} \sample \chi^m$, $\mathbf{e}_{\tau,2} \sample  \chi^\ell$,        $\mathbf{e}_{k,2} \sample  \chi^{2m}$,
as well as
\begin{align*}
  \mathbf{c}_{\mathbf{v}} & = (\mathbf{c}_{\mathbf{v},1},\mathbf{c}_{\mathbf{v},2}) \\
                          & =  \big( \mathbf{B}^T \cdot \mathbf{s}_{\mathbf{v}} + \mathbf{e}_{\mathbf{v},1} ,~  \mathbf{G}_1^T \cdot \mathbf{s}_{\mathbf{v}} + \mathbf{e}_{\mathbf{v},2} + \mathbf{v}   \cdot \lfloor q/p \rfloor  \big)  \in \Zq^m \times \Zq^{2m} \\
  \mathbf{c}_{s} & = (\mathbf{c}_{s,1},\mathbf{c}_{s,2}) \\
                 & =  \big( \mathbf{B}^T \cdot \mathbf{s}_{0} + \mathbf{e}_{0,1} ,~  \mathbf{G}_1^T \cdot \mathbf{s}_{0} + \mathbf{e}_{0,2} + \mathbf{s}  \cdot \lfloor q/p \rfloor  \big)  \in \Zq^m \times \Zq^{2m} ,
\end{align*}
 where $\mathbf{s}_{\mathbf{v}}, \mathbf{s}_{0}  \sample \chi^n$, $\mathbf{e}_{\mathbf{v},1},\mathbf{e}_{0,1} \sample \chi^m$, 
    $\mathbf{e}_{\mathbf{v},2},\mathbf{e}_{0,2}\sample \chi^{2m}$.
\item[2.] Prove in zero-knowledge that $\mathbf{c}_{\tau}$, $\mathbf{c}_{s}$, $\mathbf{c}_{\mathbf{v} }$,  $\{\mathbf{c}_k\}_{k=1}^N$ encrypt a valid message-signature pair. In Section~\ref{subsection:zk-for-signature}, we show that this involved zero-knowledge protocol can be derived from the statistical zero-knowledge argument of knowledge for a simpler, but more general  relation  that we explicitly present in \cref{se:gs-lwe-stern}. The proof system can be made statistically ZK for a malicious verifier using standard techniques (assuming a common reference string, we can use  \cite{Dam00}).  In the random oracle model, it can
  be made non-interactive using the Fiat-Shamir heuristic \cite{FS86}.

\end{itemize}
\end{description}

We   require that the adversary be unable to prove possession of a signature of a message $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$ for which it did not legally
obtain a credential by interacting with the issuer.  Note that the messages that are blindly signed by the issuer are uniquely defined since, at each signing
query, the adversary is required to supply perfectly binding commitments $\{\mathbf{c}_k\}_{k=1}^N$ to $(\mathfrak{m}_1,\ldots,\mathfrak{m}_N)$. 

In instantiations using non-interactive proofs, we assume that  these can be bound to a verifier-chosen nonce    to prevent replay attacks, as suggested    in   \cite{CKL+15}.

The security proof (in Theorem \ref{commit-thm}) makes crucial use of the R\'enyi divergence using arguments in the spirit of Bai \textit{et al.} \cite{BLL+15}. The
reduction has to guess upfront the index $i^\star \in \{1,\ldots,Q\}$ of the specific signing query for which the adversary will re-use $\tau^{(i^\star)}$. For
this query, the reduction will have to make sure that the simulation trapdoor of Agrawal \textit{et al.} \cite{ABB10} (used by the $\mathsf{SampleRight}$ algorithm
of Lemma \ref{lem:sampler}) vanishes: otherwise, the adversary's forgery would not be usable for solving $\mathsf{SIS}$. This means that, as in  the proof of
\cite{BHJ+15}, the reduction must answer exactly one signing query in a different way, without using the trapdoor.  While B\"ohl \textit{et al.} solve this
problem by exploiting the fact that they only need to prove security against non-adaptive forgers, we  directly use a built-in chameleon hash function mechanism
which is implicitly realized by the matrix $\mathbf{D}_0$ and the vector $\mathbf{s}$. Namely, in the signing query for which the Agrawal \textit{et al.}
trapdoor~\cite{ABB10} cancels, we assign a special value to the vector $\mathbf{s} \in \ZZ^{2m}$, which depends on the adaptively-chosen signed message
$(\mathsf{Msg}_1^{(i^\star)},\ldots,\mathsf{Msg}_N^{(i^\star)})$ and some Gaussian matrices $\{\mathbf{R}_k\}_{k=1}^N$  hidden behind $\{\mathbf{D}_k\}_{k=1}^N$.

One issue is that this results in a different distribution  for the vector   $\mathbf{s} \in \ZZ^m$. However, we can still view $\mathbf{s}$ as a vector sampled from a
Gaussian distribution centered away from $\mathbf{0}^{2m}$. Since this specific situation occurs only once during the simulation, we can apply a result proved in
\cite{LSS14} which upper-bounds the R\'enyi divergence between two Gaussian distributions with identical standard  deviations but different centers.  By
choosing the standard deviation $\sigma_1$ of $\mathbf{s} \in \ZZ^{2m}$ to be polynomially larger than that of the columns of matrices $\{\mathbf{R}_k\}_{k=1}^N$, we can
keep the R\'enyi divergence between the two distributions of $\mathbf{s}$ (i.e., the one of the simulation and the one of the real game) sufficiently small to apply
the probability preservation property (which still gives a polynomial reduction since the argument must only be applied on one signing query).  Namely, the
latter implies that, if the R\'enyi divergence $R_2(\mathbf{s}^{\mathsf{real}}||\mathbf{s}^{\mathsf{sim}})$ is polynomial, the probability that  the simulated vector
$\mathbf{s}^{\mathsf{sim}} \in \ZZ^{2m}$  passes the verification test will  only be polynomially smaller than in the real game and so will be the adversary's
probability of success.

Another option would have been to keep the statistical distance between $\mathbf{s}^{\mathsf{real}}$ and $\mathbf{s}^{\mathsf{sim}}$ negligible using the smudging
technique of \cite{AJL+12}. However, this would have implied to use an exponentially large modulus $q$ since $\sigma_1$ should have been exponentially larger
than the standard deviations of the columns of $\{\mathbf{R}_k\}_{k=1}^N$.

\begin{theorem} \label{commit-thm}
  Under the $\mathsf{SIS}_{n,2m, q, \hat{\beta}}$ assumption, where $\hat{\beta} = N \sigma (2m)^{3/2} + 4 \sigma_1 m^{3/2}$\hspace*{-1.5pt}, the above
  protocols are  secure protocols for obtaining a signature on a committed message and proving possession of a valid message-signature pair.
\end{theorem}

In the following proof, we make use of the Rényi divergence in a similar way to~\cite{BLL+15}:
instead of the classical statistical distance we sometimes use the R\'enyi divergence, which is a measurement of the distance between two distributions.
Its use in security proofs for lattice-based systems was first considered  by Bai {\em et al.}~\cite{BLL+15} and further improved by Prest~\cite{Pre17}. We first recall its definition.

\defRenyi*


We will focus on the following properties of the R\'enyi divergence, the proofs can be found in~\cite{LSS14}.

\begin{lemma}[{\cite[Le. 2.7]{BLL+15}}]
  \label{lem:renyi}
  Let $a \in [1, +\infty]$. Let $P$ and $Q$ denote distributions with $\Supp(P)
  \subseteq \Supp(Q)$. Then the following properties hold:
  \begin{description}
    \item[Log. Positivity:] $R_a(P||Q) \geq R_a(P||P) = 1$
    \item[Data Processing Inequality:] $R_a(P^f || Q^f) \leq R_a(P||Q)$ for any
      function $f$, where $P^f$ denotes the distribution of $f(y)$ induced by
      sampling $y \sample P$ (resp. $y \sample Q$)
    \item[Multiplicativity:] Assume $P$ and $Q$ are two distributions of a pair
      of random variables $(Y_1, Y_2)$. For $i \in \{1,2\}$, let $P_i$ (resp.
      $Q_i$) denote the marginal distribution of $Y_i$ under $P$ (resp. $Q$),
      and let $P_{2|1}(\cdot|y_1)$ (resp. $Q_{2|1}(\cdot|y_1)$) denote the conditional distribution of $Y_2$ given that $Y_1 = y_1$. Then we have:
      \begin{itemize} \renewcommand\labelitemi{$\bullet$}
        \item $R_a(P||Q) = P_a(P_1 || Q_1) \cdot R_a(P_2||Q_2)$ if $Y_B$ and $Y_2$ are independent;
        \item $R_a(P||Q) \leq R_\infty (P_1 || Q_1) \cdot max_{y_1 \in X} R_a\left( P_{2|1}(\cdot | y_1) || Q_{2|1}(\cdot | y_1) \right)$.
      \end{itemize}
    \item[Probability Preservation:] Let $A \subseteq \Supp(Q)$ be an arbitrary
    event. If $a \in ]1, +\infty[$, then $Q(A) \geq
      P(A)^{\frac{a}{a-1}}/R_a(P||Q)$. Further we have:
      \[ Q(A) \geq P(A) / R_\infty(P||Q) \]
    \item[Weak Triangle Inequality:] Let $P_1, P_2, P_3$ be three distributions
      with \[\Supp(P_1) \subseteq \Supp(P_2) \subseteq \Supp(P_3).\]
      Then we have:
      \[ R_a(P_1||P_3) \leq \begin{cases}
          R_a(P_1 || P_2) \cdot R_\infty(P_2 || P_3),\\[2mm]
          R_\infty(P_1||P_2)^{\frac{a}{a-1}} \cdot R_a(P_2||P_3) & \mbox{if } a \in ]1, +\infty[.
      \end{cases}\]
  \end{description}
\end{lemma}

In our proofs, we mainly use the probability preservation to bound the
probabilities during hybrid games where the two distributions are not close in terms of statistical distance.

%--------- PROOF ----------
\begin{proof} The proof is very similar to the proof of \cref{th:gs-lwe-security-cma-sig} and we will only explain the changes.

  Let us assume that an adversary $\adv$ can prove possession of a signature on a message $(\mathfrak{m}_1^\star,\ldots,\mathfrak{m}_N^\star)$ which has not been blindly signed by the issuer,
  we outline an algorithm $\bdv$ that solves a  $\mathsf{SIS}_{n,2m,q,\beta}$  instance $\bar{\mathbf{A}}$, where  $\bar{\mathbf{A}} =
  [ \bar{\mathbf{A}}_1 \mid \bar{\mathbf{A}}_2 ]  \in \ZZ_q^{ n \times 2m}$  with matrices
  $\bar{\mathbf{A}}_1, \bar{\mathbf{A}}_2 \sample \U(\ZZ_q^{n \times   m})$. 

  At the outset of the game, $\bdv$ generates the common parameters $\mathsf{par}$ by choosing
  $\mathbf{B} \in_R \ZZ_q^{n \times m}$ and defining $\mathbf{G}_0 = \mathbf{B} \cdot \mathbf{E}_0 \in \ZZ_q^{n \times \ell }$, $\mathbf{G}_1  = \mathbf{B} \cdot \mathbf{E}_1  \in \ZZ_q^{n \times 2m}$.
  The short Gaussian matrices $\mathbf{E}_0 \in \ZZ^{ m \times \ell}$ and $\mathbf{E}_1 \in \ZZ^{m \times 2m}$ are retained for later use. Also, $\bdv$ flips a  coin $coin \in \{0,1,2\}$ as
  a guess for the kind of attack that $\adv$ will mount. If $coin=0$, $\bdv$ expects a Type I forgery, where $\adv$'s forgery involves a new $\tau^\star \in \{0,1\}^\ell$ that
  was never used by the signing oracle. If $coin=1$, $\bdv$ expects $\adv$ to   recycle  a tag $\tau^\star$ involved in some signing query in its forgery. Namely,
  if $coin=1$, $\bdv$ expects an attack which is either a Type II forgery or a Type III forgery.
  If $coin=2$,   $\bdv$ rather bets that $\adv$ will break the soundness of the interactive argument systems used in the signature issuing protocol or the $\mathsf{Prove}$ protocol.
  Depending on the value of $coin \in \{0,1,2 \}$, $\bdv$ generates the issuer's public key $PK$ and simulates $\adv$'s view in  different ways.

  \begin{itemize}
    \item If $coin=0$, $\bdv$ undertakes to find a short non-zero vector of $\Lambda_q^{\perp}(\bar{\mathbf{A}}_1)$, which in turn yields a short non-zero vector
      of $\Lambda_q^{\perp}(\bar{\mathbf{A}})$. To this end, it defines $\mathbf{A}=\bar{\mathbf{A}}_1$ and
      generates $PK$ by computing $\{\mathbf{A}_j\}_{j=0}^\ell$ as re-randomizations of $\mathbf{A} \in \ZZ_q^{n \times m}$ as in the proof of Lemma \ref{le:lwe-gs-type-I-attacks}. This implies that $\bdv$ can always answer signing queries using the trapdoor $\mathbf{T}_{\mathbf{C}}
      \in \ZZ^{m \times m}$ of the matrix $\mathbf{C}$ without even knowing the messages hidden in the commitments $ \mathbf{c}_{\mathfrak{m}}$ and $\{\mathbf{c}_k\}_{k=1}^N$, $\mathbf{c}_{s'}$.
      When the adversary generates a proof of possession of its own at the end of the game, $\bdv$ uses the matrices $\mathbf{E}_0 \in \ZZ^{ m \times \ell}$ and $\mathbf{E}_1 \in \ZZ^{m \times 2m}$
      as an extraction trapdoor to extract a plain message-signature pair $\big( (\mathfrak{m}_1^\star,\ldots,\mathfrak{m}_N^\star),  (\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star) \big)$
      from the ciphertexts
      $\{ \mathbf{c}_k^\star\}_{k=1}^N$ $(\mathbf{c}_{\mathbf{v}_1}^\star,\mathbf{c}_{\mathbf{v}_2^\star})$, $\mathbf{c}_{\tau}^\star$, $\mathbf{c}_{\mathbf{s}}^\star$ produced by $\adv$ as part of its forgery.
      If the extracted $\tau^\star$ is not a new tag, then $\bdv$ aborts. Otherwise, it can solve the given  $\mathsf{SIS}$ instance exactly as in the proof of Lemma \ref{le:lwe-gs-type-I-attacks}.

    \item If $coin=1$, the proof proceeds as in the proof of Lemma \ref{le:lwe-gs-type-II-attacks} with one difference in \textsf{Game} $3$. This difference is that \textsf{Game} $3$ is no longer statistically
      indistinguishable from \textsf{Game} $2$: instead, we rely on an argument based on the R\'enyi divergence.
      In \textsf{Game} $3$, $\bdv$ generates $PK$ exactly as in the proof of Lemma \ref{le:lwe-gs-type-II-attacks}. This implies that $\bdv$ takes a guess $i^\dagger \leftarrow U(\{1,\ldots,Q\})$
      with the hope that $\adv$ will choose to recycle the tag    $\tau^{(i^\dagger)}  $ of the $i^\dagger$-th signing query (i.e., $ \tau^\star =\tau^{(i^\dagger)} $).
      As in the proof of Lemma \ref{le:lwe-gs-type-II-attacks}, $\bdv$  defines $\mathbf{D}=\bar{\mathbf{A}}_1 \in \ZZ_q^{n \times m}$ and $\mathbf{A}= \bar{\mathbf{A}}_1 \cdot \mathbf{S} $ for a small-norm
      matrix $\mathbf{S} \in \ZZ^{m \times m}$ with Gaussian entries. It also  ``programs'' the matrices $\{ \mathbf{A}_j\}_{j=0}^\ell$ in such a way that
      the trapdoor precisely vanishes at the $i^\dagger$-th signing query: in other words,
      the sum $$\mathbf{A}_0 + \sum_{j=1}^\ell \tau^{(i)} [j] \mathbf{A}_j = \bar{\mathbf{A}}_1 \cdot (\mathbf{S}_0 + \sum_{j=1}^\ell \tau^{(i)} [j] \cdot \mathbf{S}_j) + (h_0 + \sum_{j=1}^\ell \tau^{(i)} [j] \cdot h_j ) \cdot \mathbf{C} $$ does not depend on the matrix $\mathbf{C} \in \ZZ_q^{n \times m}$
      (of which a trapdoor $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$ is known to $\bdv$) when $\tau^{(i)} = \tau^{(i^\dagger)}$, but it does for all other tags $\tau^{(i)} \neq \tau^{(i^\dagger)}$. In the setup phase,
      $\bdv$ also sets up a random  matrix $\mathbf{D}_0 \in U(\ZZ_q^{2n \times 2m})$ which it obtains by choosing
      $\mathbf{A}' \sample (\ZZ_q^{n \times 2m})$  to define
      \begin{eqnarray} \label{def-D0}
        \mathbf{D}_0=\begin{bmatrix} \bar{\mathbf{A}} \\ \hline \mathbf{A}' \end{bmatrix} \in \ZZ_q^{2n \times 2m}.
      \end{eqnarray}
      Then, it  computes $\mathbf{c}_M = \mathbf{D}_0 \cdot \mathbf{s}_0  \in \ZZ_q^{2n}$ for a short Gaussian vector
      $\mathbf{s}_0 \sample D_{\ZZ^{2m},\sigma_0}$, which will be used in the $i^\dagger$-th query.
      Next, it samples short vectors $\mathbf{v}_1,\mathbf{v}_2 \sample D_{\ZZ^m,\sigma}$ to define
      $$\mathbf{u}= \mathbf{A}_{\tau^{(i^\dagger)}} \cdot \begin{bmatrix} \mathbf{v}_1   \\ \mathbf{v}_2 \end{bmatrix} - \mathbf{D} \cdot \textsf{bin}(\mathbf{c}_M) ~  \in \ZZ_q^n.$$
      In addition, $\bdv$  picks extra small-norm matrices $\mathbf{R}_1,\ldots,\mathbf{R}_N \in \ZZ^{2m \times 2m}$ whose columns are sampled from $D_{\ZZ^m,\sigma}$, which
      are used  to define randomizations of $\mathbf{D}_0$ by computing  $\mathbf{D}_k = \mathbf{D}_0 \cdot \mathbf{R}_k$ for each $k \in \{1,\ldots,N\}$.
      The adversary is given public parameters $\mathsf{par}\coloneqq \{\mathbf{B},\mathbf{G}_0,\mathbf{G}_1,CK\}$, where $CK=\{\mathbf{D}_k\}_{k=0}^N$, and the public key $PK\coloneqq \big( \mathbf{A}, \{\mathbf{A}_j\}_{j=0}^\ell, \mathbf{D},\mathbf{u} \big)$.
  \end{itemize}

  Using  $\mathbf{T}_{\mathbf{C}}$,
  $\bdv$ can perfectly emulate the signing oracle  at all queries, except the $i^\dagger$-th query where the
  vector ${\mathbf{s}''}^{(i^\dagger)}$ chosen by $\bdv$ is sampled from a distribution that departs from $D_{\ZZ^{2m},\sigma_0}$.  At the $i^\dagger$-th query,
  $\bdv$ uses the extraction trapdoor $\mathbf{E}_1 \in \ZZ^{m \times 2m}$ to obtain $ {\mathbf{s}' }^{(i^\dagger)} \in \ZZ^{2m}$ and $\{\mathfrak{m}_k\}_{k=1}^N$  -- which form a valid opening
  of $\mathbf{c}_{\mathfrak{m}}$ unless the soundness of the proof system is broken (note that the latter case is addressed by the situation $coin=3$) -- from the ciphertexts
  $\mathbf{c}_{s'}^{(i^\dagger)} $ and $\{ \mathbf{c}_k\}_{k=1}^N$ sent by $\adv$ at step 1 of the signing protocol. Then, $\bdv$
  computes the vector  ${\mathbf{s}''}^{(i^\dagger)}$ as
  \begin{eqnarray} \label{sim-s-prime}
    {\mathbf{s}'' }^{(i^\dagger)}  = \mathbf{s}_0 - \sum_{k=1}^N \mathbf{R}_k \cdot \mathfrak{m}_k^{(i^\dagger)}  -  {\mathbf{s}' }^{(i^\dagger)}  \in \ZZ^{2m},
  \end{eqnarray}
  which satisfies $\mathbf{c}_M=\sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k^{(i^\dagger)} + \mathbf{D}_0 \cdot ({\mathbf{s}' }^{(i^\dagger)} + {\mathbf{s}'' }^{(i^\dagger)} ) $ and
  allows   returning $(\tau^{(i^\dagger)},\mathbf{v}^{(i^\dagger)},    {\mathbf{s}'' }^{(i^\dagger)}  )$  such that
  $(\tau^{(i^\dagger)},\mathbf{v}^{(i^\dagger)},  {\mathbf{s}' }^{(i^\dagger)} +  {\mathbf{s}'' }^{(i^\dagger)}  )$   satisfies the verification
  equation of the signature scheme. Moreover, we argue that, with noticeable probability, the integer
  vector ${\mathbf{s} }^{(i^\dagger)} ={\mathbf{s}' }^{(i^\dagger)} +  {\mathbf{s}'' }^{(i^\dagger)}$ will be accepted by the verification algorithm since the R\'enyi divergence
  between the simulated distribution of ${\mathbf{s}'' }^{(i^\dagger)}$ and its distribution in the real game will be sufficiently small.  Indeed, its distribution
  is now that of a Gaussian vector $D_{\ZZ^{2m},\sigma_0,\mathbf{z}^\dagger }$ centered in $$\mathbf{z}^\dagger = - \sum_{k=1}^N
  \mathbf{R}_k  \cdot  {\mathfrak{m}_k^{(i^\dagger)} }
  - {\mathbf{s}' }^{(i^\dagger)}  \in \ZZ^{2m} ,$$ whose  norm is at most $\| \mathbf{z}^\dagger \|_2 \leq N \sigma  ({2m})^{3/2}  + \sigma (2m)^{1/2}$. By choosing the standard deviation $\sigma_0$ to
  be at least
  $\sigma_0> N \sigma  (2m)^{3/2}  + \sigma (2m)^{1/2} $,  the R\'enyi divergence between  the simulated
  distribution  of ${\mathbf{s}'' }^{(i^\dagger)}$ (in \textsf{Game} $3$) and its real distribution (which is the one of \textsf{Game} $2$) can be kept constant: we have
  \begin{eqnarray} \label{r-bound}
    R_2( {\mathbf{s}'' }^{(i^\dagger),2} ||{\mathbf{s}'' }^{(i^\dagger),3} ) \leq \exp \big( 2\pi \cdot \frac{ \| \mathbf{z}^\dagger \|_2^2}{\sigma_0^2} \big) \leq \exp(2 \pi).
  \end{eqnarray}
  This ensures that, with noticeable
  probability, $(\tau^{(i^\dagger)},\mathbf{v}^{(i^\dagger)},  {\mathbf{s}  }^{(i^\dagger)}   )$ will pass the verification test and lead $\adv$ to eventually output a valid forgery.
  So, the success probability of $\adv$ in \textsf{Game} $3$ remains noticeable as (\ref{r-bound}) implies $\Pr[W_3] \geq \Pr[W_2]^2 / \exp(2\pi)$. 

  When $W_3$ occurs in \textsf{Game} $3$, $\bdv$ uses the matrices $(\mathbf{E}_0,\mathbf{E}_1)$ to extract a plain message-signature pair $\big((\mathfrak{m}_1^\star,\ldots,\mathfrak{m}_N^\star),(\tau^\star,\mathbf{v}^\star,\mathbf{s}^\star) \big)$ from the extractable commitments
  $\{ \mathbf{c}_k^\star\}_{k=1}^N$ $(\mathbf{c}_{\mathbf{v}_1}^\star,\mathbf{c}_{\mathbf{v}_2}^\star)$, $\mathbf{c}_{\tau}^\star$, $\mathbf{c}_{\mathbf{s}}^\star$ generated by $\adv$.
  At this point, two cases can be distinguished. First, if $\mathbf{c}_M \neq \sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k^\star + \mathbf{D}_0 \cdot \mathbf{s}^\star \bmod q$, then algorithm
  $\bdv$ can
  find a short vector of $\Lambda_q^{\perp}(\bar{\mathbf{A}}_1)=\Lambda_q^{\perp}( {\mathbf{D}})$  exactly as in the proof of Lemma~\ref{le:lwe-gs-type-II-attacks}.  In the event that $\mathbf{c}_M = \sum_{k=1}^N \mathbf{D}_k \cdot \mathfrak{m}_k^\star + \mathbf{D}_0 \cdot \mathbf{s}^\star $,
  $\bdv$ can use the fact that  the collision $\mathbf{c}_M = \sum_{k=1}^N \mathbf{D}_k \cdot {\mathfrak{m}_k^{(i^\dagger)} } + \mathbf{D}_0 \cdot {\mathbf{s}^{(i^\dagger)} }  $  allows computing
  $$ \mathbf{w}=   \mathbf{s}^\star -{\mathbf{s}^{(i^\dagger)}}  + \sum_{k=1}^N \mathbf{R}_k \cdot \left(\mathfrak{m}_k^\star - \mathfrak{m}_k^{(i^\dagger)} \right)  ~ \in \ZZ^{2m} ,  $$
  which belongs to   $\Lambda_q^{\perp}(\mathbf{D}_0)$ and has   norm $\| \mathbf{w} \|_2 \leq N \sigma (2m)^{3/2} + 4 \sigma_1 m^{3/2}  $. Moreover, it
  is non-zero with overwhelming probability. Indeed, there exists at least one $k \in [1,N]$ such that  $\mathfrak{m}_k^{(i^\dagger)} \neq \mathfrak{m}_k^\star$. Let us assume w.l.o.g.
  that they 	differ in their first two bits where  $\mathfrak{m}_k^{(i^\dagger)}$ contains a $0$  and  $\mathfrak{m}_k^\star$ contains a $1$ (recall that each bit $b$
  is encoded as $(\bar{b},b)$ in both messages).
  This implies that $ {\mathbf{s}'' }^{(i^\dagger)} $ (as computed in (\ref{sim-s-prime})) does not depend on the first column of $\mathbf{R}_k$ but $\mathbf{w}$ does.
  Hence, given that the columns of $\mathbf{R}_k$ have at least $n$ bits of min-entropy conditionally on $\mathbf{D}_k =\mathbf{D}_0 \cdot \mathbf{R}_k$, the vector
  $\mathbf{w} \in \ZZ^{2m}$ is unpredictable to the adversary.

  Due to the definition of $\mathbf{D}_0 \in \ZZ_q^{2n \times 2m}$ in (\ref{def-D0}), we finally note that
  $\mathbf{w} \in \ZZ^{2m}$ is also a short  non-zero vector of $\Lambda_q^{\perp}(\bar{\mathbf{A}})$.

  \begin{itemize}
    \item If $coin=2$, $\bdv$ faithfully generates $\mathsf{par}$ and $PK$, but it retains the extraction trapdoor $(\mathbf{E}_0,\mathbf{E}_1)$ associated with the dual Regev public keys
      $(\mathbf{G}_0,\mathbf{G}_1)$. Note that $\adv$ can break the soundness of the proof system by either: (i) Generating ciphertexts
      $\{\mathbf{c}_k\}_{k=1}^N$ and $\mathbf{c}_{s'}$ that do not encrypt an opening of $\mathbf{c}_{\mathfrak{m}}$ in the signature issuing protocol; (ii) Generating ciphertexts
      $\{\mathbf{c}_k\}_{k=1}^N$, $\mathbf{c}_{\tau}$, $\mathbf{c}_{\mathbf{v}_1}$, $\mathbf{c}_{\mathbf{v}_2}$ and $\mathbf{c}_{s}$ that do not encrypt a valid signature in the $\mathsf{Prove}$ protocol.
      In either case, the reduction $\bdv$ is able to detect the event by decrypting dual Regev ciphertext using $(\mathbf{E}_0,\mathbf{E}_1)$ and create a breach in the
      soundness of the argument system.
  \end{itemize}

  It it easy to see that, since $coin \in \{0,1,2 \}$ is chosen independently of $\adv$'s view, it turns out to be correct with probability $1/3$. As a consequence, if $\adv$'s  advantage
  is non-negligible, so is $\bdv$'s.
\end{proof}

\begin{theorem} \label{anon-cred}
The scheme provides anonymity under the $\mathsf{LWE}_{n,q,\chi}$ assumption.
\end{theorem}

\begin{proof}
  The proof is rather straightforward and consists of a sequence of three games.
  \medskip

  \begin{description}
    \item[\textsf{Game} 0:] This is the real game. Namely, the adversary is given common public parameters $\mathsf{par}$ and comes up with a public key $PK$ of its own.
      The adversary can run oblivious signing protocols with honest users. At each query, the adversary chooses a user index $i$ and triggers an execution of the signing protocol
      with the challenger emulating the honest users. At some point, the adversary chooses some user index $i^\star$ for which the execution of the signing protocol ended successfully.
      At this point, the challenger $\bdv$   runs the real $\mathsf{Prove}$ protocol on behalf of user $i$.   At the end of the game, the adversary outputs
      a bit $b' \in \{0,1\}$. We define $W_0$ to be the event that
      $b'=1$.
      \smallskip

    \item[\textsf{Game} 1:] This game is like  \textsf{Game} $0$ with the difference that, at each execution of the $\mathsf{Prove}$ protocol, the challenger runs the zero-knowledge
      simulator of the interactive proof system. The latter simulator uses either a trapdoor hidden in the common reference string (if Damg\aa rd's technique \cite{Dam00} is used) or
      proceeds by programming the random oracle which allows implementing the Fiat-Shamir heuristic. In either case, the statistical zero-knowledge property ensures that the
      adversary cannot distinguish \textsf{Game} $1$ from \textsf{Game} $0$ and $|\Pr[W_1] - \Pr[W_0] | \in \mathsf{negl}(\lambda)$.
      \smallskip

    \item[Game 3:]  This game is like \textsf{Game} $1$ except that, at each execution of the $\mathsf{Prove}$ protocol, the ciphertexts $\{\mathbf{c}_k\}_{k=1}^N$, $\mathbf{c}_s$, $\mathbf{c}_{\tau}$,
      and $\mathbf{c}_{\mathbf{v}_1}$, $\mathbf{c}_{\mathbf{v}_2}$ encrypt random messages instead of the actual witnesses.  The semantic security of the dual Regev cryptosystem ensures that,
      under the $\LWE_{n,q,\chi}$ assumption, the adversary is unable to see the difference. Hence, we have $|\Pr[W_2] - \Pr[W_1]| \leq \mathbf{Adv}_{\bdv}^{\mathsf{LWE}}(\lambda)$.
  \end{description}
  \medskip

  In \textsf{Game} $2$, we can notice that the adversary is interacting with a simulator that emulates the user in the $\mathsf{Prove}$ protocol \textit{without} using
  any message-signature pair. We thus conclude that, under the $\LWE_{n,q,\chi}$ assumption, $\adv$'s view cannot distinguish a real proof of signature possession from a simulated proof
  produced without any witness.
\end{proof}

\section{A Dynamic Lattice-Based Group Signature} \label{see:lwe-gs-desc}

In this section, the signature scheme   of Section \ref{se:gs-lwe-sigep} is used to design a group signature for dynamic groups using the syntax and the security model of Kiayias and Yung \cite{KY06}, which is recalled in \cref{sse:gs-definitions}.

In the notations hereunder, for any positive integers $\mathfrak{n}$, and $q \geq 2$, we define the ``powers-of-2'' matrix $\mathbf{H}_{\mathfrak{n} \times \mathfrak{n}\lceil\log q\rceil} \in \ZZ_q^{\mathfrak{n} \times  \mathfrak{n}\lceil\log q\rceil}$ to be:
\begin{eqnarray*}
 \mathbf{H}_{\mathfrak{n} \times \mathfrak{n} \lceil\log q\rceil }  &=& \mathbf{I}_{\mathfrak{n}}  \otimes  [1 \mid 2 \mid 4 \mid \ldots \mid 2^{\lceil\log q\rceil-1} ] .
\end{eqnarray*}
Also, for each vector $\mathbf{v} \in \ZZ_q^{\mathfrak{n}}$, we define $\textsf{bin}(\mathbf{v}) \in \{0,1\}^{\mathfrak{n}\lceil\log q\rceil}$ to be the vector obtained by replacing each entry of $\mathbf{v}$ by its binary expansion.
Hence, we have $\mathbf{v}=\mathbf{H}_{\mathfrak{n} \times \mathfrak{n}\lceil\log q\rceil} \cdot \textsf{bin}(\mathbf{v})$ for any $\mathbf{v} \in \ZZ_q^{\mathfrak{n}}$.

In our scheme,  each   group membership certificate is a
signature generated by the group manager on the user's public key.    Since the group manager only needs to sign known (rather than committed) messages, we can
use a simplified version of the signature, where the chameleon hash function does not need to choose
 the discrete Gaussian vector $\mathbf{s}$ with a larger standard deviation than other vectors.

A key component of the scheme is the two-message joining protocol whereby the group manager admits new group members by signing their public key. The first message is sent by
the new user $\mathcal{U}_i$ who samples a membership secret consisting of a short vector $\mathbf{z}_i \sample D_{\ZZ^{4m},\sigma}$ (where $m= 2n \lceil\log q\rceil$), which is used to compute a
 syndrome $\mathbf{v}_i = \mathbf{F}  \cdot \mathbf{z}_i \in \ZZ_q^{4n}$  for some public matrix $\mathbf{F} \in  \ZZ_q^{4n \times 4m} $. This syndrome $\mathbf{v}_i \in \ZZ_q^{4n}$  must be signed by  $\mathcal{U}_i$ using his long term secret key $\mathsf{usk}[i]$ (as in
\cite{KY06,BSZ05}, we assume that each user has a long-term key $\mathsf{upk}[i]$ for a digital signature, which is registered in some PKI) and will uniquely
identify $\mathcal{U}_i$.
  In order to    generate  a membership certificate for    $\mathbf{v}_i \in \ZZ_q^{4n}$, the group manager $\mathsf{GM}$ signs its binary expansion
	$\mathsf{bin}(\mathbf{v}_i) \in \{0,1\}^{4n \lceil \log q \rceil }$ using the   scheme of Section \ref{se:gs-lwe-sigep}.
  
  Equipped with his membership
	certificate   $(\tau,\mathbf{d},\mathbf{s}) \in \{0,1\}^\ell \times \ZZ^{2m} \times \ZZ^{2m}$, the new group member $\mathcal{U}_i$ can  sign a message using a Stern-like protocol for
	demonstrating his  knowledge of 
	 a valid  certificate for which he also knows the secret key associated with the certified public key $\mathbf{v}_i \in \ZZ_q^{4n}$. This boils down to
	providing evidence that the membership certificate is a valid signature on some binary message $\mathsf{bin}(\mathbf{v}_i) \in \{0,1\}^{4n \lceil \log q \rceil }$
	for which he also knows a short  $\mathbf{z}_i \in \ZZ^{4m}$
	 such that
  $  \mathbf{v}_i = \mathbf{H}_{4n \times 2m} \cdot \textsf{bin}(\mathbf{v}_i)    = \mathbf{F} \cdot \mathbf{z}_i \in \mathbb{Z}_q^{4n}$.

	Interestingly, the process does not require any proof of knowledge of the membership secret $\mathbf{z}_i$ during the joining phase, which is round-optimal. Analogously to the Kiayias-Yung technique \cite{KY05} and constructions based on structure-preserving signatures
		\cite{AFG+10}, the joining protocol thus remains secure in environments where many users want
		to register at the same time in concurrent sessions.

   We remark that a similar Stern-like protocol  could also be directly used to prove knowledge of a Boyen signature \cite{Boy10} on a binary expansion of the
  user's syndrome	$\mathbf{v}_i \in \ZZ_q^{4n}$ while preserving the user's ability to prove knowledge of a short $\mathbf{z}_i \in \ZZ^{4m}$ such that $\mathbf{F}  \cdot \mathbf{z}_i =
  \mathbf{v}_i \bmod q$. However, this would require considerably longer private keys containing $ 4n \cdot \log q$ matrices $\{\mathbf{A}_j\}_{j=0}^\ell$ of dimension $n \times
  m$ each (i.e., we would need $\ell= \Theta(n \cdot \log q)$). In contrast, by using the signature scheme of Section \ref{se:gs-lwe-sigep}, we only need the group public key
  $\mathcal{Y}$ to contain  $\ell=\log N_{\mathsf{gs}}$ matrices in $\ZZ_q^{n \times m}$.  Since the number of users $N_{\mathsf{gs}}$ is polynomial, we have   $\log
  N_{\mathsf{gs}} \ll n$, which results in a much more efficient scheme.

	
	

\subsection{Description of the Scheme}

\begin{description}
\item[\textsf{Setup}$(1^\lambda,1^{N_{\mathsf{gs}}})$:] Given a security parameter $\lambda>0$
and the maximal expected number of group members ${N_{\mathsf{gs}}}=2^{\ell} \in
\mathsf{poly}(\lambda)$, choose lattice parameter
$n = \mathcal{O}(\lambda)$; prime modulus $q = \widetilde{\mathcal{O}}(\ell n^3)$; dimension $m =2  n\lceil \log q\rceil$; Gaussian parameter $\sigma = \Omega(\sqrt{n\log q}\log n)$; infinity norm bounds $\beta = \sigma\omega({\log m})$ and $B = \sqrt{n} \omega(\log n)$. Let $\chi$ be a $B$-bounded distribution.
Choose a hash function $H:\{0,1\}^*
\rightarrow \{1,2,3\}^t$ for some $t = \omega(\log n)$,
which will be modeled as a random oracle in the security analysis.
Then, do the following. \smallskip   \smallskip
\begin{itemize}
\item[1.] Generate a key pair for the signature   of Section \ref{desc-sig-protoc} for signing single-block messages. Namely, run $\TrapGen(1^n,1^m,q)$ to get~$\mathbf{A} \in
\ZZ_q^{n \times m}$ and a short basis $\mathbf{T}_{\mathbf{A}}$ of
$\Lambda_q^{\perp}(\mathbf{A})$, which  allows computing short vectors in $\Lambda_q^{\perp}(\mathbf{A})$ with  Gaussian parameter $\sigma$.
Next, choose      matrices
$\mathbf{A}_0,\mathbf{A}_1,\ldots,\mathbf{A}_{\ell},\mathbf{D} \sample (\ZZ_q^{n \times m})$, $ \mathbf{D}_0,\mathbf{D}_1 \sample (\ZZ_q^{2n \times 2m})$ and a vector $\mathbf{u} \sample (\ZZ_q^n)$.
\item[2.] Choose an additional random matrix $\mathbf{F} \sample (\ZZ_q^{4n \times 4m})$ uniformly. Looking ahead, this matrix will be used to ensure security against framing attacks.
\item[3.]
Generate a master key pair for the Gentry-Peikert-Vaikuntanathan IBE scheme
in its multi-bit variant. This key pair consists of a statistically uniform matrix
$\mathbf{B} \in \ZZ_q^{n \times m}$ and a short basis $\mathbf{T}_{\mathbf{B}} \in
\ZZ^{m \times m}$ of $\Lambda_q^{\perp}(\mathbf{B})$. This basis will allow us to compute GPV private keys with a
Gaussian parameter $\sigma_{\mathrm{GPV}} \geq \| \widetilde{\mathbf{T}}_{\mathbf{B}} \| \cdot
\sqrt{\log m}$.
\item[4.] Choose a one-time signature scheme $\Pi^\mathrm{OTS}=(\mathcal{G},\mathcal{S},\mathcal{V})$ and a hash function   $H_0:\{0,1\}^* \rightarrow \ZZ_q^{  n \times 2m}$,
that will be modeled as  random oracles.
\end{itemize}
The group public key is defined
as $$\mathcal{Y}\coloneqq \big( \mathbf{A}, ~
\{\mathbf{A}_j \}_{j=0}^{\ell},~\mathbf{B},  ~\mathbf{D},~ \mathbf{D}_0,~\mathbf{D}_1,~\mathbf{F}, ~\mathbf{u} , ~\Pi^\mathrm{OTS}, ~ H,~H_0  \big).$$
The opening authority's private key is $\mathcal{S}_{\OA}\coloneqq 
\mathbf{T}_{\mathbf{B}}   $ and the private key of the group manager consists of $\mathcal{S}_{\GM}\coloneqq  \mathbf{T}_{\mathbf{A}}$. The algorithm outputs
$\big( \mathcal{Y},\mathcal{S}_{\GM},\mathcal{S}_{\OA} \big)$.

\bigskip

\item[\textsf{Join}$^{(\mathsf{GM},\mathcal{U}_i)}$:] the group manager $\GM$ and  the prospective user $\mathcal{U}_i$    run the following  interactive protocol: \smallskip
$\left\langle \mathsf{J}_{\user}(\lambda,\mathcal{Y}),\mathsf{J}_{\GM}(\lambda,St,\mathcal{Y},\mathcal{S}_{\GM}) \right\rangle$
\begin{itemize}
\item[1.] $\mathcal{U}_i$ samples a  discrete Gaussian  vector $\mathbf{z}_{i} \leftarrow D_{\ZZ^{4m},\sigma}$ and computes $\mathbf{v}_{i} = \mathbf{F} \cdot \mathbf{z}_{i} \in \ZZ_q^{ 4n}$.
He sends the vector $\mathbf{v}_{i} \in \ZZ_q^{4n}$, whose binary representation $\mathsf{bin}(\mathbf{v}_i)$ consists of $4n\lceil\log q\rceil = 2m$ bits, together with an ordinary digital signature $sig_i = \mathrm{Sign}_{\usk[i]}(\mathbf{v}_i)$ to $\GM$.
\item[2.] $\mathsf{J}_{\GM}$ verifies that $\mathbf{v}_i$ was not previously used by a registered user and that
$sig_i$ is a valid signature on   $ \mathbf{v}_i $ w.r.t. $\upk[i]$. It  aborts if this is not the case. Otherwise,  $\GM$   chooses a fresh $\ell$-bit identifier  $\mathsf{id}_i=\mathsf{id}_i[1]\ldots \mathsf{id}_i[\ell]
\in \{0,1\}^{\ell}$ and
uses  $\mathcal{S}_{\GM}=\mathbf{T}_{\mathbf{A}}$ to certify
$\mathcal{U}_i$ as a new group member. To this end, $\GM$
defines the matrix
\begin{eqnarray} \label{matr}
\mathbf{A}_{\mathsf{id}_i}=  \left[ \begin{array}{c|c}  \mathbf{A} ~& ~    \mathbf{A}_0 +
\sum_{j=1}^\ell \mathsf{id}_i[j] \mathbf{A}_j
\end{array} \right] \in  \ZZ_q^{ n  \times 2m}.
\end{eqnarray}
Then, $\GM$ runs $\mathbf{T}_{\mathsf{id}_i}' \leftarrow
\ExtBasis(\mathbf{A}_{\mathsf{id}_i},\mathbf{T}_{\mathbf{A}})$ to obtain a  short delegated basis
$\mathbf{T}_{\mathsf{id}_i}'$ of $\Lambda_q^{\perp}(\mathbf{A}_{\mathsf{id}_i}) \in  \ZZ^{ 2m  \times 2m }$.
Finally,  $\GM$ samples a short vector $\mathbf{s}_i \sample D_{\ZZ^{2m},\sigma }$ and  uses the obtained delegated basis $\mathbf{T}_{\mathsf{id}_i}' $ to compute a short vector
$\mathbf{d}_i = \begin{bmatrix} \mathbf{d}_{i,1} \\ \hline \mathbf{d}_{i,2} \end{bmatrix} \in \ZZ^{2m}$ such that
\begin{eqnarray} \nonumber
\mathbf{A}_{\mathsf{id}_i} \cdot \mathbf{d}_i    &=&     \left[ \begin{array}{c|c}  \mathbf{A} ~& ~    \mathbf{A}_0 +
\sum_{j=1}^\ell \mathsf{id}_i[j] \mathbf{A}_j
\end{array} \right] \cdot \mathbf{d}_i\\
\label{rel-cert} &=&  \mathbf{u}   +  \mathbf{D} \cdot \bit \bigl( \mathbf{D}_0 \cdot \textsf{bin}(\mathbf{v}_i)   + \mathbf{D}_1 \cdot \mathbf{s}_i \bigr)  \bmod q. \quad
\end{eqnarray}
The triple $(\mathsf{id}_i,\mathbf{d}_i,\mathbf{s}_i)$ is sent to $\mathcal{U}_i$.  Then,
$\mathsf{J}_{\user}$  verifies that the received $(\mathsf{id}_i,\mathbf{d}_i,\mathbf{s}_i)$ satisfies (\ref{rel-cert}) and that
$\| \mathbf{d}_i \|_\infty \leq \beta$, $\| \mathbf{s}_i \|_\infty  \leq \beta $. If these conditions are not satisfied, $\mathsf{J}_{\user}$  aborts.
Otherwise,
$\mathsf{J}_{\user}$  defines the membership
certificate as
$ \crt_{i }=( \mathsf{id}_i, \mathbf{d}_i,\mathbf{s}_i )$.
The    membership secret $\scr_{i }$ is defined to be   $\scr_i=\mathbf{z}_i \in \ZZ^{4m}$. $\mathsf{J}_{\GM}$ stores
$\transcript_i=(\mathbf{v}_i, \crt_i,  i,\mathsf{upk}[i],sig_i)$
in the database  $St_{trans}$ of joining transcripts. \smallskip \smallskip
\end{itemize}



\item[\textsf{Sign}$(\mathcal{Y},\crt_i,\scr_i ,M)$:] To sign  $M \in
\{0,1\}^*$ using   $\crt_i=(\mathsf{id}_i,\mathbf{d}_i,\mathbf{s}_i)$, where $\mathbf{d}_i=[ \mathbf{d}_{i,1}^T \mid \mathbf{d}_{i,2}^T ]^T \in \ZZ^{2m}$ and $\mathbf{s}_i \in \ZZ^{2m}$, as
well as the membership secret $\scr_i=\mathbf{z}_i \in \ZZ^{4m}$, the group
member $\mathcal{U}_i$ generates a one-time signature key pair $(\mathsf{VK},\mathsf{SK}) \leftarrow \mathcal{G}(n)$ and conducts the following steps. \smallskip

\begin{itemize}
\item[1.]  Compute $\mathbf{G}_0=H_0(\mathsf{VK}) \in \ZZ_q^{ n \times 2m}$  and use it as an  IBE public key to encrypt
$\textsf{bin}(\mathbf{v}_i) \in \{0,1\}^{2m}$, where $\mathbf{v}_i=\mathbf{F} \cdot \mathbf{z}_i \in \ZZ_q^{4n}$ is the syndrome of
$\scr_i=\mathbf{z}_i \in \mathbb{Z}^{4m}$ for the matrix $\mathbf{F}$. Namely, compute $ \mathbf{c}_{\mathbf{v}_i}  \in  \ZZ_q^m \times \ZZ_q^{2m}$ as
\begin{eqnarray} \label{enc1}
\mathbf{c}_{\mathbf{v}_i}=(\mathbf{c}_1,\mathbf{c}_2) &=&  \big( \mathbf{B}^T \cdot \mathbf{e}_0 + \mathbf{x}_1 ,~  \mathbf{G}_0^T \cdot \mathbf{e}_0 + \mathbf{x}_2 + \textsf{bin}(\mathbf{v}_i) \cdot \lfloor q/2 \rfloor  \big) \qquad
\end{eqnarray}
for  randomly chosen $\mathbf{e}_0  \sample \chi^n$, $\mathbf{x}_1 \sample \chi^m, \mathbf{x}_2  \sample \chi^{2m}   $.
Notice that, as in the construction of \cite{LNW15}, the columns of $\mathbf{G}_0$  can be interpreted as public keys for the multi-bit version
of the dual Regev encryption scheme.
\item[2.]   Run the protocol in Section~\ref{subsection:zk-for-group-signature}   to prove the knowledge of  $\mathsf{id}_i
\in \{0,1\}^{\ell}$,
vectors $\mathbf{s}_i  \in \ZZ^{2m}, \mathbf{d}_{i,1},\mathbf{d}_{i,2} \in \ZZ^{m},\mathbf{z}_i \in \ZZ^{4m}$ with infinity norm bound $\beta $; $\mathbf{e}_0  \in \ZZ^n$, $\mathbf{x}_1 \in \ZZ^m, \mathbf{x}_2 \in \ZZ^{2m} $ with infinity norm bound $B$
and $\textsf{bin}(\mathbf{v}_i) \in \{0,1\}^{2m},  \mathbf{w}_{i}  \in \{0,1\}^m$, that satisfy
\eqref{enc1}   as well as
\begin{eqnarray} \label{rel-deux}
\mathbf{A} \cdot \mathbf{d}_{i,1} +   \mathbf{A}_0 \cdot  \mathbf{d}_{i,2} +  \sum_{j=1}^{\ell} ( \mathsf{id}_i[j] \cdot \mathbf{d}_{i,2}) \cdot \mathbf{A}_j
- \mathbf{D}  \cdot    \mathbf{w}_i   = \mathbf{u} \in \ZZ_q^n
\end{eqnarray}
and

\begin{eqnarray} \label{eq:rel-3}
\left\{
\begin{array}{l}
\mathbf{H}_{2n \times m} \cdot  \mathbf{w}_{i}   =   \mathbf{D}_0 \cdot   \textsf{bin}(\mathbf{v}_i)  + \mathbf{D}_1 \cdot \mathbf{s}_i  \in \ZZ_q^{2n} \\
\mathbf{F} \cdot \mathbf{z}_i  =  \mathbf{H}_{4n \times 2m} \cdot  \textsf{bin}(\mathbf{v}_i)  \in \ZZ_q^{4n}.
\end{array}
\right.
\end{eqnarray}

The protocol is repeated $t = \omega(\log n)$ times  in parallel to achieve negligible soundness error, and then made non-interactive using the Fiat-Shamir
heuristic~\cite{FS86} as a triple $\pi_K=(
\{\mathsf{Comm}_{K,j}\}_{j=1}^t,\mathsf{Chall}_K,\{\mathsf{Resp}_{K,j}\}_{j=1}^t)$,
where $\mathsf{Chall}_K = H(M, \vk, \mathbf{c}_{\mathbf{v}_i},
\{ \mathsf{Comm}_{K,j}\}_{j=1}^t) \in \{1,2,3\}^t$

\item[3.] Compute a one-time signature $sig=\mathcal{S}(\mathsf{SK},(\mathbf{c}_{\mathbf{v}_i} , \pi_K))$. \smallskip


\end{itemize}
Output the signature that consists of

\begin{equation} \label{eq:sig-final} \Sigma=\big( \mathsf{VK} ,\mathbf{c}_{\mathbf{v}_i},  \pi_K,sig \big).
\end{equation}

\smallskip

\item[\textsf{Verify}$(\mathcal{Y},M,\Sigma)$:] Parse the signature $\Sigma$ as in
(\ref{eq:sig-final}). Then, return $1$ if and only if:
(i) $\mathcal{V}(\mathsf{VK},(\mathbf{c}_{\mathbf{v}_i},\mathbf{c}_{\mathbf{s}_i},\mathbf{c}_{\mathsf{id}},\pi_K),sig)=1$;
(ii) The proof   $\pi_K$ properly verifies. \smallskip %Otherwise, return $0$. \smallskip

\item[\textsf{Open}$(\mathcal{Y},\mathcal{S}_{\OA},M,\Sigma)$:] Parse~$\mathcal{S}_{\OA}$ as~$
\mathbf{T}_{\mathbf{B}} \in \ZZ^{m \times m}$ and $\Sigma$ as
in~(\ref{eq:sig-final}).   \smallskip
\begin{itemize}
\item[1.]
Compute $\mathbf{G}_0=H_0(\mathsf{VK}) \in \ZZ_q^{n \times 2m}$. Then, using  $\mathbf{T}_{\mathbf{B}}$
to compute a small-norm matrix
$\mathbf{E}_{0,\mathsf{VK}} \in \ZZ^{m \times 2m }$    such that $   \mathbf{B} \cdot \mathbf{E}_{0,\mathsf{VK}}  = \mathbf{G}_0 \bmod q  $.
\item[2.]  Using $\mathbf{E}_{0,\mathsf{VK}}$, decrypt    $\mathbf{c}_{\mathbf{v}_i}$  to obtain a  string $\textsf{bin}(\mathbf{v} ) \in \{0,1\}^{2m}$
(i.e., by computing $\lfloor (\mathbf{c}_2 - \mathbf{E}_{0,\mathsf{VK}}^T \cdot \mathbf{c}_1) / (q/2) \rceil$). \smallskip
\item[3.] Determine whether the     $\textsf{bin}(\mathbf{v} ) \in \{0,1\}^{2m} $ obtained at step~2  corresponds to a vector $\mathbf{v} = \mathbf{H}_{4n \times 2m} \cdot \textsf{bin}(\mathbf{v} ) \bmod q$ that appears in a record   $\transcript_i=(\mathbf{v} , \crt_i,  i,\mathsf{upk}[i],sig_i)$ of  the database  $St_{trans}$ for some   $i$. If so,
output the corresponding $i$ (and, optionally, $\mathsf{upk}[i]$). Otherwise, output $\perp$.
\end{itemize}
\end{description}

We remark that the scheme readily extends to provide a mechanism whereby the opening authority can efficiently prove that signatures were correctly opened at each opening operation.
The difference between the dynamic group signature models suggested by Kiayias and Yung \cite{KY06} and Bellare \textit{et al.} \cite{BSZ05} is that, in  the latter, the opening authority
 ($\mathsf{OA}$) must be  able to convince a judge that the $\mathsf{Open}$ algorithm was run correctly.
 Here, such a mechanism can be realized using the techniques of public-key encryption with non-interactive opening \cite{DHKT08}. Namely,  since
$\textsf{bin}(\mathbf{v}_i)$ is encrypted using an IBE scheme for the identity $\vk$, the $\mathsf{OA}$ can simply reveal the decryption matrix $\mathbf{E}_{0,\mathsf{VK}}  $,
that satisfies $\mathbf{B} \cdot \mathbf{E}_{0,\vk} = \mathbf{G}_0 \bmod q$  (which corresponds to the verification of  a GPV signature) and allows the verifier to perform step 2 of the opening
algorithm himself. The resulting construction is easily seen to satisfy the notion of opening soundness of Sakai \textit{et al.} \cite{SSE+12}.

\subsection{Efficiency and Correctness}
\textsc{Efficiency.} The given dynamic group signature scheme can be implemented in polynomial time. The group public key has total bit-size $\mathcal{O}(\ell n m \log q) = \widetilde{\mathcal{O}}(\lambda^2)\cdot \log N_\textsf{gs}$. The secret signing key of each user consists of a small constant number of low-norm vectors, and has bit-size $\widetilde{\mathcal{O}}(\lambda)$.

The size of each group signature is largely dominated by that of the non-interactive argument $\pi_K$, which is obtained from the Stern-like protocol of Section~\ref{subsection:zk-for-group-signature}. Each round of the protocol has communication cost $\widetilde{\mathcal{O}}(m \cdot \log q) \cdot \log N_\textsf{gs}$. Thus, the bit-size of $\pi_K$ is $t\hspace*{-1pt}\cdot\hspace*{-1pt} \widetilde{\mathcal{O}}(m \hspace*{-1pt}\cdot\hspace*{-1pt} \log q) \hspace*{-1pt}\cdot\hspace*{-1pt} \log N_\textsf{gs} = \widetilde{\mathcal{O}}(\lambda)\hspace*{-1pt}\cdot \hspace*{-1pt}\log N_\textsf{gs}$. This is also the asymptotic bound on the size of the group signature.


\smallskip
\textsc{Correctness.} The correctness of algorithm \textsf{Verify}$(\mathcal{Y},M,\Sigma)$ follows from the facts that every certified group member is able to compute valid witness vectors satisfying equations~(\ref{enc1}), (\ref{rel-deux}) and (\ref{eq:rel-3}), and that the underlying argument system is perfectly complete. Moreover, the scheme parameters are chosen so that the GPV IBE~\cite{GPV08} is correct, which implies that algorithm \textsf{Open}$(\mathcal{Y},\mathcal{S}_{\OA},M,\Sigma)$ is also correct.


\subsection{Security Analysis}

Due to the fact that the number of public matrices $\{\mathbf{A}_j\}_{j=0}^\ell$ is only logarithmic in ${N_{\mathsf{gs}}}=2^\ell$ instead of being linear in the security parameter $\lambda$,
the proof of security against misidentification attacks (as defined in \cref{sse:gs-sec-notions}) cannot rely on the security of our signature scheme in a modular manner.
 The reason is that, at each run of the $\mathsf{Join}$ protocol, the group manager maintains a state and, instead of choosing the $\ell$-bit identifier $\mathsf{id}$ uniformly in
$\{0,1\}^{\ell}$, it chooses an identifier that has not been used yet. Since $\ell \ll \lambda$ (given that ${N_{\mathsf{gs}}}=2^\ell$ is polynomial in $\lambda$), we thus have
to prove security from scratch. However, the strategy of the reduction is exactly the same as in the security proof of the signature scheme.


\begin{theorem} \label{traceability-thm}
The scheme is secure against misidentification attacks under the $\SIS_{n,2m,q,\beta'}$ assumption, for $\beta' \hspace*{-1pt}=\hspace*{-1pt} \mathcal{O}(\ell \sigma^2 m^{3/2})$.
\end{theorem}

\begin{proof}
  We prove that   any adversary $\adv$ with non-negligible success probability $\varepsilon$  implies an algorithm $\bdv$ solving the \textsf{SIS} problem
  in the random oracle model.

  Let $\adv$ be such a $\ppt$ adversary.  
  We then build a $\ppt$ reduction~$\bdv$ that uses the adversary~$\adv$ to
  solve~$\SIS_{n,2m,q,\beta'}$: specifically, $\bdv$ takes as input~$\bar{\mathbf{A}} = \begin{bmatrix} \bar{\mathbf{A}}_1 | \bar{\mathbf{A}}_2 \end{bmatrix} \in
  \Zq^{n \times 2m}$, where $\bar{\mathbf{A}}_1,\bar{\mathbf{A}}_2 \in \Zq^{n \times m}$,  and finds $\mathbf{w} \in
  \Lambda_q^{\perp}(\bar{\mathbf{A}})$ with~$0 < \|\mathbf{w}\| \leq \beta'$.
  \medskip


  \noindent \textbf{Initialization.}  Algorithm~$\bdv$ first chooses a random    $coin \sample
  U(\{0,1,2\})$ as a guess for the kind of misidentification attack that $\adv$ will mount. Also, $\bdv$ 	
  chooses a random $\ell$-bit string $\mathsf{id}^\dagger \sample (\{0,1\}^\ell)$.
  In
  addition, $\bdv$ 	
  samples~$i^\star
  \sample ([1,Q_a])$.   \\
  \indent
  Looking ahead, $coin=0$ corresponds to the case where, after repeated executions of $\adv$, the knowledge extractor of the proof system
  reveals witnesses containing a new  identifier $\mathsf{id}^\star \in \{0,1\}^\ell$ that does not belong to any user in $U^a$.
  In this case, $\bdv$ will be able to exploit $\adv$'s forgery when $\mathsf{id}^\star=\mathsf{id}^\dagger$.
  The   case $coin=1$ corresponds to  $\bdv$'s expectation that the knowledge extractor will obtain the identifier $ \mathsf{id}^\star = \mathsf{id}^\dagger$ of a  group member in
  $ U^a$ (i.e., a group member that was legitimately introduced at the $i^\star$-th $\mathcal{Q}_{\ajoin}$-query, for some $i^\star \in \{1,\ldots,Q_a\}$, where the identifier
  $\mathsf{id}^\dagger$ is used by $\mathcal{Q}_{\ajoin}$),
  but  $\textsf{bin}( \mathbf{v}^\star ) \in \{0,1\}^{2m}$ (which is encrypted in in $\mathbf{c}_{\mathbf{v}_i}^\star$ as part of the forgery $\Sigma^\star$)  and the extracted $\mathbf{s}^\star \in \ZZ^{2m}$    are such that $ \bit \bigl( \mathbf{D}_0 \cdot \textsf{bin}( \mathbf{v}^\star ) + \mathbf{D}_1 \cdot \mathbf{s}^\star \bigr) \in \{0,1\}^m $
  does not match
  the string  $ \bit \bigl( \mathbf{D}_0 \cdot \textsf{bin}( \mathbf{v}_{i^\star} ) + \mathbf{D}_1 \cdot \mathbf{s}_{i^\star} \bigr) \in \{0,1\}^{2m} $ for which
  user $i^\star$ obtained a membership certificate at the $i^\star$-th $\mathcal{Q}_{\ajoin}$-query. When $coin=1$, the choice of $i^\star$ corresponds to  a guess that the knowledge
  extractor will reveal an $\ell$-bit identifier that coincides with the identifier $\mathsf{id}^\dagger$ assigned to the user introduced at the $i^\star$-th $\mathcal{Q}_{\ajoin}$-query.
  The last case $coin=2$ corresponds to $\bdv$'s expectation that decrypting $\mathbf{c}_{\mathbf{v}_i}^\star$ (which is part of  $\Sigma^\star$) and running
  the knowledge extractor on $\adv$ will uncover vectors $\textsf{bin}( \mathbf{v}^\star ) \in \{0,1\}^{2m}$, $\mathbf{w}^\star \in \{0,1\}^m$ and $\mathbf{s}^\star \in \ZZ^{2m}$
  such that $\mathbf{w}^\star= \textsf{bin}(\mathbf{D}_0 \cdot \textsf{bin}(\mathbf{v}^\star) + \mathbf{D}_1 \cdot \mathbf{s}^\star )$ and
  \begin{eqnarray} \label{collide}
    \bit \bigl( \mathbf{D}_0 \cdot \textsf{bin}( \mathbf{v}^\star ) + \mathbf{D}_1 \cdot \mathbf{s}^\star \bigr) = \bit \bigl( \mathbf{D}_0 \cdot \textsf{bin}( \mathbf{v}_{i^\star} ) + \mathbf{D}_1 \cdot \mathbf{s}_{i^\star} \bigr)
  \end{eqnarray}
  but $(\textsf{bin}( \mathbf{v}^\star ), \mathbf{s}^\star) \neq  ( \textsf{bin}( \mathbf{v}_{i^\star} ), \mathbf{s}_{i^\star}  ) $, where $ \mathbf{v}_{i^\star} \in \Zq^{4n}$ and $\mathbf{s}_{i^\star} \in \ZZ^{2m}$ are the vectors
  involved in the  $i^\star$-th $\mathcal{Q}_{\ajoin}$-query.
  \\	
  \indent
  Depending on $coin \in \{0,1,2\}$, the group public key $\mathcal{Y}$ is
  generated using   different methods.  \smallskip

  \noindent $\bullet$ If $coin=0$, algorithm~$\bdv$ first randomly  chooses $\mathsf{id}^\dagger \sample (\{0,1\}^\ell)$ as a guess for the $\ell$-bit string
  that will be revealed by the knowledge extractor of the proof system after repeated executions of the adversary $\adv$.
  Then, it  runs
  $\TrapGen(1^n,1^m,q)$ to obtain $\mathbf{C} \in \Zq^{n \times m}$ and a
  basis $\mathbf{T}_{\mathbf{C}}$ of~$\Lambda_q^{\perp}(\mathbf{C})$ with
  $\|\widetilde{\mathbf{T}_{\mathbf{C}}}\| \leq \bigO(\sqrt{n \log q})$. Then,
  it chooses~$\ell+2$ matrices~$ \mathbf{Q}_0,\ldots,\mathbf{Q}_{\ell},\mathbf{Q}_D \in \ZZ^{m \times m}$,
  each matrix having its columns sampled independently from~$D_{\ZZ^m,\sigma}$.  Then,  $\bdv$ defines the matrices   $\{ \mathbf{A}_i\}_{i=0}^{\ell}$ as
  \begin{eqnarray*}
    \left\{
      \begin{array}{ll}
        \mathbf{A}_0 =  \bar{\mathbf{A}}_1 \cdot  \mathbf{Q}_0 +  (\sum_{i=1}^{\ell} {\mathsf{id}^\dagger[i]}) \cdot
        \mathbf{C} \\
        \mathbf{A}_j = \bar{\mathbf{A}}_1 \cdot  \mathbf{Q}_i + (-1)^{\mathsf{id}^{\dagger}[j]} \cdot
        \mathbf{C}, \quad \text{ for  }  j \in
        [1,\ell]. \\
        \mathbf{D} = \bar{\mathbf{A}}_1 \cdot \mathbf{Q}_D
      \end{array}
    \right.
  \end{eqnarray*}
  It also defines $\mathbf{A}=\bar{\mathbf{A}}_1$.
  Next, it samples a vector $\mathbf{e}_u \sample D_{\ZZ,\sigma}^m$ and computes a syndrome $\mathbf{u} =    \bar{\mathbf{A}}_1 \cdot  \mathbf{e}_u \in  \Zq^n$. It picks $\mathbf{D}_0,\mathbf{D}_1
  \sample (\Zq^{2n \times 2m})$ at random and  also faithfully generates  the GPV master key pair $(\mathbf{B},\mathbf{T}_{\mathbf{B}})$ as in Step~3 of the real setup algorithm.  The group
  public key $\mathcal{Y}=\big(\mathbf{A},\{\mathbf{A}_j \}_{j=0}^{\ell}, \mathbf{B}, \mathbf{D},\mathbf{D}_0,\mathbf{D}_1,\mathbf{F}, \mathbf{u},\mathcal{OTS},H,H_0  \big)$
  is finally given to~$\adv$. \\
  \indent Note  that, for each $\mathsf{id} \neq \mathsf{id}^\dagger$, we have
  \begin{eqnarray} \nonumber
    \mathbf{A}_{\mathsf{id}} &=& \left[
      \begin{array}{c|c}   \bar{\mathbf{A}}_1 ~&~  \mathbf{A}_0 +
        \sum_{i=1}^\ell \mathsf{id}[i] \mathbf{A}_i
    \end{array} \right] \\ \nonumber   & = & \left[
      \begin{array}{c|c}  \bar{\mathbf{A}}_1  ~&~   \bar{\mathbf{A}}_1 \cdot (\mathbf{Q}_0 +
        \sum_{i=1}^{\ell} \mathsf{id}[i] \mathbf{Q}_i) + (
        \sum_{i=1}^{\ell} \mathsf{id}^\dagger [i]  +(-1)^{\mathsf{id}^\dagger[i]} \mathsf{id}[i])\cdot  \mathbf{C}
    \end{array} \right] \\  \label{sim-matr}   &=&
    \left[
      \begin{array}{c|c}    \bar{\mathbf{A}}_1  ~&~   \bar{\mathbf{A}}_1 +  h_{\mathsf{id}} \cdot \mathbf{C}
    \end{array} \right]
  \end{eqnarray}
  where $h_{\mathsf{id}} \in [1,\ell]$ denotes the Hamming distance between
  the identifiers $\mathsf{id}$ and $\mathsf{id}^\dagger$. Since $q>\ell$, we have
  $h_{\mathsf{id}_j} \neq 0 \bmod q$ whenever $\mathsf{id}_j \neq \mathsf{id}^\dagger$, so
  that algorithm $\bdv$ is able to compute (see~\cite[Se.~4.2]{ABB10},
    using the basis~$\mathbf{T}_{\mathbf{C}}$ of~$\Lambda_q^{\perp}(\mathbf{C})$ and
  the refined $\GPVSample$ of Lemma~\ref{le:GPV}) a basis
  $\mathbf{T}_{\mathsf{id}}$ of $\Lambda_q^{\perp}(\mathbf{A}_{\mathsf{id}})$
  with~$\|\widetilde{\mathbf{T}_{\mathsf{id}}}\| \leq \Omega(\sqrt{n\log
  q\log n})$.  In contrast,
  algorithm~$\bdv$ lacks a trapdoor for $\mathbf{A}_{\mathsf{id}^\dagger}$ as the
  latter only depends on $\mathbf{A}$ and $\{\mathbf{Q}_k\}_{k=0}^{\ell}$.
  Observe that, since the columns of the matrices~$\{\mathbf{Q}_k\}_{k=0}^\ell$ are sampled
  from~$D_{\ZZ^m,\sigma}$, the
  matrices~$ \mathbf{A}_0,\ldots,\mathbf{A}_{\ell}$ are within
  statistical distance~$2^{-\Omega(m)}$ of~$U(\Zq^{n \times m})$.
  \smallskip


  \noindent $\bullet$ If $coin=1$, algorithm~$\bdv$   sets up $\mathcal{Y}$ by defining
  $\mathbf{D}=\bar{\mathbf{A}}$. Initially, $\bdv$
  chooses $Q_a-1$ distinct strings $\mathsf{id}_1, \ldots,\mathsf{id}_{i^\star-1}, \mathsf{id}_{i^\star+1},\ldots,\mathsf{id}_{Q_a} \in \{0,1\}^\ell$ such that, for each $i \in [1,Q_a] \backslash \{i^\star\}$, $\mathsf{id}_i$ will be embedded in the membership certificate
  returned in the $i$-th $\mathcal{Q}_{\ajoin}$-query.  Let also $\mathsf{id}^\dagger=\mathsf{id}_{i^\star}$ be the $\ell$-bit identifier
  that will be used in the $i^\star$-th query.
  The reduction  $\bdv$ picks random $h_0,h_1,\ldots,h_\ell \in \Zq$ under the constraints
  \begin{eqnarray*}
    h_{\mathsf{id}^\dagger} =  h_0 + \sum_{j=1}^\ell  \mathsf{id}^\dagger[j] \cdot h_j &=& 0 \bmod q  \\
    h_{\mathsf{id}_i} = h_0 + \sum_{j=1}^\ell \mathsf{id}_i[j] \cdot h_j & \neq & 0 \bmod q   \qquad \qquad i \in \{1,\ldots,Q_a\} \setminus \{i^\dagger\}
  \end{eqnarray*}
  Next, $\bdv$ runs $(\mathbf{C},\mathbf{T}_{\mathbf{C}}) \leftarrow \mathsf{TrapGen}(1^n,1^m,q)$, $(\mathbf{D}_1,\mathbf{T}_{\mathbf{D}_1}) \leftarrow \mathsf{TrapGen}(1^{2n},1^{2m},q)$ so as to obtain  statistically random  matrices $\mathbf{C} \in \Zq^{n \times m}$, $ \mathbf{D}_1 \in \Zq^{2n \times 2m}$ together with
  trapdoors $\mathbf{T}_{\mathbf{C}}  \in \ZZ^{m \times m} $, $\mathbf{T}_{\mathbf{D}_1} \in \ZZ^{2m \times 2m}$ consisting of  short bases of $\Lambda_q^{\perp}(\mathbf{C})$ and $\Lambda_q^{\perp}(\mathbf{D}_1)$, respectively. Then,
  $\bdv$
  picks a  random $\mathbf{D}_0 \sample (\Zq^{2n \times 2m})$ and re-randomizes $\mathbf{D}=\bar{\mathbf{A}}_1 \in \Zq^{n \times m}$ using Gaussian matrices
  $\mathbf{S},\mathbf{S}_0,\mathbf{S}_1,\ldots,\mathbf{S}_{\ell} \sample \ZZ^{m \times m}$  whose columns are sampled from the distribution $D_{\ZZ^m,\sigma}$.
  Namely, from  $\mathbf{D} =\bar{\mathbf{A}}_1 $, $\bdv$
  defines
  \begin{eqnarray} \nonumber
    \mathbf{A} &=&  \bar{\mathbf{A}}_1 \cdot \mathbf{S} \\ \label{setup-sig2}
    \mathbf{A}_0 &=&  \bar{\mathbf{A}}_1 \cdot \mathbf{S}_0 + h_0 \cdot \mathbf{C} \\ \nonumber
    \mathbf{A}_j &=&  \bar{\mathbf{A}}_1 \cdot \mathbf{S}_j + h_j \cdot \mathbf{C} \qquad \qquad \forall j \in \{1,\ldots,\ell\}  .
  \end{eqnarray}
  As part of the generation of
  $\mathcal{Y}$, the vector $\mathbf{u} \in \Zq^n$ is obtained by picking  short discrete Gaussian vectors
  $  \mathbf{d}_{i^\star,1}, \mathbf{d}_{i^\star,2} \sample D_{\ZZ^m,\sigma} $
  and computing
  \begin{eqnarray} \label{def-u}
    \mathbf{u}  =   [  \mathbf{A} ~\mid ~    \mathbf{A}_0 +
      \sum_{j=1}^\ell \mathsf{id}^\dagger[j] \mathbf{A}_j
    ] \cdot
    \begin{bmatrix}
      \mathbf{d}_{i^\star,1} \\ \hline  \mathbf{d}_{i^\star,2}
    \end{bmatrix}
    -   \mathbf{D} \cdot \textsf{bin}(\mathbf{c}_M),
  \end{eqnarray}
  where
  $\mathbf{c}_{M} \sample (\Zq^{2n})$ is a randomly chosen vector. Observe that, since $\mathbf{A}$ is statistically uniform over $\Zq^{n \times m}$ and $ \mathbf{d}_{i^\star,1}
  \sample D_{\ZZ^m,\sigma}$, the distribution of
  $\mathbf{u} $ is statistically close to $U(\Zq^n)$.
  \medskip

  \noindent $\bullet$ If $coin=2$, $\bdv$ picks $\bar{\mathbf{A}}' \sample (\Zq^{n \times 2m})$
  and  a random matrix $\mathbf{Q} \sample \ZZ^{2m \times 2m}$ whose columns are sampled from $D_{\ZZ^{2m},\sigma}$. These
  are used to define $$\mathbf{D}_0= \begin{bmatrix} \bar{\mathbf{A}} \\ \hline \bar{\mathbf{A}}'  \end{bmatrix} \in \Zq^{2n \times 2m} ,$$
  and $\mathbf{D}_1=\mathbf{D}_0 \cdot \mathbf{Q} \bmod q$, which is statistically close to $U(\Zq^{2n \times 2m})$. All other components of $\mathcal{Y}$ are obtained by faithfully running the setup algorithm. \medskip


  \indent For each value of $coin \in \{0,1,2\}$,  the group public key
  $$\mathcal{Y}=\big(\mathbf{A},\{\mathbf{A}_j \}_{j=0}^{\ell},\mathbf{B},\mathbf{D},\mathbf{D}_0,\mathbf{D}_1,\mathbf{F}, \mathbf{u},\mathcal{OTS},H,H_0 \big)$$  has a distribution which is statistically close to that of the real scheme and $\mathcal{Y}$ is  given to   $\adv$.

  \medskip


  \noindent \textbf{Queries.} The reduction~$\bdv$  starts interacting
  with the adversary~$\adv$ and the way it handles~$\adv$'s queries to the $\mathcal{Q}_{\ajoin}$ oracle depends on the value of~$coin \in \{0,1,2\}$. \smallskip \smallskip

  \noindent $\bullet$ If $coin=0$, answers $\mathcal{Q}_{\ajoin}$-queries as follows. When $\adv$ triggers an execution of the joining protocol, it chooses
  a syndrome $\mathbf{v}_{i} \in \Zq^n$.
  To answer the query, $\bdv$ chooses a fresh  $\ell$-bit identifier $\mathsf{id}_i \in \{0,1\}^\ell$ such that
  $\mathsf{id}_i \neq \mathsf{id}^\dagger$. If $\adv$ also provides a correct signature $sig_i$ such that
  $\mathrm{Verify}_{\mathsf{upk}[i]}(\mathbf{v}_{i},sig_i)=1$, $\bdv$ samples $\mathbf{s}_i \sample D_{\ZZ^{2m},\sigma}$ and uses the trapdoor $\mathbf{T}_{\mathbf{C}}$ to compute  a short vector
  $\mathbf{d}_i=[\mathbf{d}_{i,1}^T ~|~\mathbf{d}_{i,2}^T]^T \in \ZZ^{2m}$ such that
  \begin{eqnarray} \label{sim-cert}
    \mathbf{A}_{\mathsf{id}_i} \cdot  \begin{bmatrix}  \mathbf{d}_{i,1} \\ \hline \mathbf{d}_{i,2} \end{bmatrix}  = \mathbf{u} + \mathbf{D} \cdot \bit \bigl( \mathbf{D}_0 \cdot \textsf{bin}(\mathbf{v}_{i}) +  \mathbf{D}_1 \cdot \mathbf{s}_i \bigr) ,
  \end{eqnarray}
  where $\mathbf{A}_{\mathsf{id}_i} \in \Zq^{n \times 2m}$ is the matrix in (\ref{sim-matr}). Note that $\bdv$ is able to compute such a vector using the $\mathsf{SampleRight}$
  algorithm of \cite{ABB10} (since the Hamming distance $h_{\mathsf{id}_i}$ between $\mathsf{id}_i$ and $\mathsf{id}^\star$ is non-zero).  The membership certificate
  $\crt_i= (\mathsf{id}_i,\mathbf{d}_i,\mathbf{s}_i)$  is then returned to $\adv$.
  \smallskip

  \noindent $\bullet$ If $coin=1$, algorithm~$\bdv$ responds each $\mathcal{Q}_{\ajoin}$-query depending on the index $i \in \{1,\ldots,Q_a\}$ of the query. Specifically,
  we distinguish two cases. \smallskip

  \begin{itemize}
    \item[-] If $i \neq i^\star$, $\bdv$ proceeds as in the previous case. Namely, it recalls the $\ell$-bit identifier $\mathsf{id}_i \in \{0,1\}^\ell$ (for which $\mathsf{id}_i \neq \mathsf{id}^\dagger$)
      that was chosen in the setup phase and samples a short vector $\mathbf{s}_{i} \sample D_{\ZZ^{2m},\sigma}$. If $\adv$ also provides a correct signature $sig_i$ such that
      $\mathrm{Verify}_{\mathsf{upk}[i]}(\mathbf{v}_{i},sig_i)=1$, generates a membership certificate $\crt_i$ for $\adv$ as in the case $coin=0$.
      Note that
      \begin{eqnarray} \nonumber
        \mathbf{A}_{\mathsf{id}_i} &=&  \left[
          \begin{array}{c|c}  \bar{\mathbf{A}} \cdot \mathbf{S}  ~&~   \bar{\mathbf{A}} \cdot (\mathbf{S}_0 +
            \sum_{j=1}^{\ell} \mathsf{id}_i[j] \mathbf{S}_j) + h_{\mathsf{id}_i}  \mathbf{C}
        \end{array} \right] \\  \label{sim-matr-coin1}   &=&
        \left[
          \begin{array}{c|c}    \bar{\mathbf{A}} \cdot \mathbf{S}  ~&~   \bar{\mathbf{A}} +  h_{\mathsf{id}_i} \cdot \mathbf{C}
        \end{array} \right]
      \end{eqnarray}
      Since   $h_{\mathsf{id}_i} \neq 0$, $\bdv$ can use the trapdoor
      $\mathbf{T}_{\mathbf{C}} \in \ZZ^{m \times m}$ of   $\Lambda_q^{\perp}(\mathbf{C})$ to compute  a short vector $\mathbf{d}_i = [ \mathbf{d}_{i,1}^T ~|~\mathbf{d}_{i,2}^T ]^T \in \ZZ^{2m}$ such that
      \begin{eqnarray*}
        \mathbf{A}_{\mathsf{id}_i}  \cdot  \begin{bmatrix} \mathbf{d}_{i,1} \\ \hline \mathbf{d}_{i,2} \end{bmatrix}  = \mathbf{u} + \mathbf{D} \cdot \bit \bigl( \mathbf{D}_0 \cdot (\textsf{bin}(\mathbf{v}_{i}) +  \mathbf{D}_1 \cdot \mathbf{s}_i  \bigr) ,
        \end{eqnarray*}
        where $\mathbf{v}_{i} \in \Zq^{4n}$ is the syndrome chosen by $\adv$ at step 1 of the joining protocol.
      \item[-] If $i = i^\star$, $\bdv$ undertakes to generate a membership certificate $\crt_{i^\star}$ for the $\ell$-bit identifier $\mathsf{id}^\dagger \in \{0,1\}^\ell$ that was
        chosen at the outset of the game. To this end, $\bdv$ has to compute $\crt_{i^\star}$  without using the trapdoor $\mathbf{T}_{\mathbf{C}}$ since the matrix $\mathbf{A}_{\mathsf{id}^\dagger}$ does no longer
        depend on $\mathbf{C}$ in (\ref{sim-matr-coin1} ). This can be done by  recalling
        the vector $\mathbf{d}_{i^\star,1},\mathbf{d}_{i^\star,2}  \in \ZZ^m$ and $\mathbf{c}_M \in \Zq^{2n}$ that were used to define $\mathbf{u} \in \Zq^n$ in (\ref{def-u}) and using $\mathbf{T}_{\mathbf{D