A Secure and Lightweight Multi-Party Private Intersection-Sum Scheme over a Symmetric Cryptosystem

Abstract

A private intersection-sum (PIS) scheme considers the private computing problem of how parties jointly compute the sum of associated values in the set intersection. In scenarios such as electronic voting, corporate credit investigation, and ad conversions, private data are held by different parties. However, despite two-party PIS being well-developed in many previous works, its extended version, multi-party PIS, has rarely been discussed thus far. This is because, depending on the existing works, directly initiating multiple two-party PIS instances is considered to be a straightforward way to achieve multi-party PIS; however, by using this approach, the intersection-sum results of the two parties and the data only belonging to the two-party intersection will be leaked. Therefore, achieving secure multi-party PIS is still a challenge. In this paper, we propose a secure and lightweight multi-party private intersection-sum scheme called SLMP-PIS. We maintain data privacy based on zero sharing and oblivious pseudorandom functions to compute the multi-party intersection and consider the privacy of associated values using arithmetic sharing and symmetric encryption. The security analysis results show that our protocol is proven to be secure in the standard semi-honest security model. In addition, the experiment results demonstrate that our scheme is efficient and feasible in practice. Specifically, when the number of participants is five, the efficiency can be increased by 22.98%.

1. Introduction

With the rapid development of artificial intelligence [1,2,3,4,5,6] and cloud computing [7,8,9,10,11], as a carrier of collaborative computing, the use of data is becoming increasingly important in various industries [12,13,14,15,16,17]. However, these data involve a large amount of private information, and the leakage of private data will cause serious security problems. Therefore, privacy computing [18,19,20,21] has been widely considered the optimal solution for maintaining data security [22,23,24,25] and protecting privacy [26,27,28,29]. Private intersection-sum (PIS) is one of the most commonly used privacy-preserving protocols in specific scenarios. It allows each party to hold a private set of data, and non-leadership parties additionally hold a private integer value associated with each datum, to jointly compute the sum of the associated integer values in the intersection.

Up to now, the two-party PIS has been applied in various fields, such as ad conversions [30] and electronic voting [31]. However, in other scenarios, private data are held by different parties. For example, in enterprise credit investigations, it is necessary to count the total amount of loans of multiple legal persons across different banks. Therefore, the multi-party PIS protocol must be considered. In addition, it is difficult for parties to participate in online computing in real time. Therefore, the outsourcing of data to the cloud by the participant, i.e., outsourced multi-party PIS, is a potential solution.

However, on the one hand, the existing PIS protocols primarily consider the two-party scenarios [30,31,32,33]. The function of multi-party PIS can be realized by executing the two-party PIS protocol multiple times, but using this approach, the intersection-sum results of the two parties and the data only belonging to the two-party intersection will be leaked. On the other hand, cloud systems store a large amount of user data and present greater temptation for attackers to conduct data mining and other attacks on private user data in the cloud. Therefore, it is challenging to design an outsourcing multi-party PIS protocol.

To summarize, we achieve the following contributions:

• We propose a secure and lightweight multi-party private intersection-sum scheme, called SLMP-PIS, which avoids the data privacy leakage problem of only repeatedly conducting existing two-party PIS schemes.
• SLMP-PIS is client-agnostic. The requester can ask the cloud server to obtain the computation result without the help of data owners, and data owners can maintain their offline status as long as their data have been outsourced securely to the cloud.
• SLMP-PIS is based on symmetric cryptosystem only. Therefore, the larger the number of participants, the more efficient SLMP-PIS is. Specifically, when the number of participants is five, the efficiency can be increased by 22.98%.

The remaining parts of this paper are organized as follows. Section 2 shows the related work associated with our work. Section 3 describes preliminaries used in our scheme, and we introduce the problem’s formulations, including the system model and adversary model in Section 4. Section 5 presents the scheme’s construction in detail. In Section 6, we conduct a security analysis, followed by Section 7, which shows the performance analysis. Finally, the conclusions of this whole paper are summarized in Section 8.

2. Related Work

We first introduce the related work on PIS. Ion et al. [32] described three PIS with cardinality protocols. One relies on a Diffie–Hellman-style double masking, and the other two use random oblivious transfer and encrypted Bloom filters. Miao et al. [33] proposed a private intersection-sum scheme with cardinality based on a shuffled, distributed, oblivious, pseudorandom function (DOPRF); Pedersen commitments; ElGamal encryptions; and Camenisch–Shoup encryptions. Niu et al. [34] described a privacy-preserving statistical computing protocol for the private set intersection to complete the relevant statistical computations of the intersection of two private sets, including cardinality, sum, average, variance, range, and so forth.

Currently, the PIS protocol has been applied in specific fields. Ion et al. [30] proposed a private intersection-sum protocol with the purpose of attributing aggregate ad conversions. Lu et al. [31] described a private intersection weighted sum protocol for privacy-preserving score-based voting with perfect ballot secrecy. Kulshrestha et al. [35] proposed a non-strict private intersection-sum protocol to compute ${\sum }_{x\in I}T\left[x\right]$, where $I=X_0\bigcap \left({\bigcup }_{i=1}^{n-1}{X}_i\right)$ and T is associated with values of X; the protocol was applied for estimating incidental collection in foreign intelligence surveillance.

In summary, the current state of the research shows that there have been PIS schemes based on different cryptographic primitives, and existing schemes are dedicated to minimizing the computational cost and communication overhead of the protocol while satisfying the basic security properties of PIS. However, none of them consider the strict multi-party privacy intersection-sum problem.

3. Preliminaries

In this section, we introduce some cryptographic tools, including oblivious transfer (OT), oblivious pseudorandom function (OPRF), and arithmetic sharing (AS).

3.1. Oblivious Transfer

Oblivious transfer [36,37] is a two-party protocol between a sender and a receiver. For 1-out-of-2 OT, the sender uses two private inputs, $m_0$ and $m_1$, and the receiver uses one private input bit $\sigma (\sigma \in \left\{0,1\right\})$. After the protocol, the receiver obtains $m_{\sigma }$. Moreover, 1-out-of-2 OT must satisfy the following properties:

(1)

Receiver’s indistinguishability security. For any $\sigma ,\tau \in \left\{0,1\right\}$ and for any probabilistic polynomial time (PPT) adversary $\mathcal{A}$ executing the sender’s part, the views that $\mathcal{A}$ sees in case the receiver tries to obtain $m_{\sigma }$ and in case the receiver tries to obtain $m_{\tau }$ are computationally indistinguishable given $m_0$ and $m_1$.

(2)

Sender’s indistinguishability security.For any adversary $\mathcal{A}$ substituting the receiver and a simulator ${\mathcal{A}}^{{}^{\prime }}$ playing the receiver’s role in the ideal model, the outputs of $\mathcal{A}$ and ${\mathcal{A}}^{{}^{\prime }}$ are statistically indistinguishable given $m_0$ and $m_1$.

3.2. Oblivious Pseudorandom Function

The oblivious pseudorandom function [38] involves two parties: one is the sender (denoted by S), and the other is the receiver (denoted by R). R takes data y as input. After the protocol is executed, R obtains the pseudorandom function value $F_y=F(k,y)$ of the data y, but cannot obtain any information about k. S obtains the key k of the pseudorandom function, so the pseudorandom function value $F_x=F(k,x)$ can be calculated for any data x.

3.3. Arithmetic Sharing

The arithmetic sharing protocol involves two parties: one is $P_0$, and the other is $P_1$. For a secret x, $P_0$ and $P_1$ each obtain a shared value. No one can obtain x alone, and they can recover x together.

Arithmetic sharing contains three algorithms, the shared values, sharing, and reconstruction, which are described as follows:

• Shared Values: on input secret $x(x\in Z_N)$, output sharing values ${〈x〉}_0^A,{〈x〉}_1^A$ satisfying ${〈x〉}_0^A+{〈x〉}_1^A=xmodN$.
• Sharing: $P_i(i\in \left\{0,1\right\})$ chooses $r(r\in Z_N)$ and sets ${〈x〉}_i^A=(x-r)modN$. Then, $P_i$ sends r to $P_{1-i}$, that is, ${〈x〉}_{1-i}^A=rmodN$.
• Reconstruction: $P_{1-i}$ sends ${〈x〉}_{1-i}^A$ to $P_i$, which computes $x=({〈x〉}_0^A+{〈x〉}_1^A)modN$.

4. Problem Formulations

In this section, we introduce the system model and adversary model of SLMP-PIS.

4.1. System Model

The system model of SLMP-PIS is shown in Figure 1. It contains three entities: a requester (Re), a cloud server (CS), and data owners (DOs).

(1)

Requester. The Re is responsible for submitting the processed data set to CS. In addition, the Re obtains the sharing value of the intersection-sum from the CS and computes the private intersection-sum result.

(2)

Cloud Server. The CS acts as a connection between the Re and DOs. After receiving the processed data set from the Re, the CS assists the DOs in performing data processing and obtaining the processed data sets from the DOs. In addition, the CS computes the sharing value of the intersection-sum and sends it to the Re.

(3)

Data Owners. Each DO holds a private set of data, and additionally holds a private integer value associated with each element. Each DO is responsible for submitting the processed data set to the CS.

4.2. Adversary Model

In the adversary model of SLMP-PIS, the Re, CS, and DOs are semi-honest parties. They strictly follow the protocol. However, the Re is interested in learning the data for the DOs and the private integer value associated with each element in the DOs’ sets. Each DO is willing to learn the data of the Re and the other DOs. The CS remains curious about the raw data of the Re and DOs.

Therefore, we introduce three active adversaries in our model: ${\mathcal{A}}_1$, ${\mathcal{A}}_2$, and ${\mathcal{A}}_3$. The goal of ${\mathcal{A}}_1$ is to learn the data of the Re. The goal of ${\mathcal{A}}_2$ is to obtain the data and associated values of the DOs. The goal of ${\mathcal{A}}_3$ is to obtain the private intersection-sum result. ${\mathcal{A}}_1$, ${\mathcal{A}}_2$, and ${\mathcal{A}}_3$ possess the following capabilities:

(1)

${\mathcal{A}}_1$,${\mathcal{A}}_2$, and ${\mathcal{A}}_3$ may eavesdrop on all communication links to obtain data owned by participants.

(2)

${\mathcal{A}}_1$ may compromise the CS to learn the data of the Re.

(3)

${\mathcal{A}}_2$ may compromise the CS to learn the DOs’ data and associated values, or compromise one DO to learn the data and associated values of the other DOs.

(4)

${\mathcal{A}}_3$ may compromise the CS and DOs to obtain the intersection-sum result.

5. The Protocol Framework

In this section, we first provide some notations used in the protocol framework in

Table 1. Notations.

Notation	Description
$\left|X\right|$	The size of the data set X
$x_i$	The i-th data of X
$\left[m\right]$	The set $\left\{1,2,\dots ,m\right\}$
$D{O}^{\left(u\right)}$	The u-th DO of the DOs
$Y^{\left(u\right)}$	The data set of the $D{O}^{\left(u\right)}$
$y_i^{\left(u\right)}$	The i-th data of $Y^{\left(u\right)}$
$Enc$	The asymmetric encryption algorithm
$Dec$	The asymmetric decryption algorithm
$MTgen$	Merkle tree generation algorithm
$F(·)$	Pseudorandom function

, and we present the overview of our scheme in Figure 2. The details will be described in the following sections.

5.1. Initialization

In this phase, multiple parties (i.e., the Re and DOs) negotiate a symmetric key $k_{ij}|i\ne j$ with each other. The CS chooses a random private key a, $D{O}^{\left(u\right)}$ chooses $b^{\left(u\right)}$, and the Re chooses c. The CS negotiates the session key $k_{a{b}^{\left(u\right)}}$ with $D{O}^{\left(u\right)}$. The Re negotiates the session key $k_{ac}$ with the CS. The Re and DOs share a group key K ($\left|K\right|=l$). In addition, several functions are selected: a pseudorandom function (PRF) $F(K,x):{\left\{0,1\right\}}^l\times {\left\{0,1\right\}}^{*}\to {\left\{0,1\right\}}^{d_1}$, and hash functions $H:{\left\{0,1\right\}}^w\to {\left\{0,1\right\}}^{d_2}$.

5.2. Outsourcing Request

In this phase, the Re runs data processing on the input of data set $X\left(\right|X|=m)$ to generate $\left\{En{c}_{Re},roo{t}_{Re}\right\}$. The details are shown in Algorithm 1, and we divide this stage into several steps as follows:

(1)

Generate the pseudorandom function value. The Re computes the pseudorandom function value $rand{f}_{x_i}$ of the data $x_i$ based on the group key K; namely, $rand{f}_{x_i}=F(K,x_i)$.

(2)

Generate the intersection sharing value. For each datum $x_i$, the Re first computes the pseudorandom function value $F_j$ based on the symmetric key $k_{0j}(j\in \left[n\right])$; namely, $F_j=F(k_{0j},x_i)$. Then, the Re XORs multiple $F_j$ according to the formula (1) to generate the intersection sharing value $S{h}_{x_i}$:

$$S{h}_{x_i}=F_1\oplus \cdots \oplus F_n$$

(1)

(3)

Generate ciphertext and verification information for pseudorandom function values and intersection sharing values. The Re calculates the ciphertext $\left\{ciphe{r}_{R{e}_1},\dots ,ciphe{r}_{R{e}_m}\right\}$ and the root $roo{t}_{Re}$ of the Merkle tree according to the formula (2) based on pseudorandom function values and intersection sharing values $\left\{rand{f}_{x_1}\left|\right|S{h}_{x_1},\dots ,rand{f}_{x_m}\left|\right|S{h}_{x_m}\right\}$:

$$\left\{\begin{array}{c}ciphe{r}_{R{e}_i}=Enc(rand{f}_{x_i}\left|\right|S{h}_{x_i},k_{ac}),i\in \left[m\right]\hfill \\ roo{t}_{Re}=MTgen(rand{f}_{x_1}\left|\right|S{h}_{x_1},\dots ,rand{f}_{x_m}\left|\right|S{h}_{x_m})\hfill \end{array}\right.$$

(2)

Algorithm 1 Re’s data processing

Input:  A data set X with $\left|X\right|=m$ Output:  $En{c}_{Re},roo{t}_{Re}$   1: for$i=1$ to m do   2:  $rand{f}_{x_i}\leftarrow F(K,x_i)$   3:  $S{h}_{x_i}\leftarrow 0$   4:  for $j=1$ to n do   5:   $F_j\leftarrow F(k_{0j},x_i)$   6:   $S{h}_{x_i}\oplus =F_j$   7:  end for   8:  $En{c}_{R{e}_i}\leftarrow Enc(PR{F}_{x_i}\left|\right|S{h}_{x_i},k_{ac})$   9: end for 10: $roo{t}_{Re}\leftarrow MTgen(PR{F}_{x_1}\left|\right|S{h}_{x_1},\dots ,PR{F}_{x_m}\left|\right|S{h}_{x_m})$ 11: $ciphe{r}_{Re}\leftarrow \left\{ciphe{r}_{R{e}_1},\dots ,ciphe{r}_{R{e}_m}\right\}$ 12: return$\left\{ciphe{r}_{Re},roo{t}_{Re}\right\}$

5.3. Data Submission

In this phase, the CS receives the ciphertext and verification information of pseudorandom function values and intersection sharing values $\left\{ciphe{r}_{Re},roo{t}_{Re}\right\}$ from Re.

Firstly, we introduce the validation of the pseudorandom function values and intersection sharing values. Assume that the CS decrypts $En{c}_{Re}$ to obtain $\left\{{\left(rand{f}_{x_1}\right|\left|S{h}_{x_1}\right)}^{\prime },\dots ,\right.\left.{\left(rand{f}_{x_m}\right|\left|S{h}_{x_m}\right)}^{\prime }\right\}$:

$$\left\{{\left(rand{f}_{x_i}\right|\left|S{h}_{x_i}\right)}^{\prime }\right\}\leftarrow Dec(ciphe{r}_{R{e}_i},k_{ac})(i\in \left[m\right]).$$

(3)

Then, the CS computes

$$roo{t}_{Re}^{{}^{\prime }}\leftarrow MTgen({\left(rand{f}_{x_1}\right|\left|S{h}_{x_1}\right)}^{\prime },\dots ,{\left(rand{f}_{x_m}\right|\left|S{h}_{x_m}\right)}^{\prime }).$$

(4)

If $roo{t}_{Re}=roo{t}_{Re}^{{}^{\prime }}$, the CS believes the verification passed and obtains $\left\{rand{f}_{x_1}\left|\right|S{h}_{x_1},\dots ,\right.\left.rand{f}_{x_m}\left|\right|S{h}_{x_m}\right\}$.

Then, on the input of the data set $(Y^{\left(u\right)},T^{\left(u\right)})\left(\right|Y^{\left(u\right)}|=|T^{\left(u\right)}|=m)$, $D{O}^{\left(u\right)}$ runs data processing to generate $\left\{E{S}^{\left(u\right)},S{h}^{\left(u\right)},E{R}^{\left(u\right)}\right\}$. The details are shown in Algorithm 2. We take a DO as an example and divide this stage into several steps as follows:

Algorithm 2 DO’s Data Processing

Input:  A data set $(Y^{\left(u\right)},T^{\left(u\right)})$ with $|Y^{\left(u\right)}|=|T^{\left(u\right)}|=m$ Output:  $E{S}^{\left(u\right)},S{h}^{\left(u\right)},E{R}^{\left(u\right)}$   1: for$i=1$ to m do   2:  $r_i^{\left(u\right)}\stackrel{}{\leftarrow }$ a random number   3:  $rand{f}_{y_i^{\left(u\right)}}\leftarrow F(K,y_i^{\left(u\right)})$   4:  $E{S}_{y_i^{\left(u\right)}}\leftarrow Enc(rand{f}_{y_i^{\left(u\right)}},t_i^{\left(u\right)}-r_i^{\left(u\right)})$   5:  $E{R}_{y_i^{\left(u\right)}}\leftarrow Enc(k_{0u},r_i^{\left(u\right)})$   6:  $S{h}_{y_i^{\left(u\right)}}\leftarrow 0$   7:  for $j=0$ to n, $j\ne u$ do   8:   $F_j\leftarrow F(k_{uj},y_i^{\left(u\right)})$   9:   $S{h}_{y_i^{\left(u\right)}}\oplus =F_j$ 10:  end for 11: end for 12: $E{S}^{\left(u\right)}\leftarrow \left\{E{S}_{y_1}^{\left(u\right)},\dots ,E{S}_{y_m}^{\left(u\right)}\right\}$ 13: $S{h}^{\left(u\right)}\leftarrow \left\{S{h}_{y_1}^{\left(u\right)},\dots ,S{h}_{y_m}^{\left(u\right)}\right\}$ 14: $E{R}^{\left(u\right)}\leftarrow \left\{E{S}_{y_1}^{\left(u\right)},\dots ,E{R}_{y_m}^{\left(u\right)}\right\}$ 15: return$\left\{E{S}^{\left(u\right)},S{h}^{\left(u\right)},E{R}^{\left(u\right)}\right\}$

(1)

Generate calculation value. For each datum $y_i$, the DO first computes the pseudorandom function value $rand{f}_{y_i}$ based on the group key K; namely, $rand{f}_{y_i}=F(K,y_i)$. Then, the DO chooses a random number $r_i$ for associated datum $t_i$ and encrypts the difference between $t_i$ and $r_i$ based on $rand{f}_{y_i}$ to generate the calculation value $E{S}_{y_i}$; namely, $E{S}_{y_i}=Enc(RP{F}_{y_i},t_i-r_i)$.

(2)

Generate intersection sharing value. For each datum $y_i$, the DO first computes the pseudorandom function value $F_j$ based on the symmetric key negotiated with the Re and other DOs $k_{uj}(j\in \left[n\right],j\ne u)$; namely, $F_j=F(k_{uj},y_i)$. Then, the DO XORs multiple $F_j$ according to the formula (5) to generate the intersection sharing value $S{h}_{y_i}$:

$$S{h}_{y_i}=F_0\oplus \cdots \oplus F_{u-1}\oplus F_{u+1}\cdots \oplus F_n$$

(5)

(3)

Generate calculation sharing value. For each datum $y_i$, the DO chooses a random number $r_i$ and generates calculation sharing value $E{S}_{y_i}$ based on the symmetric key $k_{0u}$ negotiated with the Re; namely, $E{R}_{y_i}=Enc(k_{0u},r_i)$.

Next, we introduce the CS to obtain the intersection sharing value. CS obtains the pseudorandom function value of $x_i$ by verifying the ciphertext and verification information sent by the Re. Each DO obtains the calculation value, the calculation sharing value, and the intersection sharing value through data processing. The CS and each DO obtain shared values, as shown in Algorithm 3. As a result, the CS obtains the shared value $S{h}_{CS}$. We take a DO as an example and divide this stage into several steps as follows:

Algorithm 3 Obtaining Shared Values

Input:  CS:$rand{f}_{x_i}$ DO:$rand{f}_{y_i},E{S}_{y_i}\left|\right|S{h}_{y_i}\left|\right|E{R}_{y_i}$ ($i\in \left[m\right]$) Output:  $S{h}_{CS}$   1: CS and DO execute:   2:  for $i=1$ to m do   3:   CS sends $rand{f}_{x_i}$ to $F_{OPRF}$   4:   CS receives $O{F}_{x_i}\leftarrow F(k_{OPRF},rand{f}_{x_i})$   5:  end for   6:  DO receives $k_{OPRF}$   7:  for $i=1$ to m do   8:   DO computes $O{F}_{y_i}\leftarrow F(k_{OPRF},rand{f}_{y_i})$   9:  end for 10: DO executes: 11:  for $i=1$ to m do 12:   $H_{D{O}_i}\leftarrow H\left(O{F}_{y_i}\right)$ 13:   $T{h}_{D{O}_i}\leftarrow O{F}_{y_i}\oplus S{h}_{y_i}$ 14:  end for 15:  $h_d\leftarrow {\left\{0,1\right\}}^d$ 16:  if $h_d\notin \left\{H_{D{O}_1},\dots ,H_{D{O}_m}\right\}$ then 17:   $T{h}_d\leftarrow$ a random number r 18:  end if 19:  $H\leftarrow \left\{H_{D{O}_1},\dots ,H_{D{O}_m},h_d\right\}$ 20:  $ciphe{r}_H\leftarrow Enc(H,k_{ab})$ 21:  $Th\leftarrow \left\{T{h}_{D{O}_1},\dots ,T{h}_{D{O}_m},T{h}_d\right\}$ 22:  sends hash table $T=\left\{ciphe{r}_H,Th\right\}$ to CS 23:  $ES\leftarrow \left\{E{S}_{y_1},\dots ,E{S}_{y_m}\right\}$ 24:  $ER\leftarrow \left\{E{S}_{y_1},\dots ,E{R}_{y_m}\right\}$ 25:  sends $\left\{ES,ER\right\}$ to CS 26: CS executes: 27:  $H\leftarrow Dec(ciphe{r}_H,k_{ab})$ 28:  for $i=1$ to m do 29:   $H_{C{S}_i}\leftarrow H\left(O{F}_{x_i}\right)$ 30:   $S{h}_{C{S}_i}\leftarrow T{h}_{C{S}_i}\oplus O{F}_{x_i}$ 31:  end for 32:  $S{h}_{CS}\leftarrow \left\{S{h}_{C{S}_1},\dots ,S{h}_{C{S}_m}\right\}$ 33:  return$\left\{S{h}_{CS}\right\}$

(1)

The CS and DO perform an oblivious pseudorandom function algorithm $F_{OPRF}$. First, the CS takes the pseudorandom function value $rand{f}_{x_i}$.Then, as the output of $F_{OPRF}$, the DO receives the key $k_{OPRF}$, and the CS receives the value $O{F}_{x_i}$ corresponding to $rand{f}_{x_i}$; namely, $O{F}_{x_i}=F(k_{OPRF},S{E}_{x_i})$. In particular, the CS can only obtain $O{F}_{x_i}$ corresponding to $rand{f}_{x_i}$, and cannot obtain the key $k_{OPRF}$.

(2)

The DO generates an oblivious pseudorandom function value. Based on the $k_{OPRF}$ output by $F_{OPRF}$ and the pseudorandom function value $rand{f}_{y_i}$, the DO generates the corresponding oblivious pseudorandom function value $O{F}_{y_i}$; namely, $O{F}_{y_i}=F(k_{OPRF},S{E}_{y_i})$.

(3)

The DO generates the hash table T. Firstly, the DO generates hash value $H_{D{O}_i}$ based on the oblivious pseudorandom function value $O{F}_{y_i}$; namely, $H_{D{O}_i}=H\left(O{F}_{y_i}\right)$. Then, $T{h}_{D{O}_i}$ is generated based on $O{F}_{y_i}$ and intersection sharing value $S{h}_{y_i}$; namely, $T{h}_{D{O}_i}=O{F}_{y_i}\oplus S{h}_{y_i}$. In addition, for the binary bit string $h_d$, but not in $\left\{H_{D{O}_1},\dots ,H_{D{O}_m}\right\}$, the DO selects the random number r as $h_d$ corresponding to $T{h}_d$. Finally, the DO encrypts H and generates $ciphe{r}_H$ based on the session key $k_{ab}$, where $H=\left\{H_{D{O}_1},\dots ,H_{D{O}_m},h_d\right\}$. The DO takes $ciphe{r}_H,Th$ as two columns to generate a hash table T and sends it to the CS.

(4)

The CS obtains the intersection sharing value. Firstly, the CS obtains the hash table T based on $ciphe{r}_H$ and $k_{ab}$. Then, based on the oblivious pseudorandom function value $O{F}_{x_i}$ and T, the CS obtains the intersection sharing value $S{h}_{C{S}_i}$; namely, $S{h}_{C{S}_i}=T{h}_{C{S}_i}\oplus O{F}_{x_i}$. According to the steps of the DO generation hash table T, it can be proven that $S{h}_{C{S}_i}$ satisfies the formula (6):

$$S{h}_{C{S}_i}=\left\{\begin{array}{cc}T{h}_{CS}\oplus O{F}_x=O{F}_y\oplus S{h}_y\oplus O{F}_x=S{h}_y,\hfill & x=y\hfill \\ T{h}_{CS}\oplus O{F}_x=r\oplus O{F}_x,\hfill & x\ne y.\hfill \end{array}\right.$$

(6)

At this point, the data submission phase ends. The CS obtains the data sharing value $\left\{S{h}_{CS}^{\left(u\right)},E{S}^{\left(u\right)},E{R}^{\left(u\right)}\right\}$ for each $D{O}^{\left(u\right)}$.

5.4. Outsourcing Response

In this phase, the CS first computes the private set intersection based on the intersection sharing values of the Re and DOs. Then, the private sum calculation result is computed based on the calculation value and calculation sharing value generated by the DO. The details of the CS computing the privacy sum are shown in the Algorithm 4. We take a DO as an example and divide this stage into several steps as follows:

(1)

Compute private set intersection. The CS, according to formula (7), executes XOR based on the intersection sharing value $Sh{x}_i$ generated by the Re and $S{h}_{C{S}_i}^{\left(u\right)}$, which is obtained by the interaction with each $D{O}^{\left(u\right)}$, and then generates $re{s}_{x_i}$. If $re{s}_{x_i}=0$, then the datum $x_i$ belong to the set intersection; namely, $x_i\in X\bigcap \left({\bigcap }_{u=1}^n{Y}^{\left(u\right)}\right)$:

$$re{s}_{x_i}=Sh{x}_i\oplus S{h}_{C{S}_i}^{\left(1\right)}\oplus \cdots \oplus S{h}_{C{S}_i}^{\left(n\right)}$$

(7)

(2)

Compute private intersection-sum. The CS decrypts the calculation value $E{S}_{x_i}$ based on pseudorandom function value $rand{f}_{x_i}$; namely, $D{S}_{x_i}=Dec(rand{f}_{x_i},E{S}_{x_i})$. Then, the CS sums multiple calculation values to obtain $sum$.

(3)

Generate the ciphertext of the private sum result. Based on the private intersection-sum result $sum$ and the session key $k_{ac}$ negotiated with the Re, the CS generates the ciphertext of the private sum result; namely, $ciphe{r}_{res}=Enc(sum,k_{ac})$. Then, the CS generates $E{R}_{Re}$ based on calculated sharing values $E{R}_{x_i}$ corresponding to the intersection data $x_i$ and sends $\left\{ciphe{r}_{res},E{R}_{Re}\right\}$ to the Re.

Algorithm 4 Private Sum Computation

Input:  $S{h}_{CS}^{\left(u\right)}$,$Sh{x}_i$ Output:  $ciphe{r}_{res}$   1: for$i=1$ to m do   2:  $sum\leftarrow 0$   3:  $E{R}_{Re}\leftarrow null$   4:  $re{s}_{x_i}\leftarrow Sh{x}_i$   5:  for $u=1$ to n do   6:   $re{s}_{x_i}\oplus =S{h}_{C{S}_i}^{\left(u\right)}$   7:  end for   8:  if $re{s}_{x_i}==0$ then   9:   $D{S}_{x_i}\leftarrow Dec(rand{f}_{x_i},E{S}_{x_i}^{\left(u\right)})$ 10:   $sum+=D{S}_{x_i}$ 11:  end if 12: end for 13: $ciphe{r}_{res}\leftarrow Enc(sum,k_{ac})$ 14: return$\left\{ciphe{r}_{res},E{R}_{Re}\right\}$

After receiving $\left\{ciphe{r}_{res},E{R}_{Re}\right\}$ from the CS, the Re first decrypts each $E{R}_{x_i}$ based on the group key K to obtain $r_i$ and add all $r_i$ named $su{m}_1$. Next, the Re decrypts $ciphe{r}_{res}$ based on the session key $k_{ac}$ to obtain $sum$ named $su{m}_0$. Finally, Re adds $su{m}_0$ and $su{m}_1$ to obtain the final result of privacy intersection-sum.

6. Security Analysis

In this section, we analyze the security of our proposed protocol from three points: the security of the Re’s data, the security of the DOs’ data, and the security of intersection-sum result.

6.1. Security of Re’s Data

SLMP-PIS guarantees the security of the Re’s data. In other words, no one except for the Re learns X.

In the outsourcing request phase, for each datum $x_i$, the Re generates $rand{f}_{x_i}$ and intersection sharing value $S{h}_{x_i}$. For $rand{f}_{x_i}$, Re executes pseudorandom function for $x_i$ based on the group key K, and obtains $rand{f}_{x_i}$ corresponding to $x_i$. For $S{h}_{x_i}$, Re first calculates $F_u$ based on the symmetric key $k_{0u}(i\in \left[n\right])$ negotiated with $D{O}^{\left(u\right)}$. Then, the Re performs XOR on the n pseudorandom function values to obtain the data sharing value, i.e., $S{h}_{x_i}=F_1\oplus \cdots \oplus F_n$. If the adversary ${\mathcal{A}}_1$ wants to learn $x_i$, they need to obtain key K and $k_{ou}$. However, due to the security of PRF, the probability of an adversary’s challenge being successful is negligible.

In the data submission phase, Re computes $ciphe{r}_{R{e}_i}=Enc(rand{f}_{x_i}\left|\right|S{h}_{x_i}\left|\right|r_i,k_{ac})$ based on the session key $k_{ac}$ negotiated between the Re and CS and sends it to the CS. Therefore, the adversary ${\mathcal{A}}_1$ can only obtain the ciphertext of the pseudorandom function value and intersection sharing value of the Re’s data. In the absence of $k_{ac}$, the confidentiality of symmetric encryption ensures that the probability that outsiders obtain $x_i$ is negligible.

To sum up, SLMP-PIS guarantees the security of the Re’s data based on the security of PRF and symmetric encryption.

6.2. Security of DOs’ Data

SLMP-PIS guarantees the security of the DOs’ data. On the one hand, it is difficult for the CS and Re to learn any of the DOs’ data, including datum Y and the related datum T. On the other hand, it is hard for each DO to learn the data of other DOs.

In the data submission phase, the CS first performs OPRF with the DO. The CS obtains $O{F}_{x_i}$ without $k_{OPRF}$ with negligible probability. The DO calculates $O{F}_{y_i}$ based on $k_{OPRF}$. Then, the DO generates a hash table based on $O{F}_{y_i}$ and $S{h}_{y_i}$. During this process, the DO calculates the hash value of $O{F}_{y_i}$ as the first column of the hash table, and the XOR value of $O{F}_{y_i}$ and $S{h}_{y_i}$ as the second column of the hash table. Finally, the CS obtains $S{h}_{y_i}$ or random numbers through the XOR operation based on the hash table. If the adversary ${\mathcal{A}}_2$ compromises CS’s ability to learn $y_i$, it needs to break the one-way hash function and the security of OPRF, and this probability is negligible.

In the initialization phase, each $D{O}^{\left(u\right)}$ negotiates the session key $k_{a{b}^{\left(u\right)}}$ with the CS based on the Diffie–Hellman key exchange protocol. $D{O}^{\left(u\right)}$ encrypts the first column of the hash table based on $k_{a{b}^{\left(u\right)}}$. If the adversary ${\mathcal{A}}_2$ would like to learn the data through the first column of hash table, the key $k_{a{b}^{\left(u\right)}}$ of the DO needs to be obtained. However, the probability is negligible. In addition, each $D{O}^{\left(u\right)}$ negotiates a symmetric key $k_{iu}(i\in [0,n],i\ne u)$ with Re and other DOs, and calculates the $S{h}_{y_i^{\left(u\right)}}$ based on $n-1$ symmetric keys. The possibility for any two DOs to obtain equal symmetric keys is negligible. Therefore, it is difficult for other DOs to learn the DO’s data through the second column of the hash table.

In summary, SLMP-PIS guarantees the security of the DOs’ data based on OPRF security, the one-way hash function, key security, and the discrete logarithm problem.

6.3. Security of Intersection-Sum Result

SLMP-PIS guarantees the security of the private intersection-sum result. In other words, no one except for the Re obtains the intersection-sum result.

In the outsourcing request phase, the Re generates a pseudorandom function value for each datum $x_i$. In the data submission phase, each DO generates a calculation value $E{S}_{x_i}$ and a calculation sharing value $E{R}_{x_i}$. After running the obtaining shared values algorithm, the CS computes the intersection of $X\bigcap \left({\bigcap }_{u=1}^n{Y}^{\left(u\right)}\right)$. Then, the CS computes the sharing value of intersection-sum based on $E{S}_{x_i}$, and sends the ciphertext to the Re. In the outsourcing response phase, the Re generates another sharing value. Therefore, the adversary ${\mathcal{A}}_3$ compromises the CS to learn the intersection-sum result with negligible probability due to the arithmetic secret sharing.

In conclusion, SLMP-PIS guarantees the security of the intersection-sum result based on arithmetic secret sharing and symmetric encryption.

7. Performance Analysis

In this section, we introduce the experimental settings and results of the SLMP-PIS.

7.1. Experimental Settings

We set the Re’s data set $\left\{x_i=i|i\in \left[m\right]\right\}$. We set the DO’s data set Y as formula (8) and associated values T as $\left\{t_i=i|i\in \left[m\right]\right\}$. We set the AES arithmetic to AES-256 and the hash algorithm to MD5 by default.

$$y_i^{\left(u\right)}=\left\{\begin{array}{cc}i,\hfill & 1\le i\le m/2\hfill \\ random-number,\hfill & m/2<i\le m.\hfill \end{array}\right.$$

(8)

In addition, we introduce the experimental arrangement. First, we study the computational cost in the outsourcing request phase, the data submission phase involving the DOs processing data and obtaining shared values, and the outsourcing response phase. Second, we also research the parameters and algorithms in our scheme. We study the effects of different AES algorithms and hash functions on the computational cost. Next, we compare the computational cost of our scheme in online and offline phases with different data sizes m. We set $m=2^9$ and $m=2^{11}$ as examples.

Finally, we compare our scheme with some related work, including Ion et al. [32], Lu et al. [31], and Kulshrestha et al. [35]. The comparison results are shown in

Table 2. Comparison with related work.

Schemes	Ion [32]	Lu [31]	Kulshrestha [35]	SLMP-PIS
Data privacy	√	√	√	√
Strictly PIS	√	×	×	√
Party offline	×	×	×	√
Data update	×	×	×	√
Symmetric cryptosystem	×	×	×	√

. “√” means satisfied, and “×” means dissatisfied. Ion et al. [32] proposed a strict two-party private intersection-sum protocol, Lu et al. [31] described a private intersection weighted sum protocol, and Kulshrestha et al. [35] proposed a non-strict private intersection-sum protocol to compute ${\sum }_{x\in I}T\left[x\right]$, where $I=X_0\bigcap \left({\bigcup }_{i=1}^{n-1}{X}_i\right)$ and T is associated with the values of X. Therefore, we compare our scheme with the computational cost of executing the model multiple times, as in Ion et al. [32], since they implement the same function.

The experiments are implemented on a PC (CPU, Intel(R) Core(TM) i5-8265U CPU @ 1.60 GHz 1.80 GHz; RAM, 8.00 G; OS, Windows 10) with centos7 virtual machines using python 3.7.4. The code is shown in github: https://github.com/mokx1874/SLMP-PIS.git, accessed on 19 January 2023.

7.2. Experimental Results

7.2.1. Computational Costs in Different Phases

At this stage, we evaluate the effect of data set size m and the number of DOs on the computational cost in the outsourcing request phase, the data submission phase involving the DO processing data and obtaining shared values, and the outsourcing response phase. The computational cost of the SLMP-PIS is shown in Figure 3. We select m from $2^8$ to $2^{12}$ and $\left|DOs\right|$ from 2 to 5.

In the outsourcing request phase, as shown in Figure 4, it is obvious that m and $\left|DOs\right|$ influence the computational cost. When setting $\left|DOs\right|=5$, the computational cost is 0.63 s ($m=2^8$) and 10.11 s ($m=2^{12}$). When setting $m=2^{10}$, the computational cost is 1.43 s ($\left|DOs\right|=2$) and 2.47 s ($\left|DOs\right|=5$). Therefore, the computational cost in the outsourcing request phase is positively correlated with m and $\left|DOs\right|$.

In the DOs’ data processing in the data submission phase, as shown in Figure 5, it is obvious that m and $\left|DOs\right|$ influence the computation cost. When setting $\left|DOs\right|=5$, the computational cost is 0.71 s ($m=2^8$) and 11.35 s ($m=2^{12}$). When setting $m=2^{10}$, the computational cost is 1.76 s ($\left|DOs\right|=2$) and 2.87 s ($\left|DOs\right|=5$). Therefore, the computational cost of the DOs’ data processing is a positive correlation with m and $\left|DOs\right|$. As shown in Figure 6, we evaluate the computational overhead of this stage under different m through multiple experiments. The computational costs are 0.79 s ($m=2^8$), 1.37 s ($m=2^9$), 2.35 s ($m=2^{10}$), 3.51 s ($m=2^{11}$), and 7.42 s ($m=2^{12}$). Therefore, the computational cost of obtaining shared values is a positive correlation with m.

In the outsourcing response phase, as shown in Figure 7, it is obvious that m and $\left|DOs\right|$ influence the computational cost. When setting $\left|DOs\right|=5$, the computational cost is 0.56 s ($m=2^8$) and 8.45 s ($m=2^{12}$). When setting $m=2^{10}$, the computational cost is 0.95 s ($\left|DOs\right|=2$) and 2.03 s ($\left|DOs\right|=5$). Therefore, the computational cost in the outsourcing response phase is positively correlated with m and $\left|DOs\right|$.

As a result, the computational cost in different phases has a positive correlation with m and the number of DOs, and it is acceptable.

7.2.2. The Effect of $AES$ and $Hash$

We set $m=2^{10}$ in Figure 8 and Figure 9. The results show that the impact of hash functions on computational cost is not obvious. When using MD5, the computational cost is 11.75 s, and it is 11.79 s using SHA-1, 11.83 s using SHA-256, and 11.87 s using SHA-512. The difference is negligible. For AES, we notice that AES algorithms have little impact on computation cost. When using AES-128, the computational cost is 11.72 s, 11.74 s using AES-192, and 11.81 s in using AES-256. The difference is negligible.

As a result, the impact of different AES algorithms and hash functions on the computational cost is negligible.

7.2.3. Online and Offline

The current PIS basically needs to be executed online, which places more stringent requirements on the participants. Our solution enables parties to be offline after submitting their data. As shown in Figure 10, we compare the calculation cost of online and offline processes with different m. When setting $m=2^9$ and $\left|DOs\right|=5$, the computational cost is 3.21 s in online and 4.35 s in offline processes. When setting $m=2^{11}$ and $\left|DOs\right|=5$, the computational cost is 10.81 s for online and 23.17 s for offline.

As a result, we find that the difference between the computational cost of offline processes and the computational cost of online processes gradually increases with the increase in m, and the computational cost of online processes is smaller than that of offline processes.

7.2.4. Comparison with Related Work

As shown in Figure 11, we compare the computational cost of our proposed scheme and Ion’s [32] with different m. When setting $m=2^9$ and $\left|DOs\right|=2$, the computational cost is 3.80 s in our scheme and 3.99 s in Ion’s. When setting $m=2^9$ and $\left|DOs\right|=5$, the computational cost is 7.56 s for our scheme and 11.29 s for Ion’s. When setting $m=2^{11}$ and $\left|DOs\right|=2$, the computational cost is 18.98 s for our scheme and 19.06 s for Ion’s. When setting $m=2^{11}$ and $\left|DOs\right|=5$, the computational cost is 33.97 s for our scheme and 44.11 s for Ion’s.

As a result, we find that the larger the number of DOs, the more efficient our scheme is.

8. Conclusions

In this paper, we demonstrate a secure and lightweight multi-party private intersection-sum scheme that computes the sum of associated values based on the private set intersection. On the one hand, the scheme achieves an outsourced multi-party private intersection-sum. On the other hand, our scheme allows participants to be offline and still update data. Specifically, we protect the privacy of outsourced data based on zero sharing and an oblivious pseudorandom function, and consider the privacy of associated values based on arithmetic sharing and symmetric encryption. We introduce the cloud computing technique into our scheme, which allows data owners to stay offline after outsourcing their processed data. Finally, the security analysis shows that the protocol is secure. The performance results illustrate the efficiency and feasibility of our scheme. Specifically, when the number of participants is five, the efficiency can be increased by 22.98%. As part of our future work, we will continue to study how to design a PIS protocol with malicious security.