appendix_CKS_proof.tex

\section{Postponed Security Proof for Committee Key Scheme}
\label{supplementary_proof_sec_cks}

\begin{theorem} Given the hybrid model SNARK scheme secure for relation $\mathcal{R} \in \{ \Rlacom, \Racom\}$ as 
obtained using our two-step compiler in Section~\ref{sec_two_step_compiler} and the aggregatable signature scheme $\mathit{AS}$ 
                     as per Instantiation~\ref{insta:bls} (which fulfils Definition~\ref{def:aggregate_signatures}, with the additional 
                     specification that $\mathit{aux}_{\mathit{AS}} = v+1$ and choosing $v = n-1$, 
if we assume that an efficient adversary (against soundness of) $\mathit{CKS}_{\mathcal{R}}$ outputs public keys only from the source group $\ginn{1}$,  
then the committee key scheme $\mathit{CKS}_{\mathcal{R}}$ as per Instantiation~\ref{inst:cks} is secure with respect to Definition~\ref{def: committee_key}. 
\end{theorem}

\begin{proof} We prove below the statement only for $\Rlacom$. The statement can be proven analogously for $\Racom$. \\

In order to prove perfect completeness for $\mathit{CKS}_{\mathcal{R}}$ Instantiation~\ref{inst:cks} using a hybrid model SNARK secure for relation 
$\Rlacom$, we note that if $\mathit{AS.Verify}(\mathit{pp}, \mathit{apk}, m, \mathit{asig}) = 1$ holds, then due to the instantiation for \\
$\mathit{CKS_{\Rlacom}.Verify}$, we have that 
$$\mathit{CKS_{\Rlacom}.Verify}(\mathit{pp}, \mathit{rs}_{\mathit{vk}}, \mathit{ck}, m, \mathit{asig}, (\pi_{\mathit{SNARK}}, \mathit{apk}), (\mathit{bit_i})_{i=1}^{n-1}) =1$$ 
iff, in turn, 
$$\mathit{SNARK.Verify}(\mathit{rs_{vk}}, (\mathit{ck}, (\mathit{bit_i})_{i=1}^{n-1} || 0, \mathit{apk}), \pi_{\mathit{SNARK}}, \Rlacom) = 1 \ \ \ \ \ \ \ (1)$$ holds. 
Using the fact that the keys $\mathit{srs}$ and $(\mathit{rs}_{\mathit{pk}}, \mathit{rs}_{\mathit{vk}})$ for our hybrid model SNARK were generated correctly using 
$\mathit{SNARK.Setup}(v, 3v)$ and respectively $\mathit{SNARK.KeyGen}(\mathit{srs}, \Rlacom)$, 
 also since $(\mathit{pk_i})_{i=1}^{n-1} \in \ginn{1}^{n-1}$ as honestly generated by $\mathit{AS.GenerateKeypair}$, then 
$$(x = (\mathit{ck}, (\mathit{bit_i})_{i=1}^{n-1}||0, \mathit{apk}), w = (\mathit{pk}_i)_{i=1}^{n-1}) \in \Rlacom$$ 
(because $\mathit{apk} = \sum_{i=1}^{n-1} \mathit{bit_i} \cdot \mathit{pk_i}$ due to Instantiation~\ref{insta:bls} and 
$\mathit{ck}$ was honestly generated as  $\mathbf{Com}((\mathit{pk_i})_{i=1}^{n-1})$ as a pair of binding polynomial commitments to the $x$ and $y$ 
coordinates of the keys in $w$, respectively) and, finally, adding that the proof 
$\pi_{\mathit{SNARK}}$ was generated correctly as 
$$ \pi_{\mathit{SNARK}} \leftarrow \mathit{SNARK.Prove}(\mathit{rs_{pk}}, (x,w), \Rlacom),$$ 
then, by the perfect completeness property of the hybrid model SNARK for relation $\Rlacom$, we can conclude $(1)$.\\

\noindent The proof for the soundness property is described below. Let $\mathcal{A}$ be an efficient adversary that, 
whenever it outputs a vector of public keys $(\mathit{pk_i})_{i=1}^{n-1}$, the respective vector belongs to the set $\ginn{1}^{n-1}$. 
Assuming that the following holds 
$$\mathit{CKS_{\Rlacom}.Verify}(\mathit{pp}, \mathit{rs}_{\mathit{vk}}, \mathit{ck}, m, \mathit{asig}, \pi = (\pi_{\mathit{SNARK}}, \mathit{apk'}), (\mathit{bit_i})_{i=1}^{n-1}) =1,$$ 
then, according to instantiation for $\mathit{CKS_{\Rlacom}}$, it implies that both 
$$\mathit{AS.Verify(\mathit{pp}, \mathit{apk'}, m, \mathit{asig})} = 1 \ \ \ \ \ \ (2)$$ 
and 
$$\mathit{SNARK.Verify}(\mathit{rs_{vk}}, (\mathit{ck}, (\mathit{bit_i})_{i=1}^{n-1}||0, \mathit{apk'}), \pi_{\mathit{SNARK}}, \Rlacom) = 1  \ \ \ \ \ \ (3)$$
hold where $\mathit{apk'}$ was parsed from $\pi$. Since $\mathit{ck}$ was generated correctly as the pair of binding polynomial commitments 
$\mathbf{Com}((\mathit{pk_i})_{i=1}^{n-1)}$ using the vector $(\mathit{pk_i})_{i=1}^{n-1}$ output by the adversary $\mathcal{A}$ 
(which, as per adversary definition, belongs to $\ginn{1}^{n-1}$) and due to the knowledge 
soundness property of the SNARK scheme secure for relation $\Rlacom$, the knowledge soundness and the computational binding property 
of the polynomial commitment scheme (since for our $\mathit{CKS_{\mathcal{R}}}$ instantiation we use the KZG commitment scheme), it implies that, 
with overwhelming probability $$(x = (\mathit{ck}, (\mathit{bit_i})_{i=1}^{n-1}, \mathit{apk'}), w = (\mathit{pk}_i)_{i=1}^{n-1}) \in \Rlacom.$$ 
From this, in turn, by the definition of relation $\Rlacom$, we obtain that 
$\mathit{apk'} = \sum_{i=1}^{n-1} \mathit{bit_i} \cdot \mathit{pk_i}$. Moreover, by the instantiation of aggregatable signature scheme 
$\mathit{AS}$, we have that $\sum_{i=1}^{n-1} \mathit{bit_i} \cdot \mathit{pk_i} = \mathit{AS.AggregateKeys}(\mathit{pp}, (\mathit{pk_i})_{i:\mathit{bit_i = 1}})$ 
and, as per soundness challenge definition, it holds that \\
$\mathit{apk} \leftarrow \mathit{AS.AggregateKeys}(\mathit{pp}, (\mathit{pk_i})_{i:\mathit{bit_i = 1}})$. Hence $\mathit{apk'} = \mathit{apk}$.
Finally, due to $(2)$, we conclude that $$\mathit{AS.Verify(\mathit{pp}, \mathit{apk}, m, \mathit{asig})} = 1$$ holds with overwhelming probability (q.e.d.).

\end{proof}