## 5 Application
### CCA-Secure Linear KEM  
Let \(\text{GGen}^{\text{DLIN}}(\lambda)\) be a group generator generating a group \(\mathcal{G}=(\mathbb{G},p)\), where the decision linear assumption [21] holds. In the linear KEM, a public key consists of three group elements \((g_{1},g_{2},h)\in\mathbb{G}^{3}\) such that \(h=g_{1}^{x_{1}}=g_{2}^{x_{2}}\) with corresponding private key \((x_{1},x_{2})\in\mathbb{Z}_{p}^{2}\). The encapsulation is done by computing \(\text{ct}=(g_{1}^{w_{1}},g_{2}^{w_{2}})\in\mathbb{G}\) and \(\text{k}=h^{w_{1}+w_{2}}\in\mathbb{G}\), and decapsulation is done by computing \(\text{k}=(g_{1}^{w_{1}})^{x_{1}}(g_{2}^{w_{2}})^{x_{2}}\in\mathbb{G}\). Based on this scheme, the transformed IND-CCA-secure scheme is described as follows. For security parameter \(\lambda\), the setup algorithm proceeds as follows. Generate \(\mathcal{G}=(\mathbb{G},p)\) by running \(\text{GGen}^{\text{DLIN}}(\lambda)\). Choose a random generator \(g_{1}\in\mathbb{G}\) and a random exponent \(x_{1}\in\mathbb{Z}_{p}\). Choose a random exponent \(t\) and set \(g_{2}=g_{1}^{t}\in\mathbb{G}\) and \(x_{2}=x_{1}t^{-1}\in\mathbb{Z}_{p}\) such that \(g_{1}^{x_{1}}=g_{2}^{x_{2}}=h\) for some \(h\in\mathbb{G}\). Choose hash functions \(H_{1}:\{0,1\}^{*}\to\{0,1\}^{k}\subseteq\mathbb{Z}_{p}\) and \(H_{2}:\{0,1\}^{*}\to\{0,1\}^{\ell}\). Output \(\text{SK}=(x_{1},x_{2})\) and \(\text{PK}=(\mathbb{G},p,g_{1},g_{2},\,h,\,H_{1},\,H_{2})\). For a public key \(\text{PK}=(\mathbb{G},\,p,\,g_{1},\,g_{2},\,h,\,H_{1},\,H_{2})\), the Encap algorithm proceeds as follows. Choose random exponents \(w_{1},w_{2}\in\mathbb{Z}_{p}\). Set \(\text{stmt}=(g_{1},g_{2},h,g_{1}^{w_{1}},g_{2}^{w_{2}},h^{w_{1}+w_{2}})\) and \(\text{wt}=(w_{1},w_{2})\). \begin{tabular}{l l}
3. & Compute \(\pi\leftarrow\mathcal{P}^{H_{1}}(\text{stmt},\text{wt})\). \\  & (a) & Choose random exponents \(r_{1},r_{2}\in\mathbb{Z}_{p}\). \\  & (b) & Set \(\text{com}=(g_{1}^{r_{1}},g_{2}^{r_{2}},h^{r_{1}+r_{2}})\in\mathbb{G}^{3}\). \\  & (c) & Compute \(c=H_{1}(\text{stmt},\text{com})\) and \(s_{1}=r_{1}+w_{1}c\), \(s_{2}=r_{2}+w_{2}c\in\mathbb{Z}_{p}\). \\  & (d) & Output the proof \(\pi=(s_{1},s_{2},c)\). \\
4. & Set \(\mathsf{K}\gets H_{2}(\text{stmt},\text{com},\pi)\). \\
5. & Output \(\mathsf{K}\) and \(\mathsf{CT}=(g_{1}^{w_{1}},g_{2}^{w_{2}},\pi)\). \\  & **KEM.Decap**(\(\mathsf{PK},\mathsf{CT}\), \(\mathsf{SK}\)): For a public key \(\mathsf{PK}=(\mathbb{G},p,g_{1},g_{2},h,H_{1},H_{2})\), a ciphertext \(\mathsf{CT}=(\mathsf{ct}_{1},\mathsf{ct}_{2},\pi=(s_{1},s_{2},c))\), and a private \(\mathsf{SK}=(x_{1},x_{2})\), the Decap algorithm proceeds as follows. \\  & 1. & Compute \(\mathsf{k}=\mathsf{ct}_{1}^{x_{1}}\mathsf{ct}_{2}^{x_{2}}\in\mathbb{G}\) and set \(\text{stmt}=(g_{1},g_{2},h,\mathsf{ct}_{1},\mathsf{ct}_{2},\mathsf{k})\). \\  & 2. & If \(1\leftarrow\mathcal{V}^{H_{1}}(\text{stmt},\pi)\), go on. Otherwise, abort. \\  & (a) & Set \(\text{com}=(g_{1}^{s_{1}}\cdot\mathsf{ct}_{1}^{-c},g_{2}^{s_{2}}\cdot\mathsf{ct }_{2}^{-c},h^{(s_{1}+g_{2})}\cdot\mathsf{k}^{-c})\in\mathbb{G}^{3}\). \\  & (b) & If \(c=H_{1}(\text{stmt},\text{com})\), output \(1\). Otherwise, output \(0\). \\
3. & Set \(\mathsf{K}\gets H_{2}(\text{stmt},\text{com},\pi)\) and output \(\mathsf{K}\). \\ \end{tabular}   
Theorem 5.1: _Suppose that the \((t_{dlin},e_{dlin})\) decision linear assumption holds in \(\mathcal{G}\), and \(H_{1}\) and \(H_{2}\) are random oracles. Then, the linear KEM is \((t,e,q_{d})\)-IND-CCA-secure, where_  
\[\epsilon\leq\frac{\epsilon_{dlin}}{2}+\frac{q_{H_{1}}^{2}}{2^{k-1}}+\frac{q_{ H_{2}}^{2}}{2^{\ell-1}}+\frac{2q_{H_{1}}^{2}+2q_{d}\cdot(q_{H_{1}}+q_{H_{1}}^{2})+1}{p},t_{dlin}\approx t+\mathcal{O}(q_{d}t_{e}).\]  
_Here, \(\{q_{H_{1}},q_{H_{2}}\}\) are the numbers of \(\{H_{1},H_{2}\}\) queries, \(t_{e}\) is the required time for exponentiation in \(\mathcal{G}\), and \(p\) is the group order._  
Proof.