# Privacy Protection Based on Special Identifiers of Intersection Base Computing Technology
## 3 Protocol Process and Proof of Security
### Protocol Security  
**Theorem 1**. : _The privacy intersection cardinality protocol PSI-CA is secure._  
**Proof of Theorem 1. ** Under a semi-honest model, this theorem is proved by constructing the simulators \(S_{1}\) and \(S_{2}\) to make Equations (1) and (2) hold, in the protocol PSI-CA  
\[view_{1}^{\pi}(X,Y)=\{X,\lambda_{i},r_{i},E(W),f_{1}(X,Y)\} \tag{1}\]  
\[view_{2}^{\pi}(X,Y)=\big{\{}Y,\pi_{j},r_{j},r_{t},E(A),f_{2}(X,Y)\big{\}} \tag{2}\]  
where \(X\) and \(Y\) are the input from [PERSON] and [PERSON], \(\lambda_{i}\) is the bite number of \(x_{i}\), \(r_{i}\) is the random number chosen by [PERSON] during encryption, \(\pi_{j}\) is the bite number of \(y_{j}\), and \(r_{j}\) and \(r_{t}\) are the random numbers chosen by [PERSON] after different encryption operations, where \(E(A)\) refers to the ciphertext information sent by [PERSON] to [PERSON]. We also have the ciphertext message that [PERSON] sends to [PERSON], while \(f_{1}(X,Y)\)_and_\(f_{2}(X,Y)\) is the output received by [PERSON] and [PERSON], respectively. Firstly, simulator \(S_{1}\) is constructed to simulate \(view_{1}^{\pi}(X,Y)\); the \(S_{1}\) simulation process is as follows:  
1. Accept input \((X,f_{1}(X,Y))\); based on the values of \(f_{1}(X,Y)\), select set \(Y^{\prime}=\{y_{1}{}^{\prime},y_{2}{}^{\prime},\ldots,y_{n}{}^{\prime}\}\), \(f_{1}(X,Y^{\prime})=f_{1}(X,Y)\), and let \(X^{\prime}=\{-x_{1},-x_{2},\ldots,-x_{m}\}\). The \(S_{1}\) encryption set \(X^{\prime}\) obtains \(E(X^{\prime})=\{E(-x_{1}),E(-x_{2}),\ldots,E(-x_{m})\}\) and calculates \({v_{t}}^{\prime}=(E(-x_{i})\times E({y_{j}}^{\prime}))^{r_{s}}\text{mod}N^{2}\). 3. Where \(S_{1}\) gives the element of the encrypted set \(E(W)\) as \({v_{t}}^{\prime}(t\in\{1,2,\ldots,n\times m\})\), to decrypt it, by calculating the number of zero elements, you can judge the number of intersections of the two sides, and obtain the corresponding result. In protocol execution, \(view_{1}^{\pi}(X,Y)=\{X,r_{i},E(W),f_{1}(X,Y)\}\): \[S_{1}(X,f_{1}(X,Y))=\big{\{}X,r_{i},E(W^{\prime}),f_{1}(X,Y^{\prime})\big{\}}\] Because \(E(W)=\{{v_{1}}^{\prime},\ldots,{v_{2}}^{\prime},\ldots,{v_{t}}^{\prime},\ldots,{v_{n\times m}}^{\prime}\}(t\in\{1,2,\ldots,n\times m\})\) is created by [PERSON] based on the \(E(X^{\prime})\) sent by [PERSON], the \(E(Y)\) to which the individual belongs, and the random number \(r_{s}\), although [PERSON] has a private key for decryption, she can only know that the decrypted information is composed of (0,random number). It is impossible to know which ciphertext can be decrypted to obtain 0 or a random number. So, we have \(E(W)\overset{c}{\equiv}E(W^{\prime})\), and because \(f_{1}(X,Y)=f_{1}(X,Y^{\prime})\), so we have: \[\{S_{1}(X,f_{1}(X,Y))\}_{X.Y}\overset{c}{\equiv}\{view_{1}^{\pi}(X,Y)\}_{X,Y}\] Secondly, the simulator \(S_{2}\) is constructed to simulate \(view_{2}^{\pi}(X,Y)\). The simulation process of \(S_{2}\) is as follows: 1. Accept input \((Y,f_{2}(X,Y))\), according to the values of \(f_{2}(X,Y)\), select the set \(X^{\prime}=\{x_{1}}^{\prime},x_{2}^{\prime},\ldots,x_{n}^{\prime}\},f_{2}(X^{ \prime},Y)=f_{2}(X,Y)\), and let \(X^{a}=\{-x_{1}}^{\prime},-x_{2}^{\prime},\ldots,-x_{m}^{\prime}\}\). 2. The \(S_{2}\) encrypted set \(X^{a}\) gains \(E(X^{a})=\{E(-x_{1}}^{\prime}),E(-x_{2}^{\prime}),\ldots,E(-x_{m}^{\prime})\}\) and calculates \({v_{t}}^{\prime}=(E(-x_{i}^{\prime})\times E(y_{j}^{\prime}))^{r_{s}}\text{ mod}N^{2}\). 3. \(S_{2}\) obtains the encryption set \(E(A)=E(X^{a})\), \(S_{2}\) decrypts it, and the corresponding result can be obtained by calculating the number of zero elements and judging the number of intersections between the two sides. In the execution of the agreement, \(view_{2}^{\pi}(X,Y)=\{X,r_{j},r_{s},E(W),f_{1}(X,Y)\}\), while \[S_{2}(X,f_{2}(X,Y))=\big{\{}X,r_{j},r_{s},E(A^{\prime}),f_{2}(X^{\prime},Y)\big{\}}\] Since \(E(A)\) is encrypted by [PERSON] and [PERSON] has no private key, according to the semantic security of the encryption algorithm, for [PERSON], \(E(A)\overset{c}{\equiv}E(A^{\prime})\).