# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 2 Preliminaries
### Definition  
Below we provide some definitions that will be used in this paper. **Definition 1** (Negligible Function). : _Let \(n\) denote the input size of an algorithm. A function \(negl(n)\) is called negligible if it is a function that approaches zero more rapidly than the inverse of any polynomial. Specifically, for any polynomial \(poly(n)\), there exists an integer \(n\) such that for all \(n\geqslant N\), the inequality \(negl(n)\leq\frac{1}{poly(n)}\) always holds. If the probability of an event occurring is given by a negligible function \(negl(n)\), then the event is said to be negligible. Conversely, if the probability of an event occurring is \(1-negl(n)\), then the event is said to occur with overwhelming probability._  
**Definition 2** (B-Bounded Distribution). : _A collection of distributions \(\left\{\chi_{n}\right\}_{n\in N}\) over integers is called B-bounded if it satisfies the following equation._  
\[\Pr_{\mathbf{x}\leftarrow\succ_{n}}\left[\|\mathbf{e}\|>B\right]=negl(n)\]  
**Definition 3** (\(\beta\)-Noisy Ciphertext). : _A message msg encrypted under the secret key \(\mathbf{sk}=\mathbf{t}\) results in a \(\beta\)-noisy ciphertext \(\mathbf{C}\), satisfying \(\mathbf{tc}=\mathbf{\psi t}\mathbf{G}_{n}+\mathbf{e}\), where \(||\mathbf{e}||\leq\beta\)._  
**Definition 4** (Multi-Identity Based Fully Homomorphic Encryption Scheme). : _An MIBFHE scheme is comprised of six probabilistic polynomial-time (PPT) algorithms: Setup, Extract, Enc, Extend, Eval, and Dec, each defined as follows:_  
\(\mathbf{Setup}\big{(}1^{\lambda},1^{\mathcal{D}},1^{\mathcal{L}}\big{)}\)_: Input the security parameter \(\lambda\), the maximum depth \(L\) of homomorphic operation circuits, and the maximum number of user identities \(D\). Output the master public key (MPK) and master secret key (MSK)._\(\mathbf{Extract}(MPK,MSK,id)\): Input the \(MPK\), \(MSK\), and identity vector \(id\). Output the identity public key \(\mathbf{A}_{id}\) and corresponding private key \(\mathbf{s}\mathbf{k}_{id}\). \(\mathbf{Enc}(MPK,id,msg\in\{0,1\})\): Input \(MPK\), identity \(id\), and message \(msg\in\{0,1\}\). Output a fresh ciphertext \(\mathbf{C}_{id}\). \(\mathbf{Extend}(MPK,(id_{1},id_{2},\cdots,id_{D}),\mathbf{C}_{id})\): Input \(MPK\), the necessary identities \((id_{1},id_{2},\cdots,id_{D})\), and the fresh ciphertext \(\mathbf{C}_{id}\). Compute and output the extended ciphertext for the concatenated identities \((id_{1},id_{2},\cdots,id_{D})\) \(\mathbf{Eval}(MPK,\hat{\mathbf{C}}_{id_{1}},\hat{\mathbf{C}}_{id_{2}},\cdots, \hat{\mathbf{C}}_{id_{D}},f)\): Input \(MPK\), a Boolean circuit \(f\), and the ciphertexts \(\big{(}\hat{\mathbf{C}}_{id_{1}},\hat{\mathbf{C}}_{id_{2}},\cdots,\hat{ \mathbf{C}}_{id_{D}}\big{)}\). Output the result ciphertext \(\hat{\mathbf{C}}_{eval}\). \(\mathbf{Dec}(MPK,\big{(}\mathbf{s}\mathbf{k}_{id_{1}},\mathbf{s}\mathbf{k}_{ id_{2}},\cdots,\mathbf{s}\mathbf{k}_{id_{D}}\big{)},\mathbf{C}_{id})\): Input \(MPK\), the concatenated private keys of \(D\) identities, and the extended ciphertext \(\mathbf{C}_{id}\). Output the message \(msg\in\{0,1\}\). Definition 5 (Indistinguishable from Random, Select-Identity, Chosen-Plaintext Attachment): (IND-sID-CPA) imposes additional restrictions on the adversary, requiring the adversary to declare the target identity it plans to attack before obtaining the public parameters. For an MIBFHE scheme, the security model between the challenger \(\mathcal{C}\) and the PPT adversary \(\mathcal{A}\) is defined as follows:  
Initialization Phase: The adversary \(\mathcal{A}\) first declares the target identity \(id^{*}\) it plans to attack. Then, given the maximum depth \(L\) of the computation circuit and the number of participating user identities \(D\), the challenger \(\mathcal{C}\) runs the initialization algorithm Setup to generate MPK and \(MSK\), and sends the MPK to the adversary. Query Phase: The adversary \(\mathcal{A}\) initiates private key queries for \(id_{i}\
eq id^{*}(i=1,\cdots,D)\).