# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 3 Identity-Based Encryption Scheme
### Correctness and Parameters  
**Theorem 1**.: _When \(m=n\cdot\omega(\log b+1),Q=m^{\frac{3}{2}}\sqrt{n}\omega(\log n),\sigma=\sqrt{m} \omega(\log n),\alpha<\sigma\cdot\sqrt{m}\cdot\omega(\sqrt{\log n})^{-1}\). According to Definition 1, we state the IBE we described in Section 3.1 achieves correct decryption with overwhelming probability._  
**Proof of Theorem 1.** From the decryption formula, we have  
\[\mathbf{sk}_{id}^{T}\cdot\mathbf{c}_{id} =\mathbf{sk}_{id}^{T}\Big{(}\mathbf{A}_{id}^{\prime T}\mathbf{+} \mathbf{\hat{v}}+\mathbf{e}\Big{)}\] \[=\mathbf{sk}_{id}^{T}\mathbf{A}_{id}^{\prime T}\mathbf{y}+ \left\langle\mathbf{sk}_{id}^{T},\mathbf{\hat{v}}\right\rangle+\left\langle \mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle\] \[=\mathbf{e}_{app}\mathbf{y}+ms_{g}\bigg{[}\frac{Q}{2}\bigg{]}+ \left\langle\mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle\]  
Let \(\mathbf{e}=(\mathbf{e_{0}}\parallel\mathbf{e_{1}})\in\mathbb{Z}_{Q}\times \mathbb{Z}_{Q}^{m\times 1}\),Then we have \(\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle\right|=\left| \mathbf{e_{0}}-\left\langle\mathbf{t}_{id}^{T},\mathbf{e_{1}}\right\rangle \right|\leq\left|\mathbf{e_{0}}\right|+\left|\langle\mathbf{t}_{id}^{T}, \mathbf{e_{1}}\rangle\right|\). From Lemma 1, we know that \(\left\|\mathbf{t}_{id}\right\|\leq\sigma\sqrt{m}\), where \(\sigma\geq s_{1}(\mathbf{R})\cdot\omega\big{(}\sqrt{\log n}\big{)}=\sqrt{m} \omega(\log n)\); From Lemma 2, we have  
\[\left|\left\langle\mathbf{t}_{id}^{T},\mathbf{e_{1}}\right\rangle\right|\leq \left\|\mathbf{t}_{id}\right\|Q\alpha\omega\Big{(}\sqrt{\log m}\Big{)}+\frac{ \left\|\mathbf{t}_{id}\right\|\sqrt{m}}{2}\leq\sigma\sqrt{m}Q\alpha\omega \Big{(}\sqrt{\log m}\Big{)}+\mathcal{O}(\sigma m)\]  
\[\text{i.e.,}\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle \right|=\left|\mathbf{e_{0}}\right|+\left|\left\langle\mathbf{t}_{id}^{T}, \mathbf{e_{1}}\right\rangle\right|\leq\sigma\sqrt{m}Q\alpha\omega\Big{(}\sqrt {\log m}\Big{)}+\mathcal{O}(\sigma m).\]  
To ensure the correctness of the IBE scheme's decryption, the relevant parameter values must satisfy the following conditions:  
1. To guarantee the decryption algorithm works correctly, it is necessary to ensure that the error term satisfies \(\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle\right|<\frac{Q} {4}\). As stated in GPV08, this condition holds when \(\alpha\leq\big{(}\sigma\sqrt{m+1}\cdot\omega(\sqrt{\log n})\big{)}^{-1}\) and \(Q\geq 5\sigma(m+1)\), it is highly probable that \(\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle\right|\leq \frac{Q}{5}<\frac{Q}{4}\), and \(\left|\mathbf{e}_{app}\mathbf{y}\right|<\frac{Q}{20}\). When \(\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{e}\right\rangle\right|<\frac{Q} {4}\), if \(msg=1\), then \(\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{c}_{id}\right\rangle\right|- \left|\frac{Q}{2}\right|\right|<\frac{Q}{4}\); if \(msg=0\), then \(\left|\left\langle\mathbf{sk}_{id}^{T},\mathbf{c}_{id}\right\rangle\right|< \frac{Q}{4}\), Clearly, the decryption algorithm is capable of successfully decrypting with overwhelming probability.
2. The hardness assumption of the LWE problem requires that \(\alpha Q>2\sqrt{n}\). From the above, we know that when \(\alpha\) and \(Q\) are chosen to their extreme values, we can achieve, We can ensure \(\alpha\cdot Q=\frac{5\sqrt{m+1}}{\omega\big{(}\sqrt{\log n}\big{)}}>\frac{5 \sqrt{2n\log q}}{\omega\big{(}\sqrt{\log n}\big{)}}>2\sqrt{n}\), meeting the security condition of the LWE problem \(\alpha Q>2\sqrt{n}\). Based on the above analysis, we set the scheme parameters \((m,Q,\sigma,\alpha)\) as follows: \[m =n\log q+n\log_{b}q=n\cdot\omega(\log b+1)\] \[Q =m^{\frac{3}{2}}\sqrt{n}\omega(\log n)\] \[\sigma =\sqrt{m}\omega(\log n)\] \[\alpha <\sigma\cdot\sqrt{m}\cdot\omega(\sqrt{\log n})^{-1}\]