1481 lines
100 KiB
TeX
1481 lines
100 KiB
TeX
% \chapter{Pairing-Based Dynamic Group Signatures}
|
|
% \addcontentsline{tof}{chapter}{\protect\numberline{\thechapter} Signatures de groupe dynamique à base de couplages}
|
|
% \label{ch:sigmasig}
|
|
%-------------------------------------------------
|
|
In this chapter, we aim at lifting the \textit{signature with efficient protocols} from~\cite{LPY15} to the random oracle model~\cite{BR93} in order to get an \textit{efficient} construction.
|
|
In the Camenish and Lysyanskaya terminology, signatures with efficient protocols~\cite{CL04a} are digital signatures which come with two companion protocols: a protocol whereby a signer can obliviously sign a committed message known only to the user and a zero-knowledge proof to efficiently attest possession of a hidden message-signature pair.
|
|
|
|
This building block proved useful in the design of many efficient anonymity-related protocols such as anonymous credentials~\cite{Cha85,CL01}, which are similar to group signatures except that anonymity is irrevocable (meaning that there is no opening authority).
|
|
In other words, an anonymous credential scheme involves one (or more) credential issuer(s) and a set of users who have a long term secret key which can be seen as their digital identity, and pseudonyms that can be seen as commitments to their secret key.
|
|
Users can dynamically obtain credentials from an issuer that only knows users' pseudonyms and obliviously sign users' secret keys as well as a set of attributes.
|
|
Later on, users can make themselves known to verifiers under a different pseudonym and demonstrate possession of the issuer's certificate on their secret key without revealing neither the signature nor the key.
|
|
In this context, signature with efficient protocols can typically be used as follows:
|
|
the user obtains the issuer's signature on a committed message via an interactive protocol, and uses a protocol for proving that two commitments open to the same value (which allows proving that the same secret underlies two distinct pseudonyms) and finally a protocol for proving possession of a secret message-signature pair.
|
|
|
|
As explained in \cref{ch:proofs}, the \textit{quality} of a scheme depends on both its efficiency and the reliability of the assumptions it relies on.
|
|
Before the works described in this chapter, most signature schemes rely on groups of hidden order~\cite{CL04a} or non-standard assumptions in groups with bilinear maps~\cite{CL04, BBS04, Oka06}.
|
|
To illustrate this multi-criteria quality evaluation, we can see that Camenisch and Lysyanskaya proposed a signature scheme that is secure in pairing-friendly groups but relies on the interactive LRSW assumption~\cite{LRSW99}; but this signature scheme requires $\mathcal{O}(n)$ group elements to encode an $\ell$-block message.
|
|
Pointcheval and Sanders~\cite{PS18} improved this signature to go down to $\bigO(1)$ group elements for an $\ell$-block message, but which is only proven secure in the generic group model (a model where group accesses are handled by an oracle that performs the group operations).
|
|
|
|
We note that besides the scheme presented in this section, we are only aware of two schemes based on fixed-size assumptions: (1) A variant of the Camenisch and Lysyanskaya scheme~\cite{CL04} due to Gerbush, Lewko, O'Neill and Waters~\cite{GLOW12} in composite order groups.
|
|
Due to this assumption, the groups that are used are inherently bigger and lead to less efficient representations than in prime-order groups: for equivalent security levels, Freeman~\cite{Fre10} estimates that computing a pairing over a group $N = pq$ is at least $50$ times slower than the same pairing in the prime order group setting.
|
|
(2) A construction by Yuen, Chow, Zhang and Yu~\cite{YCZY14} under the decision linear assumption~\cite{BBS04} that unfortunately does not support ``randomizable signature'', which is an important property in privacy-enhancing cryptography. An application of this property is, in the context of group signatures, the re-randomization of credentials accross distinct privacy-preserving authentication.
|
|
|
|
In this chapter, we describe a new signature scheme with efficient protocols and re-randomizable signatures under a simple and well-studied assumption.
|
|
Namely, the security of our scheme relies on the \SXDH assumption in groups of prime order with a bilinear map.
|
|
From an efficiency point of view, the signature for an $\ell$-block message consists of only $4$ groups elements.
|
|
|
|
This signature length is made possible by using efficient $\QANIZK$ arguments -- as presented in~\cref{sse:zk-nizk} and formally defined in~\cite{JR13} -- to prove the belonging to some linear subspace spanned by the rows of a matrix.
|
|
For this purpose, it was shown that for this specific task, the size of the argument may be independent of the dimension of the considered subspace~\cite{JR14,LPJY14,KW15}.
|
|
The signature scheme described in this chapter (\cref{scal-sig}) crucially takes advantage of this observation as $\ell$-block messages are certified using a $\QANIZK$ argument for a subspace of dimension $\bigO(\ell)$.
|
|
This construction natively supports efficient protocols to enhance privacy as described in \cref{new-proto}. Hence, our signature scheme enables the design of an efficient anonymous credentials system based on the sole \SXDH assumption.
|
|
|
|
As another showcase for this signature, we also design another primitive.
|
|
Namely, a dynamic group signature scheme, as described in \cref{ch:gs-background}, which is practical and relies on simple assumptions (namely, \SXDH and \SDL).
|
|
This construction is competitive both in term of signature size and computation time with the best solutions based on non-interactive assumptions~\cite{BBS04,DP06} (in these cases, the Strong Diffie-Hellman assumption~\cite{BB04}).
|
|
Concretely, at the 128-bits security, each signature fits within $320$ bytes while providing the strongest sense of anonymity (meaning the definition in \cref{sec:RGSdefsecAnon}).
|
|
|
|
\paragraph{Our Contribution.}
|
|
In this chapter, we propose a new signature scheme with efficient protocols and re-randomizable signatures under simple, well-studied assumptions. The security of our scheme is proved in the standard model under the Symmetric eXternal Diffie-Hellman (SXDH) assumption, which
|
|
is a well-established, constant-size assumption (i.e., described using a constant number of elements, regardless of the number of adversarial queries)
|
|
in groups with a bilinear map. Remarkably, we can sign $\ell$-block messages using only $4$ group elements under the SXDH assumption.
|
|
|
|
Our signature length is made possible by the use of efficient Quasi-Adaptive Non-Interactive Zero-Knowledge (\QANIZK) arguments for linear subspaces (described in~\cref{de:qa-nizk}). It was shown
|
|
\cite{LPJY14,JR14,KW15} that, for the task of arguing that a vector of group elements belongs to some linear subspace, the size of arguments may be independent of
|
|
the dimensions of the considered subspace. Our signature scheme crucially exploits this observation as $\ell$-block messages are signed by generating a \QANIZK
|
|
argument for a subspace of dimension $O(\ell)$.
|
|
|
|
Our signature natively supports efficient privacy-enhancing protocols. We describe
|
|
a two-party protocol allowing a user to obtain a signature on a committed multi-block message as well as a honest-verifier zero-knowledge protocol for efficiently demonstrating
|
|
knowledge of a signature on a committed message revealing neither the message nor the signature. Hence, our scheme readily enables the design of an efficient anonymous
|
|
credentials system based on the sole SXDH assumption.
|
|
|
|
As another application of our signature scheme, we describe a truly practical group signature (for dynamic groups) based on simple assumptions in the
|
|
random oracle model. Our scheme is competitive with the best solutions \cite{BBS04,DP06} based on non-interactive assumptions (which are those relying on the Strong Diffie-Hellman assumption \cite{BB04}) in terms of computational cost and signature length. Concretely, at the $128$-bit security level, each signature fits within $320$ bytes while providing
|
|
anonymity in the strongest sense (i.e., against adversaries equipped with a signature opening oracle). To the best of our knowledge, the new scheme thus features the shortest group signatures based on
|
|
standard assumptions.
|
|
|
|
It seems that our signature scheme has many other potential applications. For example, combining it with the ideas of \cite{CHL05} and a pseudo-random function based on standard assumptions
|
|
(e.g., \cite{NR97}) readily gives a compact e-cash system based on simple hardness assumptions.
|
|
\bigskip
|
|
|
|
The rest of the chapter is organized as follows. We will first recall the useful building blocks that are used to design and prove our signature scheme that supports efficient protocols in the~\cite{CL02a} fashion. Then we describe this scheme and we next give the construction and the proof for the group signature scheme for dynamically growing groups. Finally, we show the experimental results we obtain for this group signature scheme.
|
|
|
|
|
|
%--------------------------------------------------
|
|
\section{Building blocks}
|
|
\addcontentsline{tof}{section}{\protect\numberline{\thesection} Briques de base}
|
|
|
|
We use bilinear maps $e:\GG \times \Gh \to \GT$ over
|
|
groups of prime order $p$ and we rely on the assumed security of the \SDL and \SXDH problems defined in \cref{se:pairings}. All these definitions are recalled below.
|
|
|
|
\defPairings*
|
|
|
|
\defSXDH*
|
|
|
|
\defSDL*
|
|
|
|
\subsection{Quasi-Adaptive $\NIZK$ Arguments for Linear Subspaces} \label{sse:sigmasig-qa-nizk}
|
|
\addcontentsline{tof}{section}{\protect\numberline{\thesection} Argument $\NIZK$ quasi-adaptatif pour un sous-espace linéaire}
|
|
|
|
Quasi-Adaptive $\NIZK$ (\QANIZK) proofs \cite{JR13} are $\NIZK$ proofs where the common reference string (CRS)
|
|
may depend on the language for which proofs have to be generated.
|
|
Formal definitions are given in \cite{JR13,LPJY14,KW15}.
|
|
|
|
This section recalls the \QANIZK argument of \cite{KW15} for proving membership in the row space of a matrix.
|
|
In the description below, we assume that all
|
|
algorithms take as input the description of common public parameters $\mathsf{cp}$ consisting of asymmetric
|
|
bilinear groups $(\GG,\Gh,\GT,p)$ of prime order $p>2^\lambda$, where $\lambda$ is the security parameter.
|
|
In this setting the problem is to convince that $\boldsymbol{v}$ is a linear combination of the rows of a given
|
|
$\mathbf{M}\in\GG^{t\times n}$.
|
|
|
|
Kiltz and Wee \cite{KW15} suggested the following construction which simplifies \cite{LPJY14} and remains secure under \SXDH.
|
|
We stress that $\mathsf{cp}$ is independent of the matrix $\mathbf{M} = (\vec{M}_1\cdots\vec{M}_t)^T$.
|
|
|
|
\begin{description}
|
|
\item[\textsf{Keygen}$(\mathsf{cp},\mathbf{M})$:]
|
|
Given public parameters $\mathsf{cp}=(\GG,\Gh,\GT,p)$ and the matrix $\mathbf{M}=(M_{i,j})\in\GG^{t\times n}$.
|
|
|
|
First, choose $\hat{g_z} \sample \U(\Gh)$. Pick $\mathsf{tk}=(\chi_1^{},\ldots,\chi_n^{}) \sample \U(\Zp^n)$
|
|
and compute $\hat{g}_j=\hat{g_z^{}}^{\chi_j}$, for all $j=1$ to $n$.
|
|
|
|
Then, for $i=1$ to $t$, compute $z_i=\prod_{j=1}^n M_{i,j}^{-\chi_j}$ and
|
|
output
|
|
\[\mathsf{crs}=\big(\{ z_i \}_{i=1}^t,~ \hat{g}_z,~\{ \hat{g}_j \}_{j=1}^n \big)
|
|
\in \GG^t\times\Gh^{n+1}.\]
|
|
|
|
\item[\textsf{Prove}$(\mathsf{crs}, {\boldsymbol{v}}, \{\omega_i\}_{i=1}^t)$:]
|
|
To prove that ${\boldsymbol{v}}=\vec{M}_1^{\omega_1}\cdots\vec{M}_t^{\omega_t}$,
|
|
for some witness $\omega_1,\ldots,\omega_t \in \Zp$,
|
|
where $\vec{M}_i$ denotes the $i$-th row of $\mathbf{M}$,
|
|
parse $\mathsf{crs}$ as above
|
|
and return $\pi=\prod_{i=1}^t z_{i}^{\omega_i}$.
|
|
|
|
\item[\textsf{Sim}$(\mathsf{tk}, {\boldsymbol{v}})$:]
|
|
In order to simulate a proof for a vector ${\boldsymbol{v}} \in \GG^n$ using $\mathsf{tk}= \{ \chi_i \}_{i=1}^n $,
|
|
output $\pi = \prod_{j=1}^n v_j^{-\chi_j} $.
|
|
|
|
\item[\textsf{Verify}$(\mathsf{crs}, {\boldsymbol{v}}, \pi)$:]
|
|
Given $\pi \in \GG$, ${\boldsymbol{v}}=(v_1,\dotsc,v_n)$ and $\mathsf{crs}$ parsed as above,
|
|
return $1$ if and only if $(v_1,\dotsc,v_n)\neq (1_{\GG},\dotsc,1_{\GG})$ and $\pi$ satisfies
|
|
$ 1_{\GT} = e(\pi,\hat{g_z}) \cdot \prod_{j=1}^n e(v_j,\hat{g}_j) . $
|
|
\end{description}
|
|
|
|
The proof of the soundness of this \QANIZK argument system requires the matrix $\mathbf{M}$ to be witness-samplable.
|
|
This means that the reduction has to know the discrete logarithms of the group elements of $\mathbf{M}$.
|
|
This requirement is compatible with our security proofs.
|
|
|
|
\section{A Randomizable Signature on Multi-Block Messages} \label{scal-sig}
|
|
|
|
In \cite{LPY15}, Libert \textit{et al.} described an F-unforgeable signature%
|
|
\footnote{In F-unforgeability, the adversary only has to output a forgery for a message $M$ without outputting the message, but the image $F(M)$ for an injective function $F$ that is not necessarily efficiently invertible instead~\cite{BCKL08}. In~\cite{LPY15}, the function $F$ is $M \mapsto \hat{g}^M$.}
|
|
based on the $\SXDH$ assumption. We show that their scheme
|
|
implies an efficient ordinary digital signature which makes it possible to efficiently sign multi-block messages in $\Zp^{\ell}$ while keeping the scheme
|
|
compatible with efficient protocols. In order to keep the signature length independent of the number of blocks, we exploit the property that the underlying \QANIZK argument \cite{KW15} has constant size, regardless of the dimensions of the considered linear subspace.
|
|
Moreover, we show that their scheme remains unforgeable under the $\SXDH$ assumption.
|
|
|
|
\begin{description}
|
|
\item[\textsf{Keygen}$(\lambda,\ell):$] Choose bilinear groups $\mathsf{cp}=(\GG,\Gh,\GT,p)$
|
|
of prime order $p>2^{\lambda}$ with $g \sample \U(\GG)$, $\hat{g} \sample \U(\Gh)$.
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item Choose $\omega,a \sample \U(\Zp)$,
|
|
and set $h=g^a$,
|
|
$\Omega=h^{\omega}$.
|
|
\item Choose $\vec{v}=(v_1,\ldots,v_\ell,w) \sample \U(\GG^{\ell+1})$.
|
|
\item Define a matrix $\mathbf{{M}}=(M_{j,i})_{j,i} \in {\GG}^{ (\ell+2) \times (2\ell+4) }$
|
|
\begin{equation}\label{matrix-scal-sig}
|
|
\mathbf{{M}} = %\big({M}_{i,j} \big)_{i,j} =
|
|
\setlength{\arraycolsep}{0.3em}\def\arraystretch{1.3}
|
|
\left(\begin{array}{c|c|c|c}
|
|
g & \mathbf{1}_{{}_{\ell+1}} & \mathbf{1}_{{}_{\ell+1}} & h \\ \hline
|
|
\vec{v}^T & g^{\mathbf{I}_{\ell+1}} & h^{\mathbf{I}_{\ell+1}}
|
|
& \mathbf{1}_{{}_{\ell+1}}^T
|
|
\end{array}\right) ,
|
|
\end{equation}
|
|
where $\mathbf{1}_{{}_{\ell+1}}=(1_{\GG},\ldots,1_{\GG})\in\GG^{\ell+1}$.
|
|
\item Run $\mathsf{Keygen}(\mathsf{cp},M)$ of the \QANIZK argument of \cref{sse:sigmasig-qa-nizk}
|
|
to get the common reference string
|
|
$\mathsf{crs}=\left(\{ z_i \}_{i=1}^{\ell+2},~ \hat{g}_z^{},~\{ \hat{g}_j \}_{j=1}^{2\ell+4} \right)$.
|
|
\bigskip
|
|
\item[]
|
|
The private key is $ \mathsf{sk}\coloneqq \omega $ and the public key is
|
|
\begin{align*}
|
|
\mathsf{pk}=\Bigl(
|
|
\mathsf{cp},~g,~h,~\hat{g}, ~\vec{v}%=(v_1,\ldots,v_\ell,w)
|
|
,~\Omega=h^\omega,~\mathsf{crs}
|
|
\Bigr).
|
|
\end{align*}
|
|
\end{enumerate}
|
|
|
|
\begin{description}
|
|
\item[\textsf{Sign}$(\mathsf{sk},\vec{m}=(m_1,\ldots,m_\ell)):$] given
|
|
the private key $\mathsf{sk}=\omega$ and a message
|
|
$\vec{m}\in \Zp^\ell$, choose $s \sample \U(\Zp)$ to compute
|
|
\begin{align*}
|
|
\sigma_1 &
|
|
= g^\omega\cdot (v_1^{m_1}\cdots v_\ell^{m_\ell}\cdot w)^{s}, &
|
|
\sigma_2 & = g^{s}, & \sigma_3 & = h^{s} .
|
|
\end{align*}
|
|
Then, run $\mathsf{Prove}$ of the \QANIZK argument to prove that
|
|
the following vector of $\GG^{2\ell+4}$
|
|
\begin{align} \label{eq:vector}
|
|
(\sigma_1,\sigma_2^{m_1},\ldots,\sigma_2^{m_\ell},\sigma_2,
|
|
\sigma_3^{m_1},\ldots,\sigma_3^{m_\ell},\sigma_3,\Omega)
|
|
\end{align}
|
|
is in the row space of $\mathbf{M}$. This \QANIZK proof $\pi\in\GG$ consists of $\pi = z_1^\omega \cdot (z_2^{m_1}\cdots z_{\ell+1}^{m_\ell} \cdot
|
|
z_{\ell+2})^{s}.$
|
|
|
|
Return the signature $\sigma=\big(\sigma_1,\sigma_2,\sigma_3, \pi \big)\in\GG^{4}$.
|
|
|
|
\item[\textsf{Verify}$(\mathsf{pk},\sigma,\vec{m}):$]
|
|
parse $\sigma$ as above and $\vec{m}$ as a tuple $(m_1,\ldots,m_\ell)$ in $\Zp^\ell$ and return $1$
|
|
if and only if
|
|
\begin{align} \label{sig-ver-1}
|
|
e(\Omega,\hat{g}_{2\ell+4})^{-1} =
|
|
&~ e(\pi,\hat{g}_z) \cdot e(\sigma_1,\hat{g_1}) \\ \nonumber
|
|
&~ \cdot e(\sigma_2,\hat{g}_{2}^{m_1}\cdots\hat{g}_{\ell+1}^{m_\ell} \cdot \hat{g}_{\ell+2} ) %\\ \nonumber &~~~
|
|
\cdot e(\sigma_3,\hat{g}_{\ell+3}^{m_1}\cdots\hat{g}_{2\ell+2}^{m_\ell} \cdot \hat{g}_{2\ell+3}) .
|
|
\end{align}
|
|
|
|
\end{description}
|
|
|
|
The signature on $\ell$ scalars thus only consists of $4$ elements in $\GG$
|
|
while the verification equation only involves a computation of $5$ pairings\footnote{Actually only $4$ pairing computations are necessary, as $e(\Omega, \hat{g}_{2\ell+4})$ is independent of the inputs $\pi$ and $\vec{m}$, and can hence be precomputed.}.
|
|
|
|
\begin{theorem} \label{th:eu-cma-1}
|
|
The above signature scheme is existentially unforgeable under chosen-message attacks (\textsf{eu-cma}) if the $\SXDH$ assumption holds in $(\GG, \Gh, \GT)$.
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
We will proceed as in~\cite{LPY15} to prove that the scheme of
|
|
section~\ref{scal-sig} is secure under chosen-message attacks. Namely we will consider a sequence of hybrid games involving two
|
|
kinds of signatures. \vspace{-0.1 cm}
|
|
|
|
\begin{description}
|
|
\item[Type A signatures:] These are real signatures:
|
|
\begin{equation} \label{eq:rel-sig-A}
|
|
\begin{aligned}
|
|
\sigma_1 &= g^\omega \cdot ( v_1^{m_1} \cdots v_\ell^{m_\ell} \cdot w)^s, &
|
|
\sigma_2 &= g^s, \\
|
|
\pi &= z_1^\omega \cdot (z_2^{m_1}\cdots z_{\ell+1}^{m_\ell} \cdot
|
|
z_{\ell+2})^{s} ,&
|
|
\sigma_3 &= h^s.
|
|
\end{aligned}
|
|
\end{equation}
|
|
Since $(\sigma_1,\sigma_2^{m_1},\ldots,\sigma_2^{m_\ell},\sigma_2, \sigma_3^{m_1},\ldots,\sigma_3^{m_\ell},\sigma_3,\Omega)$
|
|
is in the row space of $\mathbf{M}$, the \QANIZK proof $\pi$ has the same distribution as if it were computed as
|
|
\begin{equation}
|
|
\label{eq:rel-sim-A}
|
|
\begin{aligned}
|
|
\pi &= \sigma_1^{-\chi_1} \cdot \left( \prod_{i=2}^{\ell+1} \sigma_2^{-\chi_i m_{i-1}} \right) \cdot \sigma_2^{-\chi_{\ell + 2}} \cdot \quad \\ \quad &
|
|
\left( \prod_{i=\ell + 3}^{2 \ell + 2} \sigma_3^{-\chi_i m_{i - \ell - 2}} \right) \cdot
|
|
\sigma_3^{-\chi_{2\ell+3}} \cdot \Omega^{-\chi_{2 \ell + 4}} .
|
|
\end{aligned}
|
|
\end{equation}
|
|
\end{description} \smallskip
|
|
|
|
We also define \textbf{Type $\mathbf{A'}$} signatures as a generalization of
|
|
Type A signatures where only condition~\eqref{eq:rel-sig-A} are imposed and no
|
|
restriction is given on $\pi$ beyond the fact that it should be a valid
|
|
homomorphic signature on vector~\eqref{eq:vector}.
|
|
\smallskip
|
|
|
|
\begin{description}
|
|
\item[Type B signatures:] These use a random value $\omega' \in_R \Zp$ instead of the secret key $\omega$. We pick random $\omega', s, s_1 \sample \U(\Zp)$ and
|
|
compute:
|
|
\begin{equation*}
|
|
\begin{gathered}
|
|
(\sigma_1,\sigma_2,\sigma_3) =( g^{\omega'} \cdot ( v_1^{m_1} \cdots v_\ell^{m_\ell} \cdot w)^s, ~ g^s, ~ h^{s+s_1}),
|
|
\end{gathered}
|
|
\label{eq:rel-sig-B}
|
|
\end{equation*}
|
|
The \QANIZK proof $\pi$ is
|
|
computed as in \eqref{eq:rel-sim-A} by using $\mathsf{tk}=\{\chi_i \}_{i=1}^{2\ell+4}$. Note that Type B signatures can be generated without using $\omega \in \Zp$.
|
|
\end{description}
|
|
\smallskip
|
|
|
|
|
|
We consider a sequence of games.
|
|
In Game $i$, $S_i$ denotes the event that $\adv$
|
|
produces a valid signature $\sigma^\star$ on $M^\star$ such that
|
|
$(M^\star, \sigma^\star)$ was not queried before, and by $E_i$ the event that
|
|
$\adv$ produces a Type $\mathrm{A}'$ signature.
|
|
|
|
\begin{description}
|
|
\item[Game 0:] This is the real game. The challenger $\bdv$ produces
|
|
a key pair $(\mathsf{sk}, \mathsf{pk})$ and sends $\mathsf{pk}$ to $\adv$. Then $\adv$
|
|
makes $Q$ signature queries: $\adv$ sends messages $M_i$ to $\bdv$, and $\bdv$
|
|
answers by sending $\sigma_i = \Sign(\mathsf{sk}, M_i)$ to $\adv$. Finally $\adv$
|
|
sends a pair $(M^\star, \sigma^\star) \notin \{ (M_i, \sigma_i) \}_{i=1}^Q$
|
|
and wins if $\Verify(\mathsf{pk}, \sigma^\star, M^\star) = 1$.
|
|
|
|
\item[Game 1:] We change the way $\bdv$ answers signing queries.
|
|
The \QANIZK proofs $\pi$ are then computed as simulated \QANIZK proofs
|
|
using $\mathsf{tk}$
|
|
as in~\eqref{eq:rel-sim-A}. These \QANIZK proofs are thus simulated
|
|
proofs for true statements, and then their distribution remains unchanged.
|
|
We have $\Pr[S_1] = \Pr[S_1 \wedge E_1] + \Pr[S_1 \wedge
|
|
\neg E_1]$.
|
|
Lemma~\ref{le:type-a-sig} states
|
|
that the event $S_1 \wedge
|
|
\neg E_1$ happens with all but negligible probability: $\Pr[S_1 \wedge
|
|
\neg E_1] \leq \advantage{\DDH}{\Gh}(\lambda) - 1/p$. Thus our task is now
|
|
to upper-bound the probability $\Pr[S_1 \wedge E_1]$.
|
|
|
|
\item[Game 2.$\boldsymbol{k~(0 \leq k \leq Q)}$:] In Game $2.k$, the
|
|
challenger returns a Type B signature for the first $k$ queries. At the
|
|
last $Q - k$ signature queries, the challenger answers a type $A$
|
|
signature. \cref{le:type-b-sig} ensures that
|
|
\[\left| \Pr\Bigl[S_{2.k} \wedge E_{2.k}\Bigr] - \Pr\Bigl[S_{2.(k-1)} \wedge E_{2.(k-1)}\Bigr] \right|\]
|
|
is smaller than $\advantage{\DDH}{\GG}(\lambda) + 1/p$.
|
|
\end{description}
|
|
|
|
In Game $2.Q$, we know that if $\SXDH$ holds, $\adv$ can only output a type $\mathrm{A}'$
|
|
forgery even if it only obtains type B signatures during the game.
|
|
Nevertheless, lemma~\ref{le:final-forgery} shows
|
|
that a type $\mathrm{A}'$ forgery in Game
|
|
$2.Q$ contradicts the DDH assumptions in $\GG$. Therefore we have
|
|
$\Pr[S_{2.Q} \wedge E_{2.Q}] \leq \advantage{\DDH}{\GG}(\lambda)$. Putting the above altogether, the probability $\Pr[S_0]$ is upper-bounded by
|
|
\begin{multline*}
|
|
\advantage{\DDH}{\Gh}(\lambda) + \frac{1}{p} + Q \left( \advantage{\DDH}{\GG}(\lambda) + \frac{1}{p} \right) + \advantage{\DDH}{\GG}(\lambda) \\
|
|
< (Q + 2) \cdot \left( \advantage{\mathrm{SXDH}}{\GG, \Gh}(\lambda) + \frac{1}{p} \right).
|
|
\end{multline*}
|
|
\end{proof}
|
|
|
|
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
\begin{lemma} \label{le:type-a-sig}
|
|
In \textbf{Game 1}, if the DDH assumption holds in $\Gh$, $\adv$ can only output a type $A'$
|
|
forgery.
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Let $\adv$ be an attacker that does not
|
|
output a type $\mathrm{A}'$ forgery. We will build an attacker $\bdv$ against the soundness of the
|
|
Quasi-Adaptive $\NIZK$ (\QANIZK) scheme, which security is implied from the double-pairing
|
|
problem that reduces from DDH as explained in~\cite{LPJY13}.
|
|
Let us define the vector $\ssigma \in \GG^{2\ell+4}$ as
|
|
\[
|
|
\ssigma \triangleq (\sigma_1^\star, \sigma_2^{\star m_1}, \ldots, \sigma_2^{\star m_\ell}, \sigma_2^\star, \sigma_3^{\star m_1}, \ldots, \sigma_3^{\star m_\ell}, \sigma_3^\star, \Omega)
|
|
\in \GG^{2\ell + 4}.
|
|
\]
|
|
If $(M^\star, \sigma^\star)$ is not a type $\mathrm{A}'$ forgery, $\ssigma$ is then not in the row
|
|
space of $\mathbf{M}$.
|
|
|
|
Our reduction $\bdv$ receives as input $\mathsf{cp}=(\GG,\Gh,\GT,p)$, a matrix ${\mathbf{M}}$ as in
|
|
(\ref{matrix-scal-sig}) and a common
|
|
reference string $\mathsf{crs}$ (depending on the matrix) for an instance of the
|
|
\QANIZK scheme allowing to prove that vectors of dimension $2\ell + 4$ are in the row space of ${\mathbf{M}}$.
|
|
The generation of the matrix ${\mathbf{M}}$ fixes $g$, $h$ and $\vec{v}=(v_1,\ldots,v_\ell,w)\in\GG^{\ell+1}$.
|
|
After that, $\bdv$ picks $\omega \sample \U(\Zp)$ and $\hat g \sample \U(\Gh)$, and set $\Omega = h^\omega$.
|
|
Then, the reduction $\bdv$ sends to $\adv$ $\mathsf{cp}$ and the verification key:
|
|
\begin{align*}
|
|
\mathsf{pk} = \bigl( g,h,\hat g, \vec{v}, \omega,\mathsf{crs} \bigr).
|
|
\end{align*}
|
|
|
|
Since $\bdv$ knows the secret key $\omega \in \Zp$, it can answer all signing queries by honestly
|
|
running the $\Sign$ algorithm, in particular, it does not need to know $\mathsf{tk}$ to do this.
|
|
|
|
When $\adv$ halts, it outputs $(M^\star, \sigma^\star)$ where $\sigma^\star$ is not a Type $\mathrm{A}'$ forgery, so that $\ssigma$ is not in the row space of $\mathbf{M}$.
|
|
Therefore, outputting $\pi^\star$ constitutes a valid proof against the soundness property of the
|
|
scheme, and thus implies an algorithm against DDH as in~\cite{KW15} since the matrix can be
|
|
witness-samplable.
|
|
\end{proof}
|
|
|
|
\begin{lemma} \label{le:type-b-sig}
|
|
If DDH holds in $\GG$, for each $k \in
|
|
\{1,\ldots, Q \}$, $\adv$ produces a type $A'$ forgery with negligibly different probabilities in \textbf{Game $\boldsymbol{2.k}$} and \textbf{Game $\boldsymbol{2.(k-1)}$}.
|
|
\end{lemma}
|
|
%
|
|
\begin{proof}
|
|
Let us assume there exists an index $k \in \{1, \ldots, Q\}$ and an adversary $\adv$ that outputs a
|
|
Type $\mathrm{A}'$ forgery with smaller probability in Game $2.k$ than in Game
|
|
$2.(k-1)$. We build a DDH distinguisher $\bdv$. \medskip
|
|
\\
|
|
Algorithm $\bdv$ takes in $(g^a, g^b, \eta) \in \GG^3$, where $\eta =
|
|
g^{a(b+c)}$, and decides if $c=0$ or $c \in_R \Zp$. To do this, $\bdv$ sets $h = g^a$. It
|
|
picks $\omega, a_{v_1}, b_{v_1}, \ldots, a_{v_\ell}, b_{v_\ell}, a_{w}, b_{w} \sample \U(\Zp)$
|
|
and sets $\Omega = h^\omega$ as well as:
|
|
\[ \forall i \in \{1,\dots, \ell \}:~~ v_i = g^{a_{v_i}} \cdot h^{b_{v_i}}, \quad w = g^{a_w} \cdot h^{b_w}. \]
|
|
% in order to have the discrete logs of $v_i$ and $w$. \medskip
|
|
% \\
|
|
|
|
The reduction $\bdv$ also chooses $\mathsf{tk} = \{ \chi_i \}_{i=1}^{2\ell + 4}$ and
|
|
computes $\mathsf{crs} = ( \{z_j\}_{j=1}^{2\ell+4}, \hat g_z, \{ \hat g_i \}_{i=1}^{2\ell + 4})$
|
|
as in steps 3-4 of \textsf{Keygen}. It then outputs $\mathsf{pk}=(g,h,\hat g, \vec{v}, \omega,\mathsf{crs})$.
|
|
\smallskip
|
|
|
|
Then, queries are answered depending on their index~$j$:\\
|
|
\textbf{Case $\boldsymbol{j < k}$:} $\bdv$ computes a Type B signature, $\sigma = (\sigma_1, \sigma_2,
|
|
\sigma_3, \pi)$, using $\mathsf{tk}=\{ \chi_i \}_{i=1}^{2\ell + 4}$ with the \QANIZK simulator
|
|
to computes $\pi$.
|
|
|
|
\textbf{Case $\boldsymbol{j > k}$:} The last $Q - k - 1$ signing queries are computed as
|
|
Type A signatures, which $\bdv$ is able to generate using the secret key $\omega \in \Zp$ he knows
|
|
and $\mathsf{crs}$ or $\mathsf{tk}=\{ \chi_i \}_{i=1}^{2\ell + 4}$ to produces valid proofs.
|
|
|
|
\textbf{Case $\boldsymbol{j = k}$:} In the $k$-th signing query $(m_1,\dots,m_\ell)$, $\bdv$
|
|
embeds the DDH instance in the signature and simulates either Game $2.k$ or Game $2.(k-1)$
|
|
depending on whether $\eta = g^{ab}$ or $\eta = g^{a(b+c)}$ for some $c \in_R \Zp$. Namely, $\bdv$ computes $\sigma_2 = g^b$, $\sigma_3 = \eta$,
|
|
and
|
|
$ \sigma_1 = g^\omega \sigma_2^{a_w + \sum_{i=1}^\ell a_{v_i} m_i} \sigma_3^{b_w + \sum_{i=1}^\ell b_{v_i} m_i}. $
|
|
Then $\bdv$ simulates \QANIZK proofs $\pi$ as recalled in \eqref{eq:rel-sim-A}, and sends $\sigma = (\sigma_1, \sigma_2, \sigma_3, \pi)$ to $\adv$.
|
|
\smallskip
|
|
|
|
If $\eta = g^{ab}$, the $k$-th signature $\sigma$ is
|
|
a Type A signature with $s=b$. If $\eta = g^{a(b+c)}$ for some $c
|
|
\in_R \Zp$, we have:
|
|
\begin{align*}
|
|
\sigma_1 & = g^\omega g^{ac\cdot(b_w + \sum_{i=1}^\ell b_{v_i} m_i)} (v_1^{m_1} \cdots v_\ell^{m_\ell} w)^b\\
|
|
& = g^{\omega'} (v_1^{m_1} \cdots v_\ell^{m_\ell} w)^b \\
|
|
\sigma_2 &= g^b, \qquad \qquad \qquad \qquad \qquad
|
|
\sigma_3 = h^{b+c}
|
|
\end{align*}
|
|
Where $\omega' = \omega + ac\cdot(b_w + \sum_{i=1}^\ell b_{v_i} m_i)$. Since the term $b_w +
|
|
\sum_{i=1}^\ell b_{v_i}m_i$ is uniform and independent of $\adv$'s view, $\sigma$ is
|
|
distributed as a Type B signature if $\eta = g^{a(b+c)}$.
|
|
|
|
When $\adv$ terminates, it outputs a couple $(m_1^\star\cdots m_\ell^\star, \sigma^\star)$ that has not been queried
|
|
during the signing queries. Now the reduction $\bdv$ has to determine whether $\sigma^\star$ is a
|
|
Type $\mathrm{A}'$ forgery or not. To this end, it tests if the equality:
|
|
\begin{equation} \label{eq:verif-proof}
|
|
\sigma_1^\star = g^\omega \sigma_2^{\star a_w + \sum_{i=1}^\ell a_{v_i} m_i^\star} \sigma_3^{\star b_w + \sum_{i=1}^\ell b_{v_i} m_i^\star}
|
|
\end{equation}
|
|
is satisfied. If it is, $\bdv$ outputs $1$ to indicate that $\eta = g^{ab}$. Otherwise it outputs
|
|
$0$ and rather bets that $\eta \in_R \GG$.
|
|
|
|
To see why this test allows recognizing Type $\mathrm{A}'$ forgeries,
|
|
we remark that $\sigma^\star$ is of the form:
|
|
\begin{align*}
|
|
\sigma^\star_2 & = g^s , &
|
|
\sigma^\star_3 & = h^{s + s_1} , &
|
|
\sigma^\star_1 & = g^{\omega + s_0} (v_1^{m^\star_1} \cdots v_\ell^{m^\star_\ell} w)^s ,
|
|
\end{align*}
|
|
and the goal of $\bdv$ is to decide whether $(s_0, s_1) = (0, 0)$ or not. We notice that
|
|
$s_0 = a\cdot s_1 \cdot (b_w + \sum_{i=1}^\ell b_{v_i} \cdot m_i^\star)$ if the forgery fulfills
|
|
relation~\eqref{eq:verif-proof} and we show this to only happen with probability $1/p$ for any $s_1\neq 0$
|
|
meaning that Type $\mathrm{B}$ forgery passes the test with the same probability.
|
|
|
|
From the entire game, and assuming a forgery which passes the test, we have the following linear system:
|
|
\[
|
|
\left(
|
|
\bgroup
|
|
\def\arraystretch{1.5}
|
|
\begin{array}{c|c}
|
|
\mathbf{I}_{\ell+1} & a \cdot \mathbf{I}_{\ell + 1}\\ \hline
|
|
\boldsymbol{0}_{\ell + 1}^{T} & ac \cdot( m_1 | \cdots | m_\ell | 1) \\ \hline
|
|
\boldsymbol{0}_{\ell + 1}^{T} & a s_1 \cdot( m_1^\star | \cdots | m_\ell^\star | 1)
|
|
\end{array}
|
|
\egroup
|
|
\right) \cdot
|
|
% \begin{pmatrix}
|
|
% 1 & & & a & & \\
|
|
% & \ddots & & & \ddots & \\
|
|
% & & 1 & & & & a \\
|
|
% & & & a c \cdot m_1 & \cdots & a c \cdot m_\ell & ac \\
|
|
% & & & a c \cdot m_1^\star & \cdots & a c \cdot m_\ell^\star & ac
|
|
% \end{pmatrix} \cdot
|
|
\begin{pmatrix}
|
|
a_{v_1} \\ \vdots \\ a_{v_\ell} \\ a_w\\
|
|
b_{v_1} \\ \vdots \\ b_{v_\ell} \\ b_w
|
|
\end{pmatrix}
|
|
=
|
|
\begin{pmatrix}
|
|
\log_g(v_1) \\ \vdots \\ \log_g(v_\ell) \\ \log_g(w) \\
|
|
\omega' - \omega \\ s_0
|
|
\end{pmatrix}
|
|
\]
|
|
where, $\boldsymbol{0}_{\ell + 1}$ denotes the zero vector of length $\ell + 1$ and $m_1, \ldots, m_\ell$
|
|
is the message involved in the $k$-th signing query. Note that the $(l+2)$-th equation is meaningless when
|
|
$c=0$ since then $\omega' = \omega$. However, even if $c\neq 0$ the information that $\adv$ can infer about
|
|
$(a_{v_1},\ldots, a_{v_\ell}, a_w, b_{v_1}, \ldots, b_{v_\ell}, b_w) \in \Zp^{2 \ell + 2}$
|
|
during the game amounts to the first $\ell+2$ equations of the system which is of full rank. It means that
|
|
this vector is unpredictable since all the solutions of this linear system live in a sub-space of dimension
|
|
at least one (actually $\ell=(2\ell+2) -(\ell+2)$). Finally, as long as $s_1\neq 0$, the right value $s_0$
|
|
can only be guessed with probability $1/p$ since the last row of the matrix is independent of the others
|
|
as soon as $(m_1, \ldots, m_\ell) \neq (m^\star_1, \ldots, m^\star_\ell) \neq 0$.
|
|
|
|
To conclude the proof, since $\bdv$ is able the tell apart the type of the forgery, if $\adv$'s probability to
|
|
output a forgery of some Type in Game $k-1$ (\textit{i.e.}, $c=0$) was significantly different than in Game $k$
|
|
(\textit{i.e.}, $c\neq0$) then $B$ would be able to solve the DDH problem with non-negligible advantage.
|
|
|
|
\end{proof}
|
|
|
|
\begin{lemma} \label{le:final-forgery}
|
|
In \textbf{Game $\boldsymbol{2.Q}$}, a PPT adversary outputting a type $A'$ forgery would contradict
|
|
the DDH assumption in $\GG$:
|
|
$ \Pr[S_{2.Q} \wedge E_{2.Q}] \leq \advantage{\DDH}{\GG}(\lambda).$
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
We will build an algorithm $\bdv$ for solving the Computational Diffie Hellman problem~(CDH) which is at
|
|
least as hard as the DDH problem. The reduction $\bdv$ takes as input a tuple $(g, h, \Omega =
|
|
h^\omega)$ and computes $g^\omega$. To generate $\mathsf{pk}$, $\bdv$ picks $\hat g
|
|
\sample \U(\Gh)$, $a_{v_1}, \ldots, a_{v_\ell}, a_w \sample \U(\Zp)$ and computes
|
|
$ v_1 = g^{a_{v_1}},$ \ldots, $ v_\ell = g^{a_{v_\ell}}$, and $w = g^{a_w}.$ Then $\bdv$ generates
|
|
$\mathsf{tk} = \{ \chi_i \}_{i=1}^{2\ell + 4}$,
|
|
$\mathsf{crs} = (\{ z_j\}_{j=1}^{\ell + 2}, \hat g_z, \{\hat g_i\}_{i=1}^{2\ell + 4})$
|
|
as in step 3-4 of the key generation algorithm, then sends the public key
|
|
$ pk = \bigl(g, h, \hat g, \boldsymbol{v} , \Omega=h^\omega, \mathsf{crs}\bigr) $ to $\adv$.
|
|
%\begin{multline*}
|
|
% pk = \Bigl(g, h, \hat g, \boldsymbol{v} , \Omega=h^\omega,
|
|
% \mathsf{pk}_{hsps}, \{ (z_j, r_j) \}_{j=1}^{\ell + 2} \Bigr)
|
|
%\end{multline*}
|
|
|
|
$\bdv$ also retains $\mathsf{tk} = \{ \chi_i \}_{i=1}^{2\ell + 4}$ to handle
|
|
signing queries. We recall that during the game, signing queries are answered by returning a
|
|
Type B signature so that, using $\mathsf{tk}$, $\bdv$ can answer all queries without knowing the
|
|
$\omega = \log_h(\Omega)$ which is part of the CDH challenge.
|
|
|
|
The results of Lemma~\ref{le:type-b-sig} implies that even if $\adv$ only obtains Type B signatures,
|
|
it will necessarily output a Type $\mathrm{A}'$ forgery
|
|
$\sigma^\star = (\sigma^\star_1, \sigma^\star_2, \sigma^\star_3, \pi^\star)$
|
|
unless the DDH assumption does not hold in $\GG$.
|
|
This event thus allows $\bdv$ to compute
|
|
\[g^\omega = \sigma_1^\star \cdot {\sigma_2^\star}^{-a_w - \sum_{i=1}^\ell a_{v_i} m_i^\star}_{},\]
|
|
which contradicts the DDH assumption in $\GG$.
|
|
\end{proof}
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
\section{Companion Protocols } \label{new-proto}
|
|
|
|
In this section, we give $\Sigma$-protocols (\cref{sse:sigma-protocols}) for issuing a signature on a committed multi-block message and for proving knowledge of a valid message-signature pair.
|
|
|
|
%------------------------------------------------------------------------
|
|
\subsection{Proof of Knowledge of a Signature on a Committed Message}
|
|
|
|
We give $\Sigma$-protocols for proving the knowledge of a signature-message pair $({\sigma},\vec{m})$ satisfying the verification equation~\eqref{sig-ver-1} of the scheme of Section~\ref{scal-sig}
|
|
|
|
\begin{align} \label{eq-mult-sig}
|
|
e(\Omega,\hat{g}_{2 \ell+4})^{-1}
|
|
& = \, e(\sigma_1,\hat{g_1}) \cdot
|
|
e(\sigma_2,\hat{g}_{2}^{m_1}\cdots\hat{g}_{\ell+1}^{m_\ell}\cdot \hat{g}_{\ell+2} )
|
|
\\ \nonumber
|
|
& \quad \cdot e(\sigma_3,\hat{g}_{\ell+3}^{m_1}\cdots\hat{g}_{2 \ell+2}^{m_\ell}\cdot \hat{g}_{2 \ell+3} )
|
|
\cdot e(\pi,\hat{g}_z),
|
|
\end{align}
|
|
%
|
|
where ${\sigma}=(\sigma_1,\sigma_2,\sigma_3,\pi)$ and $\vec{m}=(m_1,\ldots,m_\ell)$.
|
|
We note that, as shown in the proof of Theorem \ref{th:eu-cma-1}, a candidate signature $(\sigma_1,\sigma_2,\sigma_3,\pi)$ may satisfy the verification equation
|
|
although $\log_g(\sigma_2)\neq \log_h(\sigma_3)$. In applications to anonymous credentials, a malicious credential issuer could take advantage of this fact in attempts to
|
|
break the anonymity of the scheme (e.g., by linking two authentications involving the same credential). For this reason, we consider a protocol for proving possession
|
|
of a possibly maliciously generated signature.
|
|
|
|
We thus consider the case of arbitrary valid signatures that may have been maliciously computed by a signer who, {e.g.}, aims at tracing provers across different authentications. In this setting, we can still obtain a perfect SHVZK $\Sigma$-protocol to hedge against such attacks.
|
|
|
|
|
|
A first attempt to efficiently build such a protocol is to ``linearize'' the verification equation (\ref{eq-mult-sig}) by making sure that two witnesses are never paired together. However, we will still have to deal with (parallelizable) intermediate $\Sigma$-protocols for quadratic scalar relations.
|
|
Even though a quadratic pairing-product equation $e(x_1,\hat{a}) \cdot e(x_2,\hat{y})$ -- for variables $x_1,x_2,\hat{y}$ and constant $\hat{a}$ -- can be linearized by partially randomizing the variables so as to get the equation $e(x_1\cdot x_2^{r},\hat{a}) \cdot e(x_2,\hat{y}\cdot \hat{a}^{-r})$ (which allows $\hat{y}'=\hat{y}\cdot \hat{a}^{-r}$ to appear in the
|
|
clear), proving knowledge of a valid signature still requires proving a statement about some representation of $\hat{y}$ which now appears in committed form. Somehow, going through the randomizing factor $\hat{a}^{-r}$ involves a quadratic relation between some known exponents to get special-soundness. To ease the entire proof we rather directly commit to the variables in $\GG$ and $\hat{\GG}$ using their available generator $g$ and $\hat{g}$ which are not among the constants of the verification equation of the signature. We additionally need an extra generator $f$ of $\GG$ whose discrete logarithm is unknown.
|
|
|
|
|
|
\begin{description}
|
|
\item[\textsf{Commit}] Given $({\sigma},\vec{m})$, conduct the following steps.
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item Commit to $d_1\coloneqq \hat{g}_2^{m_1}\cdots\hat{g}_{\ell+1}^{m_\ell}\cdot\hat{g}_{\ell+2}\in\hat{\GG}$
|
|
and $d_2\coloneqq \hat{g}_{\ell+3}^{m_1}\cdots\hat{g}_{2 \ell+2}^{m_\ell}\cdot\hat{g}_{2\ell+3}\in\hat{\GG}$.
|
|
To this end, choose
|
|
$r_1,r_2\sample\U(\Zp)$ and compute $\hat{D}_1=d_1\cdot \hat{g}^{r_1}$ and $\hat{D}_2=d_2\cdot \hat{g}^{r_2}$.
|
|
|
|
\item In order to prove knowledge of an opening of commitments $\hat{D}_1,\hat{D}_2\in\Gh$ to the same message $\vec{m}=(m_1,\ldots,m_\ell)\in\Zp^\ell$,
|
|
choose $s_1,s_2,u_1,\ldots,u_\ell \sample\U(\Zp)$
|
|
and compute $\hat{E}_1=\hat{g}_2^{u_1}\cdots\hat{g}_{\ell+1}^{u_\ell}\cdot \hat{g}^{s_1}$
|
|
and $\hat{E}_2=\hat{g}_{\ell+3}^{u_1}\cdots\hat{g}_{2 \ell+2}^{u_\ell}\cdot \hat{g}^{s_2}$.
|
|
|
|
\item Using the randomness $r_1,r_2 \in \Zp$ from step 1, define $\sigma_0 = \sigma_2^{r_1} \cdot \sigma_3^{r_2}$
|
|
and commit to $(\pi,\sigma_0 ,\sigma_1,\sigma_2,\sigma_3)\in\GG^5.$
|
|
For this purpose, choose $t_z,t_0,t_1,t_2,t_3\sample\U(\Zp)$ at random and set $C_z=\pi \cdot g^{t_z}$,
|
|
$C_i=\sigma_i \cdot g^{t_i}$, for $i \in \{0,\ldots,3\}$, and
|
|
$\hat{D}_0=\hat{g}_z^{t_z} \cdot \hat{g}_1^{t_1} \cdot \hat{D}_{1}^{t_2}
|
|
\cdot \hat{D}_{2}^{t_3} \cdot \hat{g}^{-t_0}.$
|
|
|
|
\item In order to prove (partial) knowledge of an opening to $(C_z,C_0,C_1,C_2,C_3,\hat{D}_0)$, compute
|
|
$\hat{E}_0=\hat{g}_z^{v_z} \cdot \hat{g}_1^{v_1} \cdot \hat{D}_{1}^{v_2}
|
|
\cdot \hat{D}_{2}^{v_3} \cdot \hat{g}^{-v_0}$
|
|
for random $v_z,v_0,v_1,v_2,v_3\sample \U(\Zp)$.
|
|
\item Prove that $C_0$ is well-formed relatively to the committed values in $C_1,C_2$ and the coins
|
|
$r_1,r_2 \in \Zp$ used in $\hat{D}_1,\hat{D}_2$. To this end, prove knowledge of the representation
|
|
$C_0=C_2^{r_1} \cdot C_3^{r_2} \cdot {g}^{t_4},$ where $t_4=t_0-r_1 \cdot t_2-r_2 \cdot t_3$. To do this, compute
|
|
$F_0=C_2^{s_1} \cdot C_3^{s_2} \cdot {g}^{v_4}$, for $v_4\sample \U(\Zp)$ and where $s_1,s_2 \in \Zp$ are the random coins used in $\hat{E}_1,\hat{E}_2$.
|
|
\item To prove that $t_4=t_0-r_1 \cdot t_2-r_2 \cdot t_3$, (re-)commit to $t_0,t_2,t_3,t_4 \in \Zp$ by picking $x_2,x_3,x_4\sample \U(\Zp)$ and computing
|
|
$$T_i=g^{t_i} \cdot f^{x_i} \qquad \forall i \in \{0,2,3, 4\}, $$ where $x_0=x_2 \cdot r_1+x_3 \cdot r_2+x_4$. Ensure that committed
|
|
variables coincide with those of previous steps by computing $$\{V_i=g^{v_i} \cdot f^{y_i}\}_{i \in \{0,2,3,4\} },$$ where
|
|
$y_0,y_2,y_3,y_4\sample \U(\Zp)$. To prove the equality $T_0=T_2^{r_1} \cdot T_3^{r_2} \cdot T_4$, re-use $s_1,s_2 \in \Zp$ from steps 2 and 5 to compute
|
|
$S_0=T_2^{s_1} \cdot T_3^{s_2}$.
|
|
\medskip
|
|
\item[~~~Finally,] keep $C_z\in\GG$ and all the random coins in $\mathsf{aux}$,
|
|
\item[~~~and] output
|
|
\begin{equation} \label{eq-comm-2}
|
|
\begin{aligned}
|
|
\mathsf{com}=\Bigl(
|
|
\{C_i\}_{i=0}^3, F_0, \{(T_i,V_i)\}_{i=0,2,3,4},~~~\\
|
|
S_0, \{(\hat{D}_i,\hat{E}_i)\}_{i=0}^2
|
|
\Bigr) \in \GG^{14} \times \hat{\GG}^{6}
|
|
\end{aligned}
|
|
\end{equation}
|
|
\end{enumerate}
|
|
%
|
|
\begin{description}
|
|
\item[\textsf{Challenge}] Given $\mathsf{com}$ as per (\ref{eq-comm-2}), pick $\rho\sample \U(\Zp) $ uniformly at random and return $\mathsf{chall}=\rho $.
|
|
\item[\textsf{Response}] On inputs $\mathsf{com}$, $\mathsf{aux}$ and $\mathsf{chall}=\rho$, compute: % the following elements over $\Zp$:
|
|
\end{description}
|
|
%set $t_5=[t_4-t_1r_1-t_2r_2 \!\mod p]$ and
|
|
\begin{enumerate}
|
|
\item $\bar{m}_i= \rho\cdot m_i + u_i $, for $i=1$ to $\ell$, $\bar{r}_1= \rho \cdot r_1 +s_1 $,
|
|
and $\bar{r}_2= \rho\cdot r_2 +s_2 $;
|
|
\item $w_z= \rho\cdot t_z + v_z $ and $w_i= \rho\cdot t_i + v_i $, for $i=0$ to $3$;
|
|
\item $w_4= \rho\cdot t_4 + v_4 $, where $t_4\coloneqq t_0-t_1 \cdot r_1-t_2 \cdot r_2$;
|
|
\item $z_i= \rho\cdot x_i + y_i $ for each $i \in \{0,2,3,4\}$. \smallskip
|
|
\item[~~~Output] $\mathsf{resp}\in \GG\times \Zp^{\ell+12}$ as
|
|
\begin{align*}
|
|
%\mathsf{resp}=
|
|
\bigl( C_z,\{\bar{m}_i\}_{i=1}^\ell,\bar{r}_1,\bar{r}_2,
|
|
w_z,\{w_i\}_{i=0}^4,\{z_i\}_{i=0,2,3,4} \bigr).
|
|
\end{align*}
|
|
\end{enumerate}
|
|
%
|
|
\begin{description}
|
|
\item[\textsf{Verify}] Given $(\mathsf{com};\mathsf{chall};\mathsf{resp})$ return $0$ if it does not parse correctly or if the following relations do not hold:
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item $(\hat{D}_1/\hat{g}_{\ell+2})^{\,\rho}\cdot\hat{E}_1
|
|
=\hat{g}_2^{\,\bar{m}_1}\cdots\hat{g}_{\ell+1}^{\,\bar{m}_\ell}\cdot g^{\bar{r}_1}$ and
|
|
$(\hat{D}_2/\hat{g}_{2\ell+3})^{\,\rho}\cdot\hat{E}_2
|
|
=\hat{g}_{\ell+3}^{\,\bar{m}_1}\cdots\hat{g}_{2 \ell+2}^{\,\bar{m}_\ell}\cdot g^{\bar{r}_2}$ ;
|
|
\item $\hat{D}_0^{\,\rho}\cdot\hat{E}_0
|
|
=\hat{g}_z^{w_z} \cdot \hat{g}_1^{w_1} \cdot \hat{D}_{1}^{w_2} \cdot \hat{D}_{2}^{w_3}
|
|
\cdot \hat{g}^{-w_0}$ and
|
|
$C_0^{\,\rho}\cdot F_0=C_2^{\,\bar{r}_1} \cdot C_3^{\,\bar{r}_2} \cdot {g}^{w_4}$.
|
|
\item $T_i^{\rho}\cdot V_i=g^{w_i}f^{z_i}$ for each $i \in \{0,2,3,4\}$ and
|
|
\begin{eqnarray} \label{last-ver-sig}
|
|
(T_0/T_4)^\rho \cdot S_0 = T_2^{\bar{r}_1} \cdot T_3^{\bar{r}_2}.
|
|
\end{eqnarray}
|
|
%\end{enumerate}
|
|
%
|
|
\item[~~~Then,] return $1$ if and only if
|
|
%
|
|
\begin{align} \label{eq-vrf-2}
|
|
\lefteqn{e(C_0,\hat{g}) \cdot e(g,\hat{D}_0) \cdot e(\Omega,\hat{g}_{2 \ell+4})^{-1}} \\ \nonumber
|
|
& \quad = \, e(C_1,\hat{g_1}) \cdot e(C_2,\hat{D}_1) %\\ \qquad
|
|
\cdot e(C_3,\hat{D}_2) \cdot e(C_z,\hat{g}_z) .
|
|
\end{align}
|
|
%
|
|
% and $0$ otherwise.
|
|
\end{enumerate}
|
|
|
|
It is worth noticing that no pairing evaluation is required until the final step of $\mathsf{Verify}$, which is almost as efficient as the verification of
|
|
underlying signatures.
|
|
Moreover, the prover's first message $\mathsf{com}$ is of constant-size and the communication complexity of the protocol exceeds the length of the witness by
|
|
a constant additive overhead.
|
|
|
|
|
|
|
|
\begin{theorem}
|
|
The above interactive scheme is a secure $\Sigma$-protocol for the language $L_{sig}$ induced by the relation
|
|
$R_{sig}(\mathsf{pk},(\vec{\sigma},\vec{m}))=1$ if and only if $\mathsf{Verify}'(\mathsf{pk},\vec{\sigma},\vec{m})=1$,
|
|
where $(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verify}')$ is the signature of Section~\ref{scal-sig}.
|
|
\end{theorem}
|
|
|
|
|
|
\begin{proof}
|
|
\emph{Correctness.}
|
|
Expanding an honestly generated $\hat{D}_0=\hat{g}_z^{t_z} \cdot \hat{g}_1^{t_1} \cdot \hat{D}_1^{t_2} \cdot
|
|
\hat{D}_2^{t_3} \cdot \hat{g}^{-t_0}$ in equation (\ref{eq-vrf-2}) and regrouping the pairing factors gives
|
|
%
|
|
\begin{multline*} %\label{eq-vrf-corr-1}
|
|
\quad
|
|
e(C_0\cdot {g}^{-t_0},\hat{g}) \cdot e(\Omega,\hat{g}_{2\ell+4})^{-1} \\ %& \quad \!\!
|
|
= \, e(C_1\cdot {g}^{-t_1},\hat{g_1}) \cdot e(C_2\cdot {g}^{-t_2},\hat{D}_1) \\ %\nonumber &
|
|
\cdot \, e(C_3\cdot {g}^{-t_3},\hat{D}_2) \cdot e(C_z\cdot {g}^{-t_z},\hat{g}_z) .
|
|
\end{multline*}
|
|
%
|
|
Now, expanding the commitments to group elements in $\GG$ reduces this equation to
|
|
%
|
|
\begin{align*} %\label{eq-vrf-corr-2}
|
|
\lefteqn{e(\sigma_2^{r_1} \cdot \sigma_3^{r_2},\hat{g}) \cdot e(\Omega,\hat{g}_{2 \ell+4})^{-1} }
|
|
\\ %\nonumber
|
|
& \quad = \, e(\sigma_1,\hat{g_1}) \cdot e(\sigma_2,\hat{D}_1) \cdot e(\sigma_3,\hat{D}_2) \cdot e(\pi ,\hat{g}_z)
|
|
\end{align*}
|
|
%
|
|
which holds true for valid witnesses when $\hat{D}_1=d_1 \cdot \hat{g}^{r_1}$ and $\hat{D}_2=d_2 \cdot \hat{g}^{r_2}$.
|
|
Remaining verifications of items 1,2,3 follow from the correctness of the built-in $\Sigma$-protocols.
|
|
\medskip
|
|
|
|
\scbf{Special-Soundness.}
|
|
We assume two accepting transcripts $(\mathsf{com},\rho,\mathsf{resp})$, $(\mathsf{com},\rho',\mathsf{resp}')$ with $\rho \neq \rho'$.
|
|
The special soundness of the sub-protocols involving $\hat{D}_1,\hat{D}_2$ (with $\hat{E}_1,\hat{E}_2$)
|
|
--\,consisting of steps 1 and 2 of \textsf{Commit} and step 1 of \textsf{Verify}\,--
|
|
ensures the extraction of $m_1,\ldots,m_\ell,r_1,r_2 $ satisfying
|
|
$\hat{D}_1=d_1\cdot\hat{g}^{r_1}$, where $d_1=\hat{g}_2^{m_1}\cdots \hat{g}_{\ell+1}^{m_\ell}\cdot\hat{g}_{\ell+2}$, and
|
|
$\hat{D}_2=d_2\cdot\hat{g}^{r_2}$, where $d_2=\hat{g}_{\ell+3}^{m_1}\cdots\hat{g}_{2 \ell+2}^{m_\ell}\cdot\hat{g}_{2\ell+3}$.
|
|
From step 2 of $\mathsf{Verify}$, a similar argument on $\hat{D}_0$ (with $\hat{E}_0$) implies the extractability of $(t_z,t_0,t_1,t_2,t_3,t_4)$ such
|
|
that $\hat{D}_0={\hat{g}_z}^{t_z} \cdot {\hat{g}_1}^{t_1} \cdot {\hat{D}_{1}}^{t_2} \cdot {\hat{D}_{2}}^{t_3} \cdot {\hat{g}}^{-t_0}.$
|
|
Moreover, together with previously extracted $(r_1,r_2)$, step 2 of $\mathsf{Verify}$ also guarantees that $t_4$ satisfies $C_0=C_2^{r_1} \cdot C_3^{r_2} \cdot g^{t_4}$.
|
|
%
|
|
|
|
We now state that quantities $\{\sigma_i=C_i\cdot {g}^{-t_i}\}_{i \in \{1,2,3\}}$ and $\pi=C_z\cdot {g}^{-t_z}$ satisfy (\ref{sig-ver-1}),
|
|
so that, together with $\vec{m}=(m_1,\ldots,m_\ell)$, they form a valid witness for $R_{sig}$. Namely,
|
|
$({\sigma},\vec{m})=((\sigma_1,\sigma_2,\sigma_3,\pi),(m_1,\ldots,m_\ell))$ is a valid message-signature pair.
|
|
|
|
To see this, define $\sigma_0=C_0\cdot g^{-t_0}$. Since equation (\ref{eq-vrf-2}) holds by hypothesis, if we expand
|
|
all commitments using extracted values, we find
|
|
%
|
|
\begin{align*} %\label{eq-sound-1}
|
|
\lefteqn{e(\sigma_0,\hat{g}) \cdot e(\Omega,\hat{g}_{2 \ell+4})^{-1}} \\ %\nonumber
|
|
& \; = \, e(\sigma_1,\hat{g_1}) \cdot e(\sigma_2,d_1\cdot \hat{g}^{r_1})
|
|
\cdot e(\sigma_3,d_2\cdot \hat{g}^{r_2}) \cdot e(\pi,\hat{g}_z) .
|
|
\end{align*}
|
|
%
|
|
We are thus left with showing that $\sigma_0=\sigma_2^{r_1} \cdot \sigma_3^{r_2}$ or, equivalently,
|
|
$e(\sigma_0,\hat{g})=e(\sigma_2,\hat{g}^{r_1}) \cdot e(\sigma_3,\hat{g}^{r_2})$. Remember that, from step 2 of $\mathsf{Verify}$, we know that
|
|
extracted $(r_1,r_2,t_4) \in \Zp^3$ form a representation of $C_0$ {w.r.t.}
|
|
the base $(C_0,C_2,g)$: i.e., $C_0=C_2^{r_1} \cdot C_3^{r_2} \cdot g^{t_4}$, which, from the definition of
|
|
$\sigma_0,\sigma_2,\sigma_3$, yields
|
|
$\sigma_0\cdot g^{t_0}=\sigma_2^{r_1} \cdot \sigma_3^{r_2} \cdot g^{t_2 \cdot r_1+t_3 \cdot r_2+t_4}$. Hence, we are done if we can show that $t_0=t_2r_1+t_3r_2+t_4$. But this exactly what step 3 of $\mathsf{Verify}$ and the
|
|
special soundness of the sub-protocol involving $(T_0,T_2,T_3,T_4)$ tells us. First, we have a representation of these
|
|
$T_i$'s {w.r.t.} the basis $(g,f)\in \GG^2$ which guarantees that we are working on the already extracted $(t_0,t_2,t_3,t_4)$ involved in the expressions of $\hat{D}_0$ and
|
|
$C_0$.
|
|
Second, the verification equation (\ref{last-ver-sig}) ensures that $T_0=T_2^{r_1} \cdot T_3^{r_2} \cdot T_4$ and the final result follows by replacing them by their
|
|
representation.
|
|
\medskip
|
|
|
|
\scbf{Perfect SHVZK.}
|
|
To show this property we must build a simulator that, on input of a challenge
|
|
$\mathsf{chall}=\rho \in_R \Zp$, emulates a valid transcript without any witness.
|
|
First, we need to compute a random tuple $C_z,\{C_i\}_{i=0}^3,\{\hat{D}\}_{i=0}^2$ constrained to satisfy the verification equation (\ref{eq-vrf-2}).
|
|
|
|
|
|
From the identity $e(\Omega,\hat{g}_{2\ell+4})^{-1}=e(\Omega^{-1},\hat{g}_{2\ell+4})$ we first pick
|
|
$a_0,a_1,a_2,a_z\gets\Zp$, $\hat{D}_1\gets\Gh$ and we have $e(\Omega,\hat{g}_{2\ell+4})^{-1}=
|
|
e(\Omega^{-1},\hat{g}_{2\ell+4}\cdot\hat{g}^{a_0}\hat{g}_1^{a_1}\hat{D}_1^{a_2}\hat{g}_z^{a_z})
|
|
\cdot e(\Omega^{a_0},\hat{g})\cdot e(\Omega^{a_1},\hat{g}_1)\cdot e(\Omega^{a_2},\hat{D}_1)
|
|
\cdot e(\Omega^{a_z},\hat{g}_z)$, so that we can set $C_0=\Omega^{-a_0}$,
|
|
$C_1=\Omega^{a_1}$, $C_2=\Omega^{a_2}$ and $C_z=\Omega^{a_z}$.
|
|
Let $\hat{B}\coloneqq \hat{g}_{2\ell+4}\cdot\hat{g}^{a_0}\hat{g}_1^{a_1}\hat{D}_1^{a_2}\hat{g}_z^{a_z}$.
|
|
Now, we can introduce the constant $g \in \GG$ in the equation by picking $a_g\gets\Zp$ since
|
|
$e(\Omega^{-1},\hat{B})=e(\Omega^{-1} \cdot g^{a_g},\hat{B})\cdot e(g,\hat{B}^{-a_g})$. Then, we finally set
|
|
$\hat{D}_0=\hat{B}^{a_g}$, $\hat{D}_2=\hat{B}^{a_3}$ and $C_3=(\Omega^{-1} \cdot g^{a_g})^{1/a_3}$ for a
|
|
random $a_3\gets\Zp$.
|
|
%
|
|
|
|
To complete the simulated transcript, we run a parallel execution of the simulators of all $\Sigma$-protocols used as subroutines.
|
|
|
|
More explicitly, first pick $\rho\sample \U(\Zp)$ and
|
|
\[ \bar{m}_1, \ldots, \bar{m}_\ell, \bar{r}_1, \bar{r}_2, w_z, w_0, \ldots, w_4, z_0, z_2, z_3, z_4\sample \U(\Zp).\]
|
|
Also,
|
|
choose $T_0, T_2, T_3, T_4 \sample \U(\GG)$ and do the following:
|
|
\begin{enumerate}
|
|
\item Compute \[\hat{E}_1 = (\hat{D}_1/\hat{g}_{\ell+2})^{\,-\rho}\cdot
|
|
\hat{g}_2^{\,\bar{m}_1}\cdots\hat{g}_{\ell+1}^{\,\bar{m}_\ell}\cdot g^{\bar{r}_1}\] and, similarly,
|
|
\[\hat{E}_2 = (\hat{D}_2/\hat{g}_{2\ell+3})^{\,-\rho}\cdot
|
|
\hat{g}_{\ell+3}^{\,\bar{m}_1}\cdots\hat{g}_{2 \ell+2}^{\,\bar{m}_\ell}\cdot g^{\bar{r}_2};\]
|
|
\item Compute \[F_0 = C_0^{\,-\rho}\cdot C_2^{\,\bar{r}_1} \cdot C_3^{\,\bar{r}_2} \cdot {g}^{w_4}\]
|
|
as well as
|
|
\[\hat{E}_0 = \hat{D}_0^{\,\rho}\cdot \hat{g}_z^{w_z} \cdot \hat{g}_1^{w_1}
|
|
\cdot \hat{D}_{1}^{w_2} \cdot \hat{D}_{2}^{w_3} \cdot \hat{g}^{-w_0} ; \]
|
|
\item Compute \[V_i = T_i^{-\rho}\cdot g^{v_i}f^{z_i},\] for each $i \in \{0,2,3,4\}$, and
|
|
\[S_0 = (T_0/T_4)^{-\rho} \cdot T_2^{\bar{r}_1} \cdot T_3^{\bar{r}_2}.\]
|
|
\end{enumerate}
|
|
This concludes the proof. % TODO: ugly
|
|
\end{proof}
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
\subsection{Signing a Committed Message}
|
|
|
|
At a high level, the protocol involves a committer who wants to get a signature on ${\mathbf{m}}=(m_1,\ldots,m_\ell)$ and first computes a commitment of the form $c_v=v_1^{m_1}\cdots v_\ell^{m_\ell}\cdot u^{r}$, where $u$ is the extra public parameter (with unknown discrete log). The signer gives back elements of the form $\tau_1=g^\omega c_v^s$, $\tau_2=g^s$, $\tau_3=h^s$ which is almost the desired signature. To get the component $\sigma_1$ of the right form relatively to $\tau_2,\tau_3$ the committer has to remove the factor $u^{rs}$ from $\tau_1$. Then, the signer also sends $\tau_0=u^s$ to enable removing $\tau_0^r$.
|
|
In the protocol some randomizing steps are included as well as other additional components allowing the committer to extract $\pi$, the \QANIZK part of the signature. In the security proof of the protocol we thus have to show that the additional value $\tau_0=u^s$ does not affect the unforgeability of the signature. \smallskip
|
|
|
|
\textbf{The protocol.}
|
|
%
|
|
At the beginning of a new run of the protocol, the committer has a vector ${\mathbf{m}}=(m_1,\ldots,m_\ell)$, the public-key of the signature scheme and the extra generator $u\in\GG$ (which can be a hashed point), the signer also has the secret key of the signature scheme but not ${\mathbf{m}}$.
|
|
To get a signature on ${\mathbf{m}}$, the committer picks $r\sample \U(\Zp)$ and computes a perfectly hiding commitment $c_v=v_1^{m_1}\cdots v_\ell^{m_\ell}\cdot u^{r}\in\GG$.
|
|
Besides, it also computes the elements $c_z = z_2^{m_1}\cdots z_{\ell+1}^{m_\ell}\cdot u^{t_z}$.
|
|
%and $c_r = r_2^{m_1}\cdots r_{\ell+1}^{m_\ell}\cdot u^{t_r}$.
|
|
The signer receives these commitments and they both engage in an interactive proof of knowledge of an equal representation of $c_v$ relatively to the basis $(v_1,\ldots,v_\ell;u)$ and $c_z$ relatively to the basis $(z_2,\ldots,z_{\ell+1};u)$,
|
|
%and $c_r$ relatively to the basis $(r_2,\ldots,r_{\ell+1};u)$,
|
|
where the signer plays the role of the verifier.
|
|
Depending on the success of the proof the signer computes what we can call a ``pre-signature'' consisting of the following group elements
|
|
%
|
|
\begin{align*}
|
|
\tau_1 & = g^\omega\cdot(c_v\cdot w)^s , &
|
|
\tau_3 & = h^s , & \pi_0 & = z_1^\omega \cdot c_z^s \cdot z_{\ell+2}^s , \\
|
|
\tau_2 & = g^s , & \tau_0 & = u^s , &
|
|
%r_0 & = r_1^\omega \cdot c_r^s \cdot r_{\ell+2}^s ,
|
|
\end{align*}
|
|
%and $(z_d,r_d)=(z_{\ell+3}^s,r_{\ell+3}^s)$,
|
|
for a random $s\sample \U(\Zp)$. In the final step, the user received the pre-signature, then picks $s'\sample \U(\Zp)$ and computes
|
|
$(\sigma_1, \sigma_2, \sigma_3, \pi) \in \GG^4$ as follows
|
|
\begin{align*}
|
|
\sigma_1 & = \tau_1 \cdot\tau_0^{-r}
|
|
\cdot(v_1^{m_1}\cdots v_\ell^{m_\ell}\cdot w)^{s'}, &
|
|
\sigma_2 & = \tau_2 \cdot g^{s'} , \\
|
|
\pi & = \pi_0 \cdot \tau_0^{-t_z}
|
|
\cdot (z_2^{m_1}\cdots z_{\ell+1}^{m_\ell}\cdot z_{\ell+2})^{s'}, &
|
|
\sigma_3 & = \tau_3 \cdot h^{s'} .
|
|
%\\ r & = r_0 \cdot \tau_0^{-t_r} \cdot (r_2^{m_1}\cdots r_{\ell+1}^{m_\ell}\cdot r_{\ell+2})^{s'} .
|
|
\end{align*}
|
|
Finally the user checks the validity of the signature. Depending on the validity, the user outputs the signature or a failure symbol $\bot$.
|
|
|
|
We notice that the number of transmitted group elements is constant and no pairing is needed before the signature verification phase.
|
|
In comparison, the construction of \cite{CL02a} requires groups of larger hidden order and their protocol for signing committed message blocks requires a linear number of range proofs. \smallskip
|
|
|
|
\textbf{Security.}
|
|
%
|
|
We briefly sketch the proof of the above protocol in front of malicious entities since classical arguments can be applied. Assuming that the committer uses secure ZKPK and does not output $\bot$, a malicious signer which receives perfectly hiding commitments $c_v,c_z$ cannot tell apart an honest proof from a simulated proof. Consequently the signer learns nothing from ${\mathbf{m}}$ during the execution of the protocol.
|
|
In the other case, we have to show that a corrupted committer remains unable to produce valid signature on a new vector ${\mathbf{m}^\star}$. First, since the generation of $u$ is not under the controlled of the committer but of the random oracle, $u$ can be made independent of rest of $\mathsf{pk}$. Then, we only need to show that the signature remains unforgeable when $\tau_0$ is given in the signature. Since ${\mathbf{m}}$ and $s$ can be extracted from the proof of knowledge the reduction can output a signature on ${\mathbf{m}}$. Moreover it is easy to see from the security proof (in \cref{sse:sigmasig-qa-nizk}) of the signature how this additional element can be simulated. Actually the only place in the reduction where $\tau_0$ could not be computed directly as $u^s$ for a known $s$ is when the challenger $\bdv$ has to embed an $\SXDH$ challenge in a simulated signature. Given ($g,h,g^b,h^{b+c}$), $\bdv$ can compute $u=g^{a_u}h^{b_u}$ from random $a_u,b_u\gets\Zp$ and program the random oracle to output this element $u$ as the specification of the public-key would do. Then to simulate $\tau_0$ $\bdv$ simply has to compute $\tau_0=(g^b)^{a_u}(h^{b+c})^{b_v}=u^bh^{c\cdot b_v}$ which is $u^b$ or random. The rest of the reduction remains unchanged since the value $a_u,b_u$ are completely independent of those already described in the sketch of proof in \cref{sse:sigmasig-qa-nizk}. \smallskip
|
|
|
|
\textbf{Remark.}
|
|
%
|
|
Since a malicious signer may know the simulation trapdoor $\mathsf{tk}=\{\chi_i\}_{i=1}^{2\ell+4}$ of the underlying \QANIZK argument, he could produce valid signature so that $\log_g \sigma_2\neq\log_h \sigma_3$. Then, if the committer later needs to proof knowledge of the received signature it then has to use the sigma protocol of Section~\ref{scal-sig} where both $\sigma_2$ and $\sigma_3$ only appear in committed form.
|
|
|
|
|
|
|
|
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~%
|
|
\section{The Dynamic Group Signatures Scheme} \label{sse:sigmagis-gsig}
|
|
\addcontentsline{tof}{section}{\protect\numberline{\thesection} Construction de la signature de groupe dynamique}
|
|
|
|
We adapt the protocol of section~\ref{scal-sig} to build a dynamic group
|
|
signature~\cite{BSZ05,KY06}.
|
|
At a high level, each group member obtains a membership certificate consisting of a signature $(\sigma_1,\sigma_2,\sigma_3,\pi)$ on
|
|
a message $\ID \in \Zp$ which is only known to the group member. During the joining protocol, each group member thus obtains a signature
|
|
on a committed message $\ID \in \Zp$. Here, we use a deterministic commitment to $\ID$, which suffices to ensure security against framing attacks and allows for a better
|
|
efficiency. When signing a message, each group member verifiably encrypts the components $(\sigma_1,\pi)$ of his membership certificate that depend on $\ID$ (and not $\sigma_2,\sigma_3$ which can be assumed to be honestly computed here, unlike in the previous section).
|
|
For the sake of efficiency, we use a randomness re-using \cite{BBKS07} variant of the Cramer-Shoup encryption scheme \cite{CS98} whereby $\sigma_1$ and $\pi$ are both encrypted using
|
|
the same encryption exponent $\theta \in \Zp$. For public verifiability purposes, the validity of Cramer-Shoup ciphertexts is demonstrated using
|
|
$\Sigma$-protocols and the Fiat-Shamir heuristic \cite{FS86} (somewhat in the fashion of \cite{SG98}) rather than designated verifier $\NIZK$ proofs \cite{CS98}.
|
|
|
|
In the join protocol, the user proves knowledge of his membership secret $\ID \in \Zp$ in a zero-knowledge manner, which restricts the group manager to sequentially interact
|
|
with prospective users. However, this limitation can be removed using an extractable commitment as in \cite{DP06}.
|
|
|
|
\begin{description}
|
|
\item[\textsf{Keygen}$(\lambda, N)$:] given $\lambda \in \NN$,
|
|
and the maximum number of users $N \in \poly(\lambda)$, choose asymmetric
|
|
bilinear groups $\mathsf{cp}=(\GG, \Gh, \GT,p)$ of order $p > 2^\lambda$.
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item Generate a key pair $(\pk_s, \sk_s)$ for the scheme of
|
|
section~\ref{scal-sig} for a one-block message (i.e., $\ell=1$). The secret key is
|
|
$\sk_s = \omega$, while the public key is
|
|
\begin{align*}
|
|
\pk_s = \bigl( \mathsf{cp},~g,~h,~\hat{g}, ~\vec{v}=(v,w),
|
|
~\Omega=h^\omega,~\mathsf{crs} \bigr),
|
|
\end{align*}
|
|
where %$\Omega=h^\omega$ and
|
|
$\mathsf{crs} = \big(\{{z}_j\}_{j=1}^{3}, \hat g_z, \{\hat g_i\}_{i=1}^{6} \big)$.
|
|
|
|
\item Pick $x_z, y_z, x_\sigma, y_\sigma, x_\ID, y_\ID \sample \U(\Zp)$ and set
|
|
\begin{align*}
|
|
X_z & = g^{x_z} h^{y_z}, & X_\sigma & = g^{x_\sigma} h^{y_\sigma}, & X_\ID & = g^{x_\ID} h^{y_\ID}.
|
|
\end{align*}
|
|
|
|
\item Choose a hash function $H : \bit^* \times \GG^{10} \times \GT \to \Zp$
|
|
that will be modeled as a random oracle.
|
|
|
|
\item Define
|
|
$\gspk = \bigl\{ \pk_s, X_z, X_\sigma, X_\ID \bigr\} $ to be the group public key.
|
|
The group manager's private key is $\mathcal{S}_\GM = \omega = \sk_s$ whereas the opening authority's private key consists of
|
|
$ \mathcal{S}_\mathrm{OA} = \bigl(x_z, y_z, x_\sigma, y_\sigma, x_\ID, y_\ID \bigr)$.
|
|
\end{enumerate}
|
|
%
|
|
\begin{description}
|
|
\item[\textsf{Join}$^{(\GM, \U_i)}$:] The group manager $\GM$, and the
|
|
prospective user $\U_i$ run the following interactive protocol:
|
|
%$[ \mathsf{J}_{\user}(\lambda, \gspk), \mathsf{J}_\GM(\lambda, St, \gspk, \mathcal{S}_{\GM}) ]$
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item $\U_i$ chooses ${\ID \sample \U(\Zp)}$ and sends the following to
|
|
$\GM$: $(V_\ID, Z_{\ID}, \hat G_{2, \ID}, \hat G_{4, \ID}) =
|
|
(v^\ID, z_2^\ID, \hat g_2^\ID, \hat g_4^\ID)$
|
|
|
|
\item $\GM$ checks that $V_\ID$ does not appear in any transcript of
|
|
$St$ and abort if it does. Otherwise (i.e., if $V_\ID$ is fresh),
|
|
$\GM$ verifies that: for $k=2,4$,
|
|
\begin{align*}
|
|
e(V_\ID,\hat g_k) & \iseq e( v, \hat G_{k,\ID}) ,
|
|
& e(Z_{\ID},\hat g_k) & \iseq e( z_2, \hat G_{k,\ID}) .
|
|
%\\
|
|
%& e(V_\ID, \hat G_{4,\ID}^{-1}) &\iseq 1.
|
|
\end{align*}
|
|
If all tests pass, samples a fresh index $i \in \Zp$ and sends it to
|
|
$\U_i$, otherwise abort.
|
|
|
|
\item $\U_i$ runs an interactive zero-knowledge proof of knowledge of
|
|
$\ID =\log_v(V_\ID)$ in interaction with $\GM$. For instance, the
|
|
4-round protocol of Cramer~\textit{et al.}~\cite{CDM00} can be used for
|
|
this purpose. Let $\pi_K(\ID)$ denote the interaction transcript.
|
|
|
|
\item $\GM$ uses $V_\ID=v^{\ID}$ to sign $\ID$ using the scheme of
|
|
section~\ref{scal-sig}: i.e., $\GM$ picks $s \sample \U(\Zp)$, and
|
|
uses $\mathcal{S}_\GM = \omega$ to compute
|
|
$\sigma_1= g^\omega\cdot(V_\ID \cdot w)^s= g^\omega \cdot (v^\ID \cdot w)^s$
|
|
and
|
|
\begin{align*}
|
|
\sigma_2 & = g^s, & \sigma_3 & = h^s.
|
|
\end{align*}
|
|
Then $\GM$ uses $Z_{\ID}$ to generate the \QANIZK proof $\pi\in \GG$ as
|
|
\begin{align*}
|
|
\pi &= z_1^\omega \cdot (Z_{\ID} \cdot z_3)^s
|
|
= z_1^\omega \cdot (z_2^\ID \cdot z_3)^s
|
|
\end{align*}
|
|
and finally sends
|
|
$\crt_i = (i, V_\ID, \sigma_1, \sigma_2, \sigma_3, \pi)$
|
|
|
|
\item Finally $\GM$ and $\mathcal{U}_i$ respectively store
|
|
\begin{align} \label{gsig-trans}
|
|
\!\!\!\!\transcript_i & \! = \!
|
|
\Bigl(\! \bigl( Z_{\ID}, \hat G_{2,\ID}, \hat G_{4,\ID} \bigr), \pi_K(\ID),\crt_i \!\Bigr)
|
|
\end{align}
|
|
and $(\crt_i,\scr_i) =\bigl( (i, V_\ID, \sigma_1, \sigma_2, \sigma_3, \pi), \ID \bigr)$. %
|
|
\end{enumerate}
|
|
%
|
|
\begin{description}
|
|
\item[\textsf{Sign}$(\gspk, \scr_i, \crt_i, M)$:] Given a message $M \in \bit^*$ and a secret $\scr_i = \ID$, the user $\U_i$
|
|
does the following:
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item Re-randomize the certificate $\crt_i$. Namely, choose $r \sample \U(\Zp)$ and compute $\tilde \sigma_2 = \sigma_2 \cdot g^r$, $\tilde \sigma_3 = \sigma_3 \cdot h^r$,
|
|
$\tilde \sigma_1 = \sigma_1 \cdot (v^\ID \cdot w)^r$, $\tilde \pi = \pi \cdot (z_2^\ID \cdot z_3)^r$.
|
|
|
|
\item Encrypt elements $\tilde \pi$, $\tilde \sigma_1$ and $v^\ID$ from the membership certificate.
|
|
Specifically, choose $\theta \sample \U(\Zp)$ and compute the Cramer-Shoup ciphertext
|
|
$C_{\mathsf{CS}}=(C_1,C_2,C_z,C_{\sigma},C_{\ID})$, where $C_1 = g^\theta$, $C_2 = h^\theta$,
|
|
\begin{align*}
|
|
C_z & = \tilde \pi \cdot X_z^\theta, &
|
|
C_\sigma & = \tilde \sigma_1 \cdot X_\sigma^\theta, &
|
|
C_\ID & = v^\ID \cdot X_\ID^\theta.
|
|
\end{align*}
|
|
|
|
\item Then, prove knowledge of $(\ID, \theta) \in \Zp^2$ such that
|
|
\begin{align*} %\label{sham-rel-1}
|
|
C_1 & = g^\theta ,&
|
|
C_2 & = h^\theta, &
|
|
C_\ID & = v^\ID \cdot X_\ID^\theta, %\quad
|
|
\end{align*}
|
|
% and
|
|
\begin{align*} %\label{sham-rel-3}
|
|
\lefteqn{\big(e(C_z, \hat g_z) \cdot e(C_\sigma, \hat g_1) \cdot e(\tilde \sigma_2, \hat g_3)
|
|
\cdot e(\tilde \sigma_3, \hat g_5) \cdot e(\Omega, \hat g_6) \big)} \\ %\nonumber
|
|
& = \big( e(X_z, \hat g_z) \cdot e(X_\sigma, \hat g_1) \big)^{\theta}
|
|
\cdot\big(e(\tilde \sigma_2, \hat g_2) \cdot e(\tilde \sigma_3, \hat g_4) \big)^{-\ID} .
|
|
\end{align*}
|
|
Namely, sample random $r_\ID, r_\theta \sample \U(\Zp)$, compute
|
|
\begin{eqnarray*}
|
|
&\begin{aligned}
|
|
R_1 &= g^{r_\theta}, &
|
|
R_2 &= h^{r_\theta}, &
|
|
R_3 &= v^{r_\ID} \cdot X_\ID^{r_\theta},
|
|
\end{aligned}\\
|
|
&\begin{aligned}
|
|
R_4 &= \big( e(X_z, \hat g_z) \cdot e(X_\sigma, \hat g_1) \big)^{r_\theta}
|
|
\cdot \big(e(\tilde \sigma_2, \hat g_2) \cdot e(\tilde \sigma_3, \hat g_4) \big)^{-r_\ID}
|
|
\end{aligned}
|
|
\end{eqnarray*}
|
|
and then define $c$ as $c = H(M, C_{\mathsf{CS}},\tilde{\sigma}_2,\tilde{\sigma}_3, R_1, R_2, R_3, R_4)$.
|
|
Finally compute the two responses $s_\theta = r_\theta + c \cdot \theta$, $s_\ID = r_\ID + c \cdot \ID$~both in~$\Zp$.
|
|
\item Return the signature $\Sigma $ which consists of
|
|
\begin{equation} \label{gsig-sigma}
|
|
\hspace{-1.25em} \Sigma=(C_{\mathsf{CS}}, \tilde \sigma_2, \tilde \sigma_3, c, s_\ID, s_\theta)
|
|
\in\GG^7\times\Zp^3
|
|
\end{equation}
|
|
%
|
|
\end{enumerate}
|
|
%
|
|
\begin{description}
|
|
\item[\textsf{Verify}$(\gspk, M, \Sigma)$:]
|
|
Parse the signature $\Sigma$ as in \eqref{gsig-sigma} and $C_{\mathsf{CS}}$ as
|
|
$(C_1, C_2, C_z, C_\sigma, C_\ID)$.
|
|
Then, output 1 if the the zero-knowledge proof verifies. Namely,
|
|
\end{description}
|
|
\begin{enumerate}
|
|
\item Compute the group elements $R_1$, $R_2$, $R_3\in\GG$ as:
|
|
%\begin{eqnarray}
|
|
%&\begin{gathered}
|
|
%\begin{aligned}
|
|
%R_1 & = g^{s_\theta} \cdot C_1^{-c}, &
|
|
%R_2 & = h^{s_\theta} \cdot C_2^{-c},
|
|
%\end{aligned}\\
|
|
%\begin{aligned}
|
|
%R_3 & = v^{s_\ID} \cdot X_\ID^{s_\theta} \cdot C_\ID^{-c}, \label{gsig-verif-1}
|
|
%\end{aligned}
|
|
%\end{gathered} \\
|
|
%&\begin{aligned}
|
|
%R_4 &= \big( e(X_z, \hat g_z) \cdot e(X_\sigma, \hat g_1) \big)^{s_\theta} \\&
|
|
%\qquad \cdot \big(e(\tilde \sigma_2, \hat g_2) \cdot e(\tilde \sigma_3, \hat g_4) \big)^{-s_\ID} \\&
|
|
%\quad \cdot \big(e(C_z, \hat g_z) \cdot e(C_\sigma, \hat g_1)\\&
|
|
%\qquad \cdot e(\tilde \sigma_2, \hat g_3) \cdot e(\tilde \sigma_3, \hat g_5) \big)^{-c}
|
|
%\end{aligned} \label{gsig-verif-2}
|
|
%\end{eqnarray}
|
|
%
|
|
\begin{eqnarray}
|
|
&\begin{gathered}
|
|
\begin{aligned}
|
|
R_1 & = g^{s_\theta} \cdot C_1^{-c}, & \;
|
|
R_2 & = h^{s_\theta} \cdot C_2^{-c},
|
|
\end{aligned}\\
|
|
\begin{aligned}
|
|
R_3 & = v^{s_\ID} \cdot X_\ID^{s_\theta} \cdot C_\ID^{-c}; \label{gsig-verif-1}
|
|
\end{aligned}
|
|
\end{gathered}
|
|
\end{eqnarray}
|
|
and the element $R_4\in\GT$ as
|
|
\begin{equation}
|
|
\label{gsig-verif-2}
|
|
\begin{aligned}
|
|
\lefteqn{\big( e(X_z, \hat g_z) \cdot e(X_\sigma, \hat g_1) \big)^{s_\theta}
|
|
\cdot \big(e(\tilde \sigma_2, \hat g_2) \cdot e(\tilde \sigma_3, \hat g_4) \big)^{-s_\ID}} \\
|
|
& \quad \cdot \big(e(C_z, \hat g_z) \cdot e(C_\sigma, \hat g_1)
|
|
\cdot e(\tilde \sigma_2, \hat g_3) \cdot e(\tilde \sigma_3, \hat g_5)
|
|
\cdot e(\Omega, \hat g_6) \big)^{-c}.
|
|
\end{aligned}
|
|
\end{equation}
|
|
|
|
\item Return $1$ if
|
|
$
|
|
c = H(M,C_{\mathsf{CS}},\tilde{\sigma}_2,\tilde{\sigma}_3, R_1, R_2, R_3, R_4)$ and $0$ otherwise.
|
|
\end{enumerate}
|
|
%
|
|
\begin{description}
|
|
\item[\textsf{Open}$(\gspk, \mathcal{S}_\OA, M, \Sigma)$:] Given a message-signature pair $(M,\Sigma)$
|
|
and the $\mathsf{OA}$'s private key $S_\mathrm{OA} = \bigl(x_z, y_z, x_\sigma, y_\sigma, x_\ID, y_\ID \bigr)$:
|
|
\end{description}
|
|
\begin{enumerate}
|
|
%\item Parse the signature $\Sigma$ as per~\eqref{gsig-sigma} and $\mathcal{S}_\OA$ as $ \bigl(x_z, y_z, x_r, y_r, x_\sigma, y_\sigma, x_\ID, y_\ID \bigr)$.
|
|
\item Decrypt $C_{\mathsf{CS}}=(C_1, C_2, C_z, C_\sigma, C_\ID)$ by computing
|
|
% $\sigma_1 = C_\sigma \cdot C_1^{-x_\sigma} \cdot C_2^{-y_\sigma}$,
|
|
% $ \pi = C_z \cdot C_1^{-x_z} \cdot C_2^{-y_z}$ and $V_\ID =C_\ID \cdot C_1^{-x_\ID} C_2^{-y_\ID}$.
|
|
\begin{gather*}
|
|
\sigma_1 = C_\sigma \cdot C_1^{-x_\sigma} \cdot C_2^{-y_\sigma}, \qquad
|
|
\pi = C_z \cdot C_1^{-x_z} \cdot C_2^{-y_z},\\
|
|
V_\ID =C_\ID \cdot C_1^{-x_\ID} C_2^{-y_\ID}.
|
|
\end{gather*}
|
|
%\begin{align*}
|
|
% \tilde \sigma_1 &= C_\sigma \cdot C_1^{-x_\sigma} \cdot C_2^{-y_\sigma}, &
|
|
% r &= C_r \cdot C_1^{-x_r} \cdot C_2^{-y_r},& \\
|
|
% z &= C_z \cdot C_1^{-x_z} \cdot C_2^{-y_z}, &
|
|
% V_\ID &=C_\ID \cdot C_1^{-x_\ID} C_2^{-y_\ID}. &
|
|
%\end{align*}
|
|
\item Search $V_\ID$ in the database of joining transcripts~\eqref{gsig-trans} and
|
|
check that it corresponds to a
|
|
valid signature $\big(\tilde \sigma_1, \tilde \sigma_2, \tilde \sigma_3, \tilde \pi \big)$ for the
|
|
committed value $V_\ID$. If so, return the corresponding $i$, otherwise return $\bot$. \medskip
|
|
|
|
% \item Look for $V_\ID$ in the records parsed as in~\eqref{gsig-trans}, and checks that
|
|
% $\big(\tilde \sigma_1, \tilde \sigma_2, \tilde \sigma_3, \tilde z, \tilde r \big)$ correspond to a valid
|
|
% signature for the signature scheme of section~\ref{scal-sig} for the committed value $V_\ID$: using the
|
|
% corresponding $\hat G_{2,\ID}, \hat G_{4,\ID}$ verify that
|
|
% \[ 1 \iseq e(\tilde z, \hat g_z) \cdot e(\tilde r, \hat g_r) \cdot e(\tilde \sigma_2, \hat G_{2, \ID} \cdot \hat g_3) \cdot e(\tilde \sigma_3, \hat G_{4,\ID} \cdot \hat g_5) \cdot e(\Omega, \hat g_6) \]
|
|
% If everything went correctly, return the corresponding $i$, otherwise return $\bot$.
|
|
|
|
% \item For each element in the records parsed as in~\eqref{gsig-trans}, checks that
|
|
% $\big(\tilde \sigma_1, \tilde \sigma_2, \tilde \sigma_3, \tilde z, \tilde r \big)$
|
|
% is a valid signature for the signature scheme of section~\ref{scal-sig} for $v_\ID$: using
|
|
% the corresponding $\hat g_{2,\ID}, \hat g_{4,\ID}$ verify that
|
|
% \[ 1 \iseq e(\tilde z, \hat g_z) \cdot e(\tilde r, \hat g_r) \cdot e(\tilde \sigma_2, \hat g_{2, \ID} \cdot \hat g_3) \cdot e(\tilde \sigma_3, \hat g_{4,\ID} \cdot \hat g_5) \cdot e(\Omega, \hat g_6) \]
|
|
% If one and only one of them corresponds, then return the corresponding $i$, otherwise return $\bot$.
|
|
\end{enumerate}
|
|
|
|
It is possible to spare one group element in the signature by eliminating the encryption $C_{\ID}$ of $v^\ID$ which is only used to open signatures in constant time.
|
|
Then, the opening algorithm has to check for each transcript if
|
|
$(\tilde \sigma_1, \tilde \sigma_2, \tilde \sigma_3, \tilde \pi)$ corresponds to the identifier $\ID$ embedded
|
|
in $(\sigma_1, \hat G_{2,\ID}, \hat G_{4, \ID})$ by testing the relation
|
|
\[ 1 \iseq e(\tilde \pi, \hat g_z) \cdot e(\tilde \sigma_1, \hat g_1) \cdot e(\tilde \sigma_2, \hat G_{2, \ID} \cdot \hat g_3) \cdot e(\tilde \sigma_3, \hat G_{4,\ID} \cdot \hat g_5) \cdot e(\Omega, \hat g_6). \]
|
|
This results in a modified opening algorithm which takes $O(N)$ in the worst-case. In applications where signature openings are infrequent, this is acceptable.
|
|
|
|
%---------------------------------------------------------------------
|
|
\subsection{Security}
|
|
|
|
The security of the above dynamic group signature scheme, namely full anonymity, security against misidentifications and security against framing attacks that are defined in \cref{sse:gs-sec-notions} are expressed in \cref{th:sgsig-anonymity}, \cref{th:sgsig-mis-identification} and~\cref{th:sgsig-non-frameability} respectively.
|
|
The security relies on the \SXDH assumption for anonymity and misidentification, and on the \SDL assumption for non-frameability.
|
|
|
|
\begin{theorem} \label{th:sgsig-anonymity}
|
|
If $\SXDH$ holds in $(\GG, \Gh, \GT)$, the scheme is CCA-anonymous in the random oracle model. %
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
We use a sequence of games where, for each $i$, $W_i$ is the event that the adversary $\adv$ wins in Game $i$.
|
|
\\
|
|
At the first transition, we need to rely on the security of the computational soundness of the \QANIZK argument of Section~\ref{sse:sigmasig-qa-nizk} which relies on the $\SXDH$ assumption, since $\tilde \sigma_2$ and
|
|
$\tilde \sigma_3$ appear un-encrypted in each group signature.
|
|
|
|
|
|
\begin{description}
|
|
\item[Game 0:] This is the real CCA-anonymity game.\\
|
|
In the challenge phase, the adversary outputs two valid membership certificates and membership secrets $(\crt_0^\star,\scr_0^\star),(\crt_1^\star,\scr_1^\star)$ and obtains a challenge signature which the challenger computes using $(\crt_d^\star,\scr_d^\star)$, where $d \sample \U(\bit)$. We define $W_0$ to be the event that
|
|
the adversary outputs $d'=d$.
|
|
|
|
\item[Game 1:] This game is as Game $0$, except that the challenger $\bdv$ aborts in the event,
|
|
which we call $F_1$, that $\adv$ chooses
|
|
membership certificates $\crt_0^\star, \crt_1^\star$ for which one of the underlying signatures
|
|
$ \bigl( \sigma_1^\star, \sigma_2^\star, \sigma_3^\star, \pi^\star \bigr) $
|
|
correctly verifies but $\log_g(\sigma_2^\star) \neq \log_h(\sigma_3^\star)$.
|
|
This implies that the vector
|
|
$(\sigma_1^\star, \sigma_2^{\star \ID}, \sigma_2^\star, \sigma_3^{\star \ID}, \sigma_3^\star, \Omega)$
|
|
is outside the row space of the matrix $\mathbf{M}$ (\ref{matrix-scal-sig}), so that $F_1$ would contradict
|
|
the soundness of the \QANIZK proof of \cite{KW15}
|
|
(via the same arguments as in Theorem 9 of \cite{LPY15} since the matrix can be witness-samplable here)
|
|
and thus the DDH assumption in $\Gh$. We have
|
|
$ [\Pr[W_1] - P[W_0] | \leq \advantage{\DDH}{\Gh}(\lambda).$
|
|
|
|
\item[Game 2:] We change the way to generate the challenge signature $ \Sigma^\star $. Instead of faithfully running the
|
|
Schnorr-like protocol, we use the HVZK-simulator to produce the proofs $s_\theta, s_\ID$ without knowing the witnesses
|
|
$\theta, \ID$. Namely, we pick $c,~ s_\theta,~ s_\ID \sample \U(\Zp)$ at random and set $ R_1 = g^{s_\theta} \cdot C_1^{-c}$, $R_2 = h^{s_\theta} \cdot C_2^{-c},$
|
|
$R_3 = v^{s_\ID} \cdot X_{\ID}^{s_\theta} \cdot C_{\ID}^{-c}$ as well as
|
|
%\begin{multline*}
|
|
%R_4 = \big( e(X_z, \hat g_z) \cdot e(X_\sigma, \hat g_1) \big)^{s_\theta} \\
|
|
%\cdot \big(e(\tilde \sigma_2, \hat g_2) \cdot e(\tilde \sigma_3, \hat g_4) \big)^{-s_\ID} \\
|
|
%\cdot \big(e(C_z, \hat g_z) \cdot e(C_\sigma, \hat g_1) \cdot e(\tilde \sigma_2, \hat g_3) \cdot e(\tilde \sigma_3, \hat g_5) \big)^{-c}.
|
|
%\end{multline*}
|
|
$R_4\in\GT$ as in~(\ref{gsig-verif-2}).
|
|
Then, we program the random oracle and assign the output $c$ to the hash value $H(M,C_{\mathsf{CS}},\tilde{\sigma}_2,\tilde{\sigma}_3, R_1, R_2, R_3,
|
|
R_4)$. In the unlikely event that this value was previously defined (which only happens with probability at most $1/p^3$), the challenger aborts.
|
|
Thus $|\Pr[W_2] - \Pr[W_1] | \leq 1/p^3$
|
|
|
|
\item[Game 3:] We modify again the generation of the challenge signature $ \Sigma^\star $. Namely, the challenger computes
|
|
$C_z, C_\sigma, C_\ID$ using $\mathcal{S}_\OA$ as follows
|
|
\begin{align*}
|
|
C_z &= \tilde \pi \cdot C_1^{x_z} \cdot C_2^{y_z}, \\
|
|
C_\sigma &= \tilde \sigma \cdot C_1^{x_\sigma} \cdot C_2^{y_\sigma}, &
|
|
C_\ID &= v^\ID \cdot C_1^{x_\ID} \cdot C_2^{y_\ID}.
|
|
\end{align*}
|
|
The distribution of $(C_z, C_\sigma, C_\ID)$ remains the same and we have $\Pr[W_3] = \Pr[W_2]$.
|
|
|
|
\item[Game 4:] Here, we modify the distribution of the challenge signature and replace $C_2 = h^\theta$ by $C_2 = h^{\theta + \theta'}$, for a randomly chosen $\theta'
|
|
\sample \U(\Zp)$. We prove in Lemma~\ref{le-gsig-3} that
|
|
$\left| \Pr[W_4] - \Pr[W_3] \right| \leq \advantage{\DDH}{\GG}(\lambda)$.
|
|
|
|
\item[Game 5:] We introduce one more change. Instead of sampling $h \in_R \Zp$,
|
|
the challenger chooses a random $\alpha \sample \U(\Zp)$ at the beginning of the game, sets $h = g^\alpha$ and retains the information $\alpha = \log_g(h)$ (note that
|
|
we are done with the DDH assumption and we can henceforth use $\alpha=\log_g(h)$). At each signature opening query,
|
|
the challenger returns $\perp$ on any signature
|
|
$\Sigma=(C_1, C_2, C_z, C_\sigma, C_\ID, \tilde \sigma_2, \tilde \sigma_3, c, s_\ID, s_\theta)$ such
|
|
that $C_2 \neq C_1^\alpha$. Game $5$ remains the same as Game $4$. until the event $E_5$ that $\adv$ queries the opening of a signature
|
|
that properly verifies although $C_2 \neq C_1^\alpha$. Lemma~\ref{le-gsig-4} states that $\Pr[E_5] \leq q_O \cdot q_H/ p$, where $q_O$ is the number of opening
|
|
queries and $q_H$ is the number of random oracle queries.
|
|
|
|
\end{description}
|
|
|
|
In Game $5$, $ \Sigma^\star $ perfectly hides $(\tilde{\pi},\tilde{\sigma}_1,v^{\mathsf{ID}})$. Indeed,
|
|
\begin{equation*}
|
|
\begin{gathered}
|
|
\begin{aligned}
|
|
C_1 &= g^\theta, \, & C_2 &= h^{\theta + \theta'}, \,
|
|
& C_z &= (\tilde z \cdot h^{\theta' \cdot y_z} ) \cdot X_z^\theta ,
|
|
\end{aligned}\\
|
|
\begin{aligned}
|
|
C_\sigma &= (\tilde \sigma_1 \cdot h^{\theta' \cdot y_\sigma} ) \cdot X_\sigma^\theta,
|
|
& \; C_\ID &= ( v^\ID \cdot h^{\theta' \cdot y_{\ID}} ) \cdot X_\ID^\theta
|
|
\end{aligned}
|
|
\end{gathered}
|
|
\end{equation*}
|
|
and $(y_{\sigma},y_z,y_{\mathsf{ID}}) \in \Zp^3$ are completely independent of $\adv$'s view.
|
|
The only way for $\adv$ to infer information about $(y_{\sigma},y_z,y_{\mathsf{ID}}) $ is to make
|
|
opening queries on signatures such that $C_2 \neq C_1^\alpha$. However, all such signatures are declared invalid in Game $5$.
|
|
It comes that $\Pr[W_5]=1/2$. \medskip
|
|
\\
|
|
Finally, $\adv$'s advantage $\bigl| \Pr[W_0] - 1/2 \bigr|$ is bounded by
|
|
\[
|
|
\advantage{\DDH}{\GG}(\lambda) + \advantage{\DDH}{\Gh}(\lambda)+ \frac{q_O \cdot q_H}{p} + \frac{1}{p^3},
|
|
\]
|
|
which concludes the proof.
|
|
%
|
|
\end{proof}
|
|
|
|
\begin{comment}
|
|
|
|
\begin{lemma} \label{le-gsig-1}
|
|
In Game $1$ we have $\Pr[F_1] \leq \Advt{\Gh}{\mathrm{DDH}}{\lambda}$.
|
|
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Let us assume that $F_1$ occurs with non-negligible probability, we build a LHSPS forger $\bdv$ that receives as input a
|
|
public key $\pk_{hsps}$.
|
|
|
|
$\bdv$ faithfully generates the signature public key by faithfully running steps $1$, $2$, $3$ of the signature scheme
|
|
of Section~\ref{scal-sig} and then calls for the signing oracle to obtain homomorphic signatures $\{ (z_j, r_j) \}_{j=1}^3$
|
|
on the rows of the matrix $\mathbf{M} \in \GG^{3 \times 6}$. It then conducts the remaining steps faithfully to obtain a
|
|
group public key $\gspk$. Since $\bdv$ knows $\mathcal{S}_\OA$, it an perfectly simulate the opening oracle. If
|
|
$F_1$ occurs -- which it does by hypothesis --, one of the two membership certificate $\crt_d^\star$ of the challenge
|
|
phase must contain a signature $\sigma^\star$ such that $\log_g(\sigma_2^\star) \neq \log_h(\sigma^\star_3)$. At this
|
|
point, $\bdv$ can win the game against its challenger by outputting the vector $(\sigma_1^\star, \sigma^{\star \ID}_2,
|
|
\sigma_2^\star, \sigma_3^{\star \ID}, \sigma_3^\star, \Omega)$, and the corresponding signature $(z^\star, r^\star)$.
|
|
Since the LHSPS scheme is secure under the DDH assumption in $\hat G$, we therefore obtains the claimed inequality.
|
|
\end{proof}
|
|
|
|
\end{comment}
|
|
|
|
\begin{lemma} \label{le-gsig-3}
|
|
In Game $4$, the adversary $\adv$ wins the anonymity game with negligibly different probabilities than in Game $3$ if
|
|
the DDH assumption holds in $\GG$.
|
|
\end{lemma}
|
|
%
|
|
\begin{proof}
|
|
Let us assume that an adversary $\adv$ wins with noticeably different probabilities in Game $4$ and Game $3$. We
|
|
then construct a DDH distinguisher $\bdv$ from $\adv$.
|
|
|
|
Our reduction $\bdv$ takes as input a DDH instance $(g^a, g^b, \eta)$, where $\eta = g^{a(b+c)}$ and has to
|
|
decide with non-negligible probability $\varepsilon$ whether $c = 0$ or $c \in_R \Zp$. To achieve this, $\bdv$ sets $h = g^a$ and computes the challenge signature as $ C_1 = g^b$ and $ C_2 = \eta$.
|
|
The rest of the game continues like in Game $3$ (which is also the same as in Game $2$).
|
|
If $\adv$ wins and correctly guesses $d'=d \in \bit$, $\bdv$ outputs $1$, meaning that $C_2 = h^{b } = g^{ab}$. Otherwise, $\bdv$ returns $0$ meaning that $(g^a, g^b, \eta) \in_R \GG^3$.
|
|
\\
|
|
It is easy to see that $\bdv$'s advantage as a DDH distinguisher is $\varepsilon$ if $|\Pr[W_4]-\Pr[W_3]|=\varepsilon$.
|
|
%
|
|
\end{proof}
|
|
|
|
\begin{lemma} \label{le-gsig-4}
|
|
In Game $5$, we have $\Pr[E_5] \leq q_O \cdot q_H/ p$.
|
|
\end{lemma}
|
|
%
|
|
\begin{proof}
|
|
This proof uses idea similar to the security proof of the Katz-Wang~\cite{KW03} signature scheme.
|
|
In Game $5$, event $E_5$ happens if $\log_g(C_1) \neq \log_h(C_2)$ and the verification
|
|
equations~\eqref{gsig-verif-1} and \eqref{gsig-verif-2} holds.
|
|
In particular, we have $ R_1 = g^{s_\theta} \cdot C_1^{-c}$ and $R_2 = h^{s_\theta} \cdot C_2^{-c}$,
|
|
%\begin{align*}
|
|
% R_1 &= g^{s_\theta} \cdot C_1^{-c}, &
|
|
% R_2 &= h^{s_\theta} \cdot C_2^{-c},
|
|
%\end{align*}
|
|
which can be interpreted as a linear system with unknowns $(c,s_\theta) \in \Zp^2$
|
|
\begin{equation} \label{gsig-proof-sys}
|
|
\begin{cases}
|
|
\log_g(R_1) = s_\theta - \log_g(C_1) \cdot c &\bmod p, \\
|
|
\log_h(R_2) = s_\theta - \log_h(C_2) \cdot c &\bmod p.
|
|
\end{cases}
|
|
\end{equation}
|
|
We can assume w.l.o.g. that each opening query is preceded by the corresponding random oracle query (otherwise, the reduction can simply make the hash query for itself).
|
|
The input of each hash query contains a pair $(R_1, R_2)$ determining the non-homogeneous terms of the linear
|
|
system~\eqref{gsig-proof-sys}. Since $\log_g(C_1) \neq \log_h(C_2)$, the system is full-rank, so that for each $(R_1,R_2)$, there is exactly
|
|
one pair $(c, s_\theta) \in \Zp^2$ that satisfies (\ref{gsig-proof-sys}). The probability that, in response to a random oracle query, the reduction returns
|
|
the value of $c$ which is uniquely determined by (\ref{gsig-proof-sys}) is at most $1/p$.
|
|
For all hash queries, the probability that one of them be answered with the uniquely determined $c \in \ZZ_q$ is \emph{at most}
|
|
$q_H/p$. A union bound over all opening queries implies that the probability that the event $E_4$ happens is smaller than
|
|
$\Pr[E_4] \leq q_O \cdot q_H/p.$
|
|
%
|
|
\end{proof}
|
|
|
|
|
|
The proof of security against misidentification attacks requires the reduction to rewind a
|
|
the proof of knowledge of $\ID$ at each execution of the join protocol with the adversary attempting to escape traceability.
|
|
For this
|
|
reason, we need to assume that users join the system sequentially, rather than concurrently.
|
|
However, this problem can be solved as in \cite{DP06} by having the user send an extractable commitment to $\ID$ and non-interactively prove (via the Fiat-Shamir heuristic) that he did so correctly.
|
|
This allows the reduction to
|
|
extract $\ID$ without rewinding the user at each execution of $\mathsf{Join}$. Then, the proof of security against framing attacks must be modified by having the reduction
|
|
simulate the proof of knowledge of $\ID$ (by programming a random oracle) and rely on the hiding property of the extractable commitment.
|
|
|
|
|
|
\begin{theorem} \label{th:sgsig-mis-identification}
|
|
In the ROM, the scheme is secure against
|
|
misidentification attacks under the $\SXDH$ assumption in $(\GG,\Gh)$.
|
|
\end{theorem}
|
|
%
|
|
\begin{proof}
|
|
The proof uses the forking technique \cite{PS00} % {\em rewinding extractor} method
|
|
%from Bernhard~{\em et~al.}~\cite{BFW15},
|
|
which consists in implicitly rewinding the zero-knowledge proof by running the adversary twice and changing the outputs of the random oracle after the hash query that involves
|
|
the forgery message. The Forking Lemma~\cite{PS00} -- more precisely, its generalization given by Bellare and Neven~\cite{BN06} -- ensures that, after two runs of the adversary,
|
|
the reduction can extract witnesses of which knowledge is demonstrated by the signature of knowledge.
|
|
%After the extraction, the reduction can then call the corresponding oracles to simulate the game without having
|
|
%information it does not hold.
|
|
|
|
Let us assume an attacker $\adv$ against the misidentification game that wins with non-negligible
|
|
probability $\varepsilon$. We build an adversary $\bdv$ against the chosen-message security of the signature
|
|
scheme of section~\ref{scal-sig}. \medskip
|
|
|
|
\textit{Keygen.} At the key generation, $\bdv$ invokes its own challenger for the chosen-message security game to obtain the
|
|
public key $\pk_s$ for the signature scheme. $\pk_s$ is embedded in the group public key $\gspk$. Except for $\mathcal{S}_\GM$, all keys
|
|
are generated as in the normal
|
|
\textsf{Keygen} algorithm. \medskip
|
|
|
|
\textit{Join.} To answer joining queries without knowing $\sk_s$, $\bdv$ uses the knowledge extractor of the proof
|
|
of knowledge of $\ID = \log_v(V_\ID)$ to extract the identity to be signed. Namely, on a
|
|
\textsf{Join} query, the reduction $\bdv$ rewinds the adversary $\adv$ in order to extract the witness $\ID=\log_v(V_{\ID})$ of which $\adv$ demonstrates knowledge at step 3 of the
|
|
join protocol. Having extracted $\ID \in \Zp$, $\bdv$ invokes its own
|
|
signing oracle on the message $\ID$ to obtain $(\sigma_1, \sigma_2, \sigma_3, z, r)$. Then, $\bdv$ returns $\crt_i=(i,V_{\ID},\sigma_1,\sigma_2,\sigma_3,z,r)$ as in a normal execution
|
|
of the join protocol.
|
|
\medskip
|
|
|
|
At some point, the attacker $\adv$ produces a valid forgery
|
|
\[ (M^\star, \Sigma^\star = (C_1^\star, C_2^\star, C_z^\star, C_\sigma^\star, C_\ID^\star,
|
|
\tilde \sigma_2^\star, \tilde \sigma_3^\star, c^\star, s_\ID^\star, s_\theta^\star))\] for
|
|
which the opening algorithm does not reveal a properly registered identity. With all but negligible probability, $\adv$ must have queried the random oracle value
|
|
\[ H(M^\star, C_{\mathsf{CS}}^\star,\tilde{\sigma}_2^\star,\tilde{\sigma}_3^\star, R_1^\star, R_2^\star, R_3^\star, R_4^\star)\]
|
|
which would have been unpredictable otherwise.
|
|
|
|
Thus, $\bdv$ replays the adversary $\adv$ with the \emph{same} input and random tape as in the first run. In the second run, the random oracle is also the same until the hash query
|
|
\[ H(M^\star, C_{\mathsf{CS}}^\star,\tilde{\sigma}_2^\star,\tilde{\sigma}_3^\star, R_1^\star, R_2^\star, R_3^\star, R_4^\star).\]
|
|
At this point, the forking occurs and $\bdv$ outputs fresh random oracle values. By the Forking Lemma of~\cite{BN06}, $\bdv$ obtains
|
|
two suitably related forgeries with non-negligible probability $\varepsilon \cdot (\varepsilon / q_H -1/p) $. Namely, $\bdv$ will obtain two matching transcripts
|
|
$(C_{\mathsf{CS}}^\star, \tilde \sigma_2^\star, \tilde \sigma_3^\star, c^\star, s_\ID^\star, s_\theta^\star)$,
|
|
$(C_{\mathsf{CS}}^\star, \tilde \sigma_2^\star, \tilde \sigma_3^\star, c^\dag, s_\ID^\dag, s_\theta^\dag )$
|
|
of the $\Sigma$-protocol for the commitment message
|
|
\[ \mathsf{com}=(C_{\mathsf{CS}}^\star,\tilde{\sigma}_2^\star,\tilde{\sigma}_3^\star, R_1^\star, R_2^\star, R_3^\star, R_4^\star).\]
|
|
From the responses
|
|
$s_\ID^\star$ and
|
|
$s_\ID^\dag$ (that necessarily involve the same identifier $\ID^\star$ which is uniquely determined by $C_{\mathsf{CS}}^\star = (C_1^\star, C_2^\star, C_z^\star, C_\sigma^\star, C_\ID^\star)$), $\bdv$ runs the knowledge extractor of to obtain
|
|
$\ID^\star \in \Zp$. Namely, given $(c^\star ,c'^\star , s_\theta^\star , s_\theta'^\star ,s_\ID^\star , s_\ID'^\star ) \in \Zp^6$ with
|
|
\begin{align*}
|
|
c^\star &\neq c^\dag, &
|
|
s_\theta^\star &\neq s_\theta^\dag &
|
|
s_\ID^\star &\neq s_\ID^\dag
|
|
\end{align*}
|
|
which verifies the relation~\eqref{gsig-verif-1} , \eqref{gsig-verif-2} for the same commitment $(R_1^\star,
|
|
R_2^\star, R_3^\star, R_4^\star) \in \GG^4$, one can compute the secrets $\ID^\star = \frac{s_\ID^\dag - s_\ID^\star}{c^\star-c^\dag} \bmod p$ and $\theta^\star = \frac{s_\theta^\dag - s_\theta^\star}{c^\star - c^\dag} \bmod p$.
|
|
%\begin{align*}
|
|
% \ID^\star &= \frac{s_\ID^\dag - s_\ID^\star}{c^\star-c^\dag} \bmod p, &
|
|
% \theta^\star &= \frac{s_\theta^\dag - s_\theta^\star}{c^\star - c^\dag} \bmod p.
|
|
%\end{align*}
|
|
\medskip
|
|
\\
|
|
Finally $\bdv$ uses $\mathcal{S}_\OA$ to extract $\tilde \sigma_1^\star, \tilde r^\star, \tilde z^\star$ and outputs
|
|
$\bigl(\ID^\star, \sigma^\star = (\tilde \sigma_1^\star,\tilde \sigma^\star_2,\tilde \sigma_3^\star, \tilde r^\star, \tilde z^\star)\bigr)$ as a forgery
|
|
for the signature scheme of Section~\ref{scal-sig}.
|
|
%
|
|
\end{proof}
|
|
|
|
|
|
\begin{theorem} %[Non-frameability]
|
|
\label{th:sgsig-non-frameability}
|
|
In the ROM, the scheme is secure against framing attacks under the SDL assumption.
|
|
\end{theorem}
|
|
|
|
\begin{proof} Let us assume that a PPT adversary $\adv$ can create, with advantage $\varepsilon$, a forgery $(M^\star,\sigma^\star)$ that opens to some honest user $i\in U^b$ who did not sign $M^\star$. We give a reduction $\bdv$ that uses $\adv$ to break SDL.
|
|
|
|
Algorithm $\bdv$ takes as input an SDL instance $(g,\hat{g},g^a,\hat{g}^a)$ and uses its interaction with the adversary $\adv$ to compute $a \in \Zp$.
|
|
To generate the group public key $\gspk$, $\bdv$ runs all the steps of the real setup algorithm $\textsf{Keygen}$ except step 1.
|
|
At step 1, $\bdv$ defines the generators $g,\hat{g}$ in $\pk_s$ to be those of its input and computes $h=g^{\alpha_h}$, $v=g^{\alpha_v}$, $w=g^{\alpha_w}$, $\hat{g}_z=\hat{g}^{\alpha_z}$ for randomly chosen scalars $\alpha_h,\alpha_v,\alpha_w,\alpha_z \sample \U(\Zp)$.
|
|
In order to compute $\{z_j\}_{j=1}^3$ of $\mathsf{crs}$ contained in $\pk_s$, $\bdv$ chooses $\mathsf{tk}=\{\chi_j\}_{j=1}^6$ of step 4 of the key generation algorithm of the signature scheme of Section \ref{scal-sig} with $\ell=1$. (Note that when $\ell=1$, $n=6$ and that $\{z_j\}_{j=1}^3$ are \QANIZK argument for the vectors $(g,1,1,1,1,h)$, $(v,g,1,h,1,1)$ and $(w,1,g,1,h,1)$. Moreover $\{\hat{g}_i=\hat{g}_z^{\chi_i}\}_{i=1}^6$ are the verifying key.)
|
|
As a result of this setup phase, $\bdv$ knows $\mathcal{S}_{\GM}=\sk_s=\omega$, $\mathcal{S}_{\OA}=\bigl(x_z, y_z, x_\sigma, y_\sigma, x_\ID, y_\ID \bigr)$ and even $\mathsf{tk}$. The adversary $\adv$ is run on input of the group public key $\gspk\coloneqq (\pk_s,(X_z,X_\sigma,X_{\ID}),H)$, which has the same distribution as in the real attack game. \medskip
|
|
\\
|
|
Should $\adv$ decide to corrupt the group manager or the opening authority during the game, $\bdv$ is able to reveal $\mathcal{S}_{\GM}=\sk_s$ and $\mathcal{S}_{\OA}$ when requested.
|
|
%At the outset of the game, $\bdv$ picks a random $j^\star \sample \{1,\ldots,q_b\}$ and interacts with $\adv$ as follows.
|
|
In addition, $\bdv$ must be able to answer the following queries.
|
|
\begin{itemize}
|
|
% \item[-] $Q_{\mathsf{keyGM}}$-queries: if $\adv$ decides to corrupt the group manager, $\bdv$ surrenders $\mathcal{S}_{\GM}=\omega=\sk_s$.
|
|
\item[-] $Q_{\bjoin}$-queries: At any time $\adv$ can act as a corrupted group manager and introduce a new honest user $i$ in the group by invoking the $Q_{\bjoin}$ oracle. Then, $\bdv$ runs $\mathsf{J}_{\mathsf{user}}$ on behalf of the honest user in an execution of $\mathsf{Join}$. %The actions taken by $\bdv$ are dictated by the index $j \in \{1,\ldots,q_b\}$ of the $Q_{\bjoin}$-query. \\
|
|
%\begin{itemize}
|
|
%\item[-] If $j \neq j^\star$, $\bdv$ follows the exact specification of $\mathsf{J}_{\mathsf{user}}$.
|
|
%\item[-] If $j=j^\star$,...
|
|
%\end{itemize}
|
|
At step 1 of $\mathsf{Join}$, $\bdv$ picks a random $\delta_i \sample \U(\Zp)$ and uses $\mathsf{tk}$ to compute the tuple
|
|
$(V_i,Z_i,\hat{G}_{2,i},\hat{G}_{4,i})$, for an unknown $\scr_{i}=\ID_i=a\cdot\delta_i \in \Zp$, that
|
|
$\mathsf{J}_{\mathsf{GM}}$ expects at step 1 of the join protocol. Namely, $\bdv$ computes the vector
|
|
$ \vec{v}_i= (V_i,G_i,1,H_i,1,1)=(v,g,1,h,1,1)^{\ID_i}$ as
|
|
\[
|
|
V_i =(g^a)^{\alpha_v\cdot\delta_i}, \quad G_i = (g^a)^{\delta_i}, \quad H_i =(g^a)^{\alpha_h\cdot\delta_i},
|
|
\]
|
|
and then computes $Z_i$ as a simulated \QANIZK proof for $\vec{v}_i \in \GG^6$ using $\mathsf{tk}$.
|
|
A straightforward calculation
|
|
shows that $Z_i=z_2^{\ID_i}$ since the \QANIZK argument of Section \ref{sse:sigmasig-qa-nizk} has a deterministic proving algorithm, so that
|
|
$(V_i,Z_i,\hat{G}_{2,i},\hat{G}_{4,i})$ successfully passes the test of step 2.
|
|
As for the last two components, for each $j\in \{2,4\}$, $\bdv$ computes
|
|
\begin{eqnarray*}
|
|
\quad\hat{G}_{j,i} \coloneqq (\hat{g}^a)^{\delta_i(\alpha_z\chi_j+\alpha_r\gamma_j)}
|
|
= (\hat{g}_z^{\chi_j}\hat{g}_r^{\gamma_j})^{\ID_i} = \hat{g}_j^{\ID_i},
|
|
\end{eqnarray*}
|
|
%where $g^a$ is a component of the discrete logarithm problem it is trying to solve.
|
|
At step 3 of $\mathsf{Join}$, $\bdv$ simulates the interactive proof of knowledge of $\ID_i=\log_{v}(V_i)$ using the simulator.
|
|
In the rest of the protocol, $\bdv$ proceeds like the actual run and obtains $ \crt_{i}=(i, V_i, \sigma_1, \sigma_2, \sigma_3, \pi)$.
|
|
Finally, $\bdv$ stores $(\crt_{i},Z_i,\delta_i,\hat{G}_{2,i},\hat{G}_{4,i})$.
|
|
% \item[-] $Q_{\mathsf{pub}}$-queries: These can be answered as in the real game, by having the simulator return
|
|
%$\gspk$.
|
|
\item[-] $Q_{\mathsf{sig}}$-queries: When $\adv$ requests user $i \in U^b$ to sign a message $M$, $\bdv$ is able to use
|
|
the membership certificate $ \crt_{i}=(i, V_i, \sigma_1, \sigma_2, \sigma_3, \pi)$ to compute the ciphertext $C_{\mathsf{CS}}$ at steps 1-2 of the signing algorithm.
|
|
While $\bdv$ does not know the witness $\ID_i=a\cdot\delta_i\in\Zp$ to generate a proof at step 3, $\bdv$ is able to simulate the
|
|
non-interactive proof $(c, s_\ID, s_\theta)$, for a randomly chosen challenge $c \sample \U(\Zp)$ by programming the random oracle.
|
|
More precisely, $\bdv$ re-randomizes the certificate $\crt_i$ by picking $r \sample \U(\Zp)$ and computing
|
|
\begin{align*}
|
|
\tilde\sigma_1 & = \sigma_1 \cdot (V_i\cdot w)^r & \tilde \sigma_2 & = \sigma_2 \cdot g^r, \\
|
|
\tilde \pi & = \pi \cdot (Z_i \cdot z_3)^r, & \tilde \sigma_3 & = \sigma_3 \cdot h^r.
|
|
\end{align*}
|
|
Then $\bdv$ encrypts $\tilde \pi$, $\tilde \sigma_1$ and $V_i$ as in the real
|
|
signing algorithm to get the encryption ${C}_{\mathsf{CS}}=(C_1, C_2, C_z, C_\sigma, C_\ID)$. Then, $\bdv$
|
|
chooses $c, s_\ID, s_\theta\in\Zp$ and computes $R_1,R_2,R_3,R_4$ as in
|
|
(\ref{gsig-verif-1}) and (\ref{gsig-verif-2}) of $\mathsf{Verify}$. Finally, $\bdv$
|
|
programs $H$ to return $c$ on inputs $(M, C_{\mathsf{CS}},\tilde \sigma_2, \tilde \sigma_3, R_1, R_2, R_3, R_4)$. In the event that $H$ is already defined at that point,
|
|
$\bdv$ aborts.
|
|
The probability to fail at one signing query is $\leq q_s/p^3$, where
|
|
$q_s$ is the number of signing queries.
|
|
\end{itemize}
|
|
|
|
When $\adv$ halts, it presumably frames some honest user ${i^\star} \in U^b$ by outputting a signature
|
|
\begin{align*}
|
|
\Sigma^\star = (C_1^\star, C_2^\star, C_z^\star, C_\sigma^\star, C_\ID^\star, \tilde \sigma_2^\star, \tilde \sigma_3^\star, c^\star, s_\ID^\star, s_\theta^\star) , \quad
|
|
\end{align*}
|
|
for some message $M^\star$, that opens to ${i^\star} \in U^b$ although user $i^\star$ did not sign $M^\star$. With high probability, $\adv$ must have queried the hash value
|
|
$H(M^\star, C_{\mathsf{CS}}^\star, \tilde \sigma_2^\star,\tilde \sigma_3^\star,R_1^\star, R_2^\star, R_3^\star, R_4^\star)$, which would be unpredictable otherwise.
|
|
Hence, $\bdv$ can run $\adv$ a second time with the same input and random tape.
|
|
|
|
At the moment when $\adv$ queries $H(M^\star, C_{\mathsf{CS}}^\star, \tilde \sigma_2^\star,\tilde \sigma_3^\star,R_1^\star, R_2^\star, R_3^\star, R_4^\star)$ in the second run, $\bdv$ starts responding with different random oracle values which depart from those of the initial run.
|
|
The Forking Lemma of \cite{BN06} ensures that, with non-negligible probability the second run will result in a forgery
|
|
\[\Sigma^\dag = (C_1^\star, C_2^\star, C_z^\star, C_\sigma^\star, C_\ID^\star, \tilde \sigma_2^\dag, \tilde \sigma_3^\dag, c^\dag, s_\ID^\dag, s_\theta^\dag)\] on
|
|
the same message $M^\star$,
|
|
with distinct challenges
|
|
$c^\dag\neq c^\star$. From the two responses $(s_\ID^\star, s_\theta^\star)$, $(s_\ID^\dagger, s_\theta^\dagger)$, $\bdv$ can extract witnesses
|
|
$(\theta^\star,\ID^\star)$ satisfying ${C}_\ID^\star=v^{\ID^\star}X_\ID^{\theta^\star}$ and
|
|
which identifies $V_i^\star=v^{\ID^\star}$. At this stage, $\bdv$ can compute and output the sought-after SDL solution
|
|
$a\coloneqq \ID^\star/\delta_i$ in $\Zp$.
|
|
\\
|
|
This observation tells us that, if $\adv$ has advantage $\varepsilon$ as a framing adversary making $q_H$ random oracle queries, then $\bdv$ implies an algorithm solving the SDL problem with probability $\varepsilon (\varepsilon / q_H -1/p) $.
|
|
|
|
\end{proof}
|
|
|
|
We stress that the proofs can be easily adapted to the case where the opening algorithm has linear complexity in the number of users.
|
|
|
|
%------------------------------------------------------------------------
|
|
|
|
\subsection{Comparison with Existing Schemes}
|
|
|
|
\begin{table*}[h]
|
|
\small
|
|
\centering
|
|
\begin{tabular}{|c|c|c|c|c|c|c|}
|
|
\hline
|
|
Name & \multicolumn{3}{c|}{Signature length} & Assumptions & Group Type & Anonymity \\ \cline{2-4}
|
|
& $\GG$ & $\Zp$ & bits & & &
|
|
\\ \hline
|
|
Ours & $7$ & $3$ & $2560$ bits& \textsf{SXDH} + \textsf{SDL} & Dynamic & CCA \\ \hline
|
|
Boneh-Boyen-Shacham & $3$ & $6$ & $2304$ bits & $q$-\textsf{SDH} + \textsf{DLIN} & Static & CPA \\ \hline
|
|
|
|
Delerabl\'ee-Pointcheval & $4$ & $5$ & $2304$ bits & $q$-\textsf{SDH} + \textsf{XDH} & Dynamic & CCA \\ \hline
|
|
Bichsel {\em et al.} & $3$ & $2$ &$1280$ bits & \textsf{LRSW} + \textsf{SDL} & Dynamic & CCA- \\ \hline
|
|
Pointcheval-Sanders & $2$ & $2$ & $1024$ bits & \textsf{LRSW}-like & Dynamic & CCA- \\ \hline
|
|
|
|
\end{tabular}
|
|
\caption{Comparison between different group signature schemes}
|
|
\label{sig-comp}
|
|
\end{table*}
|
|
|
|
Table~\ref{sig-comp} compares our scheme with previous practical group signatures based on pairing-related assumptions.
|
|
Since we focus on practical schemes, we only consider those in the random oracle model.
|
|
To make the comparison possible, we use $256$-bit group orders, so that elements of $\GG$ and $\Zp$ are encoded using
|
|
$256$ bits each.
|
|
|
|
The scheme of Boneh, Boyen and Shacham~\cite{BBS04} is the first scheme providing short signatures: each signature is
|
|
comprised of $3$ group elements and $6$ elements of $\Zp$. However, this scheme is designed for static groups only and
|
|
relies on the Strong Diffie-Hellmann assumption, which is a non-standard $q$-type assumption, and its anonymity is only
|
|
proved in the CPA sense.
|
|
|
|
Delerablée and Pointcheval~\cite{DP06} presented a scheme designed for a dynamically growing group and which is also
|
|
fully (i.e., CCA) anonymous. The security of their scheme is based on the eXternal Diffie-Hellman assumption (XDH),
|
|
which we also use here, and the $q$-SDH assumption. In \cite{DP06}, each signature consists of $4$ group elements and $5$
|
|
scalars in $\Zp$, which leads to the same signature size as previously. They also proposed a variant to get rid of the
|
|
XDH assumption at the cost of $2$ more group elements and one more scalar, but they still rely on the $q$-SDH
|
|
assumption.
|
|
|
|
Bichsel~{\em et al.} \cite{BCN+10} proposed a very short group signature for dynamic groups, where each
|
|
signature consists of $3$ group elements and $2$ elements in $\Zp$.
|
|
The downsides are their use the LRSW assumption~\cite{LRSW99}, which is a very {\em ad-hoc} interactive assumption, and
|
|
their security notion is not fully-anonymous, but is an hybrid security with selfless-anonymity, which is marked ``CCA-'' in Table~\ref{sig-comp}.
|
|
%they don't provide full-CCA anonymity but an hybrid security with selfless anonymity, which is marked ``CCA*'' in Table~\ref{sig-comp}.
|
|
Another caveat is that, unlike the two previous systems, the opening complexity of their scheme is linear in the number of group members.
|
|
|
|
|
|
In 2015, Pointcheval and Sanders~\cite{PS16} gave another instantiation of~\cite{BCN+10} based on a variant of the LRSW
|
|
assumption in the asymmetric setting (meaning using only Type III pairings), which provides even shorter signatures than
|
|
\cite{BCN+10} with the same downsides.
|
|
Their scheme provides signatures composed of only $2$ group elements in $\GG$ and $2$ scalars in~$\Zp$.
|
|
|
|
|
|
Our main contribution compared to these schemes is to provide size-comparable signatures --\,we recall that our scheme is
|
|
composed of $7$ group elements and $3$ scalars in $\Zp$\,-- while relying on standard, constant-size assumptions.
|
|
Moreover, we can notice that we can save one element in $\GG$ at the expense of a linear-time opening algorithm in the
|
|
number $\Ngs$ of group users (like \cite{BCN+10}).
|
|
|
|
%On the other hand, the comparison of computational cost is not straightforward, as it is not clear if the computation of $e(x^\alpha, \hat x) \cdot e(y^\beta, \hat y)$ is easier than the computation
|
|
|
|
\subsection{Experimental Results}
|
|
\addcontentsline{tof}{subsection}{\protect\numberline{\thesubsection} Résultats expérimentaux}
|
|
|
|
\begin{table}
|
|
\centering
|
|
\begin{tabular}{|c|r|r|}
|
|
\hline
|
|
\textbf{Algorithm/Protocol} & \textbf{Our scheme} & \textbf{Standard deviation}\\
|
|
\hline \hline
|
|
\textsf{Keygen} & 9.70 ms & 2.18 ms \\ \hline
|
|
\textsf{Join} & 23.16 ms & 0.11 ms \\ \hline
|
|
\textsf{Sign} & 15.70 ms & 0.04 ms \\ \hline
|
|
\textsf{Verify} & 26.91 ms & 0.04 ms \\ \hline
|
|
\end{tabular}
|
|
\caption{Experimental results for the Pairing-Base group signature scheme}
|
|
\label{ta:sigmasig-figures}
|
|
\end{table}
|
|
|
|
An implementation of the aforementioned group signature scheme has been made in \texttt{C} using the \textit{Relic toolkit} for pairing-based cryptography~\cite{AG} and is available at the following \textsc{URL}:~\url{https://gforge.inria.fr/projects/sigmasig-c/}.
|
|
|
|
The relic toolkit provides an implementation for pairing computations, hash functions (SHA-256 in this case) and benchmarking macros.
|
|
The benchmarking was made on a single-core of an \textit{Intel\textregistered{} Core\texttrademark{} i5-7500 CPU @ 3.40GHz} (Kaby Lake architecture) with 6MB of cache.
|
|
To implement pairings, the relic library implements the Barreto-Naehrig~\cite{BN06} curve over a 256 bits curve.
|
|
As explained previously, since recent advances in pairing-friendly elliptic curve cryptanalysis, there is no more curve that shows the best timing results in every aspect.
|
|
Figures are available in Table~\ref{ta:sigmasig-figures}.
|
|
|
|
%Unfortunately, we didn't have time to implement other protocols from~\cref{sig-comp} in order to present fair comparison.
|
|
%Moreover, those schemes hardly show implementation results, and providing timing comparisons seems compromised.
|