261 lines
19 KiB
TeX
261 lines
19 KiB
TeX
% \section{Stern-like Proofs}
|
|
% \addcontentsline{tof}{section}{\protect\numberline{\thesection} Preuves à la Stern}
|
|
% \label{sse:stern}
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
Stern's protocol has originally been introduced in the context of code-base cryptography~\cite{Ste96}.
|
|
\index{Syndrome Decoding Problem}
|
|
Initially, it was designed for Syndrome Decoding Problem (\SDP): given a matrix $\mathbf{M} \in \FF_2^{n \times m}$ and a syndrome $\mathbf{v} \in \FF_2^n$, the goal is to find a binary vector $\mathbf{w} \in \FF_2^m$ with fixed hamming weight $w$ such that $\mathbf{M} \cdot \mathbf{w} = \mathbf{v} \bmod 2$.
|
|
|
|
This problem bears similarities with the $\ISIS$ problem defined in \cref{de:sis} where the constraint on the norm of $\mathbf{x}$ is replaced by a constraint on Hamming weight, and operations are in $\FF_2$ instead of $\Zq$.
|
|
|
|
After the first work of Kawachi, Tanaka and Xagawa~\cite{KTX08} that extended Stern's proofs to statements $\bmod q$, the results of Ling, Nguyen, Stehlé and Wang~\cite{LNSW13} enable the use of Stern's protocol to prove general $\SIS$ or $\LWE$ statements (meaning proving knowledge of a solution to these problems).
|
|
These advances in the expressiveness of Stern-like protocols has been used to further improve them and therefore enable privacy-based primitives for which no constructions previously existed in the post-quantum world, such as dynamic group signatures~\cite{LLM+16}, group encryption~\cite{LLM+16a}, electronic cash~\cite{LLNW17}, etc.
|
|
|
|
Unlike Schnorr-like proofs that we described in the previous section, Stern-like proofs are mainly combinatorial and rely on the fact that every permutation on a binary vector $\mathbf{w} \in \bit^m_{}$ leaves its Hamming weight $w$ invariant. As a consequence, for $\pi \in \permutations_m$, $\mathbf{w}$ satisfies these conditions if and only if $\pi(\mathbf{x})$ also does.
|
|
Therefore, the randomness of $\pi$ is used to verify these two constraints (being binary and having fixed Hamming weight) in a zero-knowledge fashion.
|
|
We can notice that this can be extended to vectors $\mathbf{w} \in \nbit^m$ having fixed numbers of $-1$ and $1$.
|
|
This property allowed~\cite{LNSW13} to propose the generalization of this protocol to any $\ISIS_{n,m,q,\beta}$ statements.
|
|
In \cref{sse:stern-abstraction}, we describes these permutations while abstracting the set of ZK-provable statements as the set $\mathsf{VALID}$ that satisfies conditions~\eqref{eq:zk-equivalence}.
|
|
|
|
It is worth noticing that this argument on knowledge does not strictly follow the definition of a $\Sigma$-protocol in~\cref{de:sigma-protocol}. The challenge space is ternary as described in \cref{sse:stern-abstraction}, hence the protocol verifies $3$-special soundness.
|
|
Thus, standard theorems on $\Sigma$-protocols have to be adapted in this setting.
|
|
|
|
In this Section, we describe in a high-level manner the behavior of Stern-like protocols before detailing it.
|
|
|
|
|
|
\subsection{The Decomposition-Extension Framework} \label{sse:stern-dec-ext}
|
|
\addcontentsline{tof}{subsection}{\protect\numberline{\thesubsection} Méthode de décomposition-extension}
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%
|
|
%%%% Recap Table %%%%
|
|
%%%%%%%%%%%%%%%%%%%%%
|
|
\begin{figure}[h]
|
|
\begin{itemize}
|
|
\item $\mathsf{B}^{2}_{\mathfrak m}$: the set of vectors in $\bit^{2\mathfrak m}$ with Hamming weight $\mathfrak m$.
|
|
\item $\mathsf{B}^{3}_{\mathfrak m}$: the set of vectors in $\nbit^{3\mathfrak m}$ which has exactly $\mathfrak m$ coordinates equal to $j$ for each $j \in \nbit$.
|
|
\end{itemize}
|
|
\caption{Notations for Stern-like protocols.}
|
|
\label{fig:stern-notations}
|
|
\end{figure}
|
|
|
|
The original Stern protocol was designed to prove knowledge of a SDP preimage. That is, to prove the knowledge of a vector $\mathbf{w} \in \bit^m$ that verifies
|
|
\begin{equation} \label{eq:sdp-statement}
|
|
\mathbf{M} \cdot \mathbf{w} = \mathbf{v} \bmod 2.
|
|
\end{equation}
|
|
|
|
A first improvement by~\cite{KTX08} was to extend this protocol using a statistically hiding SIS-based commitment scheme as described in~\ref{fig:Interactive-Protocol} to prove in (statistical) zero-knowledge that
|
|
\begin{equation} \label{eq:isis-stern-relation}
|
|
\mathbf{M} \cdot \mathbf{w} = \mathbf{v} \bmod q.
|
|
\end{equation}
|
|
|
|
The details of this proof is given in \cref{sse:stern-abstraction}, but it can be summarized in the following Lemma.
|
|
|
|
\begin{lemma}[{\cite[Se. 4]{KTX08}}] \label{le:zk-ktx}
|
|
There exists a statistical \textsf{ZKAoK} with perfect completeness and soundness error 2/3 to prove the knowledge of a secret vector $\mathbf{w} \in \bit^m$ that verifies relation~\eqref{eq:isis-stern-relation} for public input $(\mathbf{M}, \mathbf{v}) \in \Zq^{n \times m} \times \Zq^{n}$.
|
|
\end{lemma}
|
|
|
|
Ling, Nguyen, Stehlé and Wang~\cite{LNSW13} noticed that the \textsf{ZKAoK} of \cref{le:zk-ktx} works in a straightforward manner to prove knowledge of a vector in $\nbit^m$.
|
|
|
|
%A method to relax the constraints on the \textsf{ZKAoK} of \cref{le:zk-ktx} is the so-called ``Decomposition-Extension'' technique~\cite{LNSW13,LSS14,ELL+15,LLNW16} as explained in the introduction of this Section (\cref{sse:stern}).
|
|
|
|
\index{Lattices!Inhomogeneous \SIS}
|
|
To prove the knowledge of an \ISIS preimage, i.e.
|
|
the knowledge of a bounded vector $\mathbf{w} \in [-B,B]^m$ that satisfies relation~\eqref{eq:isis-stern-relation}, the goal is to rewrite $\mathbf{w}$ as $\bar{\mathbf{w}} = \mathbf{K} \cdot \mathbf{w} \bmod q$ with a public transformation matrix $\mathbf{K}$ such that $\bar{\mathbf{w}} \in \nbit^{m'}$ and of known numbers of elements equal to $j$ for each $j \in \nbit$.
|
|
This reduces to use \cref{le:zk-ktx} to prove the knowledge of $\bar{\mathbf{w}} \in \nbit^{m'}$ for public input $(\mathbf{M} \cdot \mathbf{K}, \mathbf{v})$.
|
|
|
|
To construct such a transfer matrix $\mathbf{K}$, \cite{LNSW13} showed that \textit{decomposing} a vector $\mathbf{x} \in [-B,B]^m$ as a vector $\tilde{\mathbf{x}} \in \nbit^{m \cdot \delta_B}$ and \textit{extending} the resulting vector into $\bar{\mathbf{x}} \in \mathsf{B}^3_{m \delta_B}$ leads to a new statement that can be proven using the variant of Stern's protocol described in~\cite{KTX08}.
|
|
The resulting matrix $\mathbf{K}= \left[\mathbf{K}_{m,B}^{} \mid \mathbf{0}^{m \times 2m\delta_B}\right] \in \ZZ^{m \times 3m\delta_B}$, where $\mathbf{K}_{m,B}^{}$ is the \nbit-decomposition matrix $\mathbf{K}_{m,B} = \mathbf{I}_m \otimes \left[B_1 \mid \cdots \mid B_{\delta_B} \right]$ with $B_j^{} = \left\lfloor \frac{B + 2^{j-1}}{2^j} \right\rfloor$, for all $j \in \{1,\ldots,j\}$, can be computed from public parameters.
|
|
|
|
In \cref{ch:ge-lwe}, we extend Stern-like protocols to handle statements where the matrix~$\mathbf M$ of~\eqref{eq:isis-stern-relation} is kept hidden. For this purpose, we define the decomposition-extension method in more detail in~\cref{se:decomposition-extensions-permutations}.
|
|
|
|
|
|
\subsection{Abstraction of Stern's Protocol} \label{sse:stern-abstraction}
|
|
\addcontentsline{tof}{subsection}{\protect\numberline{\thesubsection} Abstraction du protocole de Stern}
|
|
|
|
\begin{figure}[t]
|
|
\small
|
|
\begin{enumerate}
|
|
\item \textbf{Commitment:} Prover samples $\mathbf{r}_w \leftarrow \U(\mathbb{Z}_q^D)$, $\phi \leftarrow \U(\mathcal{S})$ and randomnesses $\rho_1, \rho_2, \rho_3$ for $\mathsf{COM}$.
|
|
Then, he sends $\mathrm{CMT}= \big(C_1, C_2, C_3\big)$ to the verifier, where
|
|
\begin{gather*}
|
|
C_1 = \mathsf{COM}(\phi, \mathbf{M}\cdot \mathbf{r}_w \bmod q; \rho_1), \hspace*{5pt}
|
|
C_2 = \mathsf{COM}(\Gamma_{\phi}(\mathbf{r}_w); \rho_2), \\
|
|
C_3 = \mathsf{COM}(\Gamma_{\phi}(\mathbf{w} + \mathbf{r}_w \bmod q); \rho_3).
|
|
\end{gather*}
|
|
|
|
\item \textbf{Challenge:} The verifier sends a challenge $Ch \sample \U(\{1,2,3\})$ to the prover.
|
|
\item \textbf{Response:} Depending on $Ch$, the prover sends $\mathrm{RSP}$ computed as follows:
|
|
\smallskip
|
|
\begin{itemize}
|
|
\item $Ch = 1$: Let $\mathbf{t}_{w} = \Gamma_{\phi}(\mathbf{w})$, $\mathbf{t}_{r} = \Gamma_{\phi}(\mathbf{r}_w)$, and $\mathrm{RSP} = (\mathbf{t}_w, \mathbf{t}_r, \rho_2, \rho_3)$. \smallskip
|
|
|
|
\item $Ch = 2$: Let $\phi_2 = \phi$, $\mathbf{w}_2 = \mathbf{w} + \mathbf{r}_w \bmod q$, and
|
|
$\mathrm{RSP} = (\phi_2, \mathbf{w}_2, \rho_1, \rho_3)$. \smallskip
|
|
\item $Ch = 3$: Let $\phi_3 = \phi$, $\mathbf{w}_3 = \mathbf{r}_w$, and
|
|
$\mathrm{RSP} = (\phi_3, \mathbf{w}_3, \rho_1, \rho_2)$.
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
\textbf{Verification:} Receiving $\mathrm{RSP}$, the verifier proceeds as follows:
|
|
\smallskip
|
|
\begin{itemize}
|
|
\item $Ch = 1$: Check that
|
|
\begin{gather*}
|
|
\mathbf{t}_w \in \mathsf{VALID},\\
|
|
C_2 = \mathsf{COM}(\mathbf{t}_r; \rho_2), \qquad
|
|
{C}_3 = \mathsf{COM}(\mathbf{t}_w + \mathbf{t}_r \bmod q; \rho_3).
|
|
\end{gather*}
|
|
|
|
\item $Ch = 2$: Check that
|
|
\[
|
|
C_1 = \mathsf{COM}(\phi_2, \mathbf{M}\cdot \mathbf{w}_2 - \mathbf{v} \bmod q; \rho_1),\qquad
|
|
{C}_3 = \mathsf{COM}(\Gamma_{\phi_2}(\mathbf{w}_2); \rho_3).
|
|
\]
|
|
|
|
\item $Ch = 3$: Check that
|
|
\[
|
|
C_1 = \mathsf{COM}(\phi_3, \mathbf{M}\cdot \mathbf{w}_3; \rho_1), \qquad
|
|
C_2 = \mathsf{COM}(\Gamma_{\phi_3}(\mathbf{w}_3); \rho_2).
|
|
\]
|
|
|
|
\end{itemize}
|
|
In each case, the verifier outputs $1$ if and only if all the conditions hold.
|
|
\caption{Stern-like \textsf{ZKAoK} for the relation $\mathrm{R_{abstract}}$.}
|
|
\label{fig:Interactive-Protocol}
|
|
\end{figure}
|
|
\index{Zero Knowledge!Stern's protocol}
|
|
|
|
|
|
Let $K$, $D$, $q$ be positive integers with $D \geq K$ and $q \geq 2$, and let $\mathsf{VALID}$ be a subset of $\mathbb{Z}^D$. Suppose that $\mathcal{S}$ is a finite set such that every element $\phi \in \mathcal{S}$ can be associated with a permutation $\Gamma_\phi \in \permutations_D$ satisfying the following conditions:
|
|
\begin{eqnarray}\label{eq:zk-equivalence}
|
|
\begin{cases}
|
|
\mathbf{w} \in \mathsf{VALID} ~ \iff ~ \Gamma_\phi(\mathbf{w}) \in \mathsf{VALID}, \\
|
|
\text{If } \mathbf{w} \in \mathsf{VALID} \text{ and } \phi \text{ is uniform in } \mathcal{S}, \text{ then } \Gamma_\phi(\mathbf{w}) \text{ is uniform in } \mathsf{VALID}. \quad
|
|
\end{cases}
|
|
\end{eqnarray}
|
|
We aim to construct a statistical Zero-Knowledge Argument of Knowledge (\textsf{ZKAoK}) for the following abstract relation:
|
|
\begin{eqnarray*}
|
|
\mathrm{R_{abstract}} = \big\{ \big((\mathbf{M}, \mathbf{v}), \mathbf{w} \big) \in \mathbb{Z}_q^{K \times D} \times \mathbb{Z}_q^K \times \mathsf{VALID}: \mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q.\big\}
|
|
\end{eqnarray*}
|
|
|
|
Note that, Stern's original protocol corresponds to the special case when the set
|
|
$\mathsf{VALID} = \{
|
|
\mathbf{w} \in \bit^D: \mathsf{wt}(\mathbf{w}) = k\}$, where $\mathsf{wt}(\cdot)$ denotes the Hamming weight and $k < D$ is a given integer, $\mathcal{S} = \permutations_D$ is the set of all permutations of~$D$ elements and $\Gamma_{\phi}(\mathbf{w}) = \phi(\mathbf{w})$.
|
|
|
|
The conditions in \eqref{eq:zk-equivalence} play a crucial role to prove in zero-knowledge that $\mathbf{w} \in \mathsf{VALID}$. To this end, the prover samples a random $\phi \hookleftarrow \U(\mathcal{S})$ and lets the verifier check that $\Gamma_\phi(\mathbf{w}) \in \mathsf{VALID}$ without learning any additional information about $\mathbf{w}$ due to the randomness of $\phi$. Furthermore, to prove in a zero-knowledge manner that the linear equation is satisfied, the prover samples a masking vector $\mathbf{r}_w \hookleftarrow \U(\mathbb{Z}_q^D)$, and convinces the verifier instead that $\mathbf{M}\cdot (\mathbf{w} + \mathbf{r}_w) = \mathbf{M}\cdot \mathbf{r}_w + \mathbf{v} \bmod q.$
|
|
|
|
|
|
The interaction between prover $\mathcal{P}$ and verifier $\mathcal{V}$ is described in Figure~\ref{fig:Interactive-Protocol}. The protocol uses a statistically hiding and computationally binding string commitment scheme \textsf{COM} (e.g., the \textsf{SIS}-based scheme from~\cite{KTX08} described in~\cref{de:sis-commitment}).
|
|
|
|
\begin{theorem}\label{Theorem:zk-protocol}
|
|
The protocol in Figure~\ref{fig:Interactive-Protocol} is a statistical \emph{\textsf{ZKAoK}} with perfect completeness, soundness error~$2/3$, and communication cost~$\mathcal{O}(D \cdot \log q)$. Namely:
|
|
\begin{itemize}
|
|
\item There exists a polynomial-time simulator that, on input $(\mathbf{M}, \mathbf{v})$, outputs an accepted transcript statistically close to that produced by the real prover.
|
|
\item There exists a polynomial-time knowledge extractor that, on input a commitment $\mathrm{CMT}$ and $3$ valid responses $(\mathrm{RSP}_1,\mathrm{RSP}_2,\mathrm{RSP}_3)$ to all $3$ possible values of the challenge $Ch$, outputs $\mathbf{w}' \in \mathsf{VALID}$ such that $\mathbf{M}\cdot \mathbf{w}' = \mathbf{v} \bmod q.$
|
|
\end{itemize}
|
|
\end{theorem}
|
|
The proof of the theorem relies on standard simulation and extraction techniques for Stern-like protocols~\cite{KTX08,LNSW13,LLM+16}.
|
|
|
|
\begin{proof}
|
|
Note that, by construction, the protocol is perfectly complete: if an honest prover follows the protocol, then he always gets accepted by the verifier. It is also easy to see that the communication cost is bounded by $\widetilde{\mathcal{O}}(D \cdot \log q)$.
|
|
|
|
|
|
We will now prove that the protocol is a statistical zero-knowledge argument of knowledge for the relation $\mathrm{R_{abstract}}$ and is given below.
|
|
|
|
\smallskip
|
|
\scbf{Zero-Knowledge Property. } We construct a \textsf{PPT} simulator $\mathsf{SIM}$ interacting with a (possibly dishonest) verifier $\widehat{\mathcal{V}}$ such that, given only the public input, $\mathsf{SIM}$ outputs with probability negligibly close to $2/3$ a simulated transcript that is statistically close to the one produced by the honest prover in the real interaction.
|
|
|
|
The simulator first chooses a random $\overline{Ch} \in \{1,2,3\}$. This is a prediction of the challenge value that $\widehat{\mathcal{V}}$ will \emph{not} choose.
|
|
\smallskip
|
|
|
|
\begin{description}
|
|
\item[\textsf{Case} $\overline{Ch}=1$]: Using basic linear algebra over $\mathbb{Z}_q$, $\mathsf{SIM}$ computes a vector $\mathbf{w}' \in \mathbb{Z}_q^D$ such that $\mathbf{M}\cdot \mathbf{w}' = \mathbf{v} \bmod q.$
|
|
Next, it samples $\mathbf{r} \hookleftarrow \U(\mathbb{Z}_q^D)$, $\pi \hookleftarrow \U(\mathcal{S})$, and randomnesses $\rho_1, \rho_2, \rho_3$ for $\mathsf{COM}$.
|
|
|
|
Then, it sends the commitment $\mathrm{CMT}= \big(C'_1, C'_2, C'_3\big)$ to $\widehat{\mathcal{V}}$, where
|
|
\begin{gather*}
|
|
C'_1 = \mathsf{COM}(\pi, \mathbf{M}\cdot \mathbf{r}; \rho_1), \qquad
|
|
C'_2 = \mathsf{COM}(\Gamma_{\pi}(\mathbf{r}); \rho_2), \\
|
|
C'_3 = \mathsf{COM}(\Gamma_{\pi}(\mathbf{w}' + \mathbf{r}); \rho_3).
|
|
\end{gather*}
|
|
Receiving a challenge $Ch$ from $\widehat{\mathcal{V}}$, the simulator responds as follows:
|
|
\begin{itemize}
|
|
\item If $Ch=1$: Output $\bot$ and abort.
|
|
\item If $Ch=2$: Send $\mathrm{RSP} = \big(\pi, \mathbf{w}' + \mathbf{r}, \rho_1, \rho_3 \big)$.
|
|
\item If $Ch=3$: Send $\mathrm{RSP} = \big(\pi, \mathbf{r}, \rho_1, \rho_2\big)$.
|
|
\end{itemize}
|
|
|
|
|
|
\smallskip
|
|
|
|
\item[\textsf{Case} $\overline{Ch}=2$:] $\mathsf{SIM}$ samples $\mathbf{w}' \hookleftarrow \U(\mathsf{VALID})$, $\mathbf{r} \hookleftarrow \U(\mathbb{Z}_q^D)$, $\pi \hookleftarrow \U(\mathcal{S})$, and randomnesses $\rho_1, \rho_2, \rho_3$ for $\mathsf{COM}$.
|
|
|
|
Then, it sends the commitment $\mathrm{CMT}= \big(C'_1, C'_2, C'_3\big)$ to $\widehat{\mathcal{V}}$, where
|
|
\begin{gather*}
|
|
C'_1 = \mathsf{COM}(\pi, \mathbf{M}\cdot \mathbf{r}; \rho_1), \qquad
|
|
C'_2 = \mathsf{COM}(\Gamma_{\pi}(\mathbf{r}); \rho_2), \\
|
|
C'_3 = \mathsf{COM}(\Gamma_{\pi}(\mathbf{w}' + \mathbf{r}); \rho_3)
|
|
\end{gather*}
|
|
as previously.
|
|
|
|
Receiving a challenge $Ch$ from $\widehat{\mathcal{V}}$, the simulator responds as follows:
|
|
\begin{itemize}
|
|
\item If $Ch=1$: Send $\mathrm{RSP} = \big(\Gamma_\pi(\mathbf{w}'), \Gamma_\pi(\mathbf{r}), \rho_2, \rho_3\big)$.
|
|
\item If $Ch=2$: Output $\bot$ and abort.
|
|
\item If $Ch=3$: Send $\mathrm{RSP} = \big(\pi, \mathbf{r}, \rho_1, \rho_2\big)$.
|
|
\end{itemize}
|
|
|
|
\smallskip
|
|
|
|
\item[Case $\overline{Ch}=3$:] $\mathsf{SIM}$ samples $\mathbf{w}' \hookleftarrow \U(\mathsf{VALID})$, $\mathbf{r} \hookleftarrow \U(\mathbb{Z}_q^D)$, $\pi \hookleftarrow \U(\mathcal{S})$, and randomnesses $\rho_1, \rho_2, \rho_3$ for $\mathsf{COM}$.
|
|
|
|
Then, it sends the commitment $\mathrm{CMT}= \big(C'_1, C'_2, C'_3\big)$ to $\widehat{\mathcal{V}}$, where
|
|
\[ C'_2 = \mathsf{COM}(\Gamma_{\pi}(\mathbf{r}); \rho_2), \qquad C'_3 = \mathsf{COM}(\Gamma_{\pi}(\mathbf{w}' + \mathbf{r}); \rho_3)\]
|
|
as in the previous two cases, while
|
|
\begin{eqnarray*}
|
|
C'_1 = \mathsf{COM}(\pi, \mathbf{M}\cdot (\mathbf{w}'+ \mathbf{r}) - \mathbf{v}; \rho_1), \hspace*{5pt}
|
|
\end{eqnarray*}
|
|
Receiving a challenge $Ch$ from $\widehat{\mathcal{V}}$, it responds as follows:
|
|
\begin{itemize}
|
|
\item If $Ch=1$: Send $\mathrm{RSP}$ computed as in the case $(\overline{Ch}=2, Ch=1)$.
|
|
\item If $Ch=2$: Send $\mathrm{RSP}$ computed as in the case $(\overline{Ch}=1, Ch=2)$.
|
|
\item If $Ch=3$: Output $\bot$ and abort.
|
|
\end{itemize}
|
|
\end{description}
|
|
\smallskip
|
|
|
|
We observe that, in all the above cases, since $\mathsf{COM}$ is statistically hiding, the distribution of the commitment $\mathrm{CMT}$ and the distribution of the challenge~$Ch$ from~$\widehat{\mathcal{V}}$ are statistically close to those in the real interaction. Hence, the probability that the simulator outputs~$\bot$ is negligibly close to~$1/3$. Moreover, one can check that whenever the simulator does not halt, it provides an accepted transcript, the distribution of which is statistically close to that of the prover in the real interaction. In other words, we have designed a simulator that can successfully emulate the honest prover with probability negligibly far from~$2/3$.
|
|
|
|
\medskip
|
|
|
|
\scbf{Argument of Knowledge.} Let us assume that
|
|
\begin{gather*}
|
|
\mathrm{RSP}_1 = (\mathbf{t}_x, \mathbf{t}_r, \rho_{2}^{(1)}, \rho_{3}^{(1)}), \qquad
|
|
\mathrm{RSP}_2 = (\phi_2, \mathbf{y}, \rho_{1}^{(2)}, \rho_{3}^{(2)}),\\
|
|
\mbox{and }\mathrm{RSP}_3 = (\phi_3, \mathbf{w}_3, \rho_{1}^{(3)}, \rho_{2}^{(3)})
|
|
\end{gather*}
|
|
are $3$ valid responses to the same commitment $\mathrm{CMT} = (C_1, C_2, C_3)$, with respect to all $3$ possible values of the challenge. The validity of these responses implies that:
|
|
\[
|
|
\begin{cases}
|
|
\mathbf{t}_x \in \mathsf{VALID}; \\[2.5pt]
|
|
C_1 = \mathsf{COM}(\phi_2, \mathbf{M}\cdot \mathbf{w}_2 - \mathbf{v}; \rho_1^{(2)}) = \mathsf{COM}(\phi_3, \mathbf{M}\cdot \mathbf{w}_3; \rho_1^{(3)}); \\[2.5pt]
|
|
C_2 = \mathsf{COM}(\mathbf{t}_r; \rho_2^{(1)}) = \mathsf{COM}(\Gamma_{\phi_3}(\mathbf{w}_3); \rho_2^{(3)}); \\[2.5pt]
|
|
{C}_3 = \mathsf{COM}(\mathbf{t}_x + \mathbf{t}_r; \rho_3^{(1)}) = \mathsf{COM}(\Gamma_{\phi_2}(\mathbf{w}_2); \rho_3^{(2)}).
|
|
\end{cases}
|
|
\]
|
|
Since \textsf{COM} is computationally binding, we can deduce that:
|
|
\[
|
|
\begin{cases}
|
|
\mathbf{t}_x \in \mathsf{VALID}; \\
|
|
\phi_2 = \phi_3; \\
|
|
\mathbf{t}_r = \Gamma_{\phi_3}(\mathbf{w}_3);\\
|
|
\mathbf{t}_x + \mathbf{t}_r = \Gamma_{\phi_2}(\mathbf{w}_2); \\
|
|
\mathbf{M}\cdot \mathbf{w}_2 - \mathbf{v} = \mathbf{M}\cdot \mathbf{w}_3 \bmod q.
|
|
\end{cases}
|
|
\]
|
|
Let $\mathbf{w}' = \mathbf{w}_2 - \mathbf{w}_3$, then we have $\Gamma_{\phi_2}(\mathbf{w}') = \mathbf{t}_x \in \mathsf{VALID}$ which implies that $\mathbf{w}' \in \mathsf{VALID}$. Furthermore, we have $\mathbf{M}\cdot \mathbf{w}' = \mathbf{M}\cdot (\mathbf{w}_2 - \mathbf{w}_3) = \mathbf{v} \bmod q.$
|
|
|
|
This concludes the proof.
|
|
\end{proof}
|
|
|