## 3 Preliminaries
### Mpc  
In this study, MPC based on secret sharing is used. Secret sharing refers to constructing secret shares for each private input of the participants, such that each participant holds parts of secret shares, which contain no meaningful information regarding the original private inputs separately, but, together, can reconstruct the original private inputs [33]. For instance, to create secret shares for one-bit private input \(x\in\{0,\ 1\}\), one arbitrary bit is chosen, \(x_{2}\in\{0,\ 1\}\), then \(x_{1}=x\oplus x_{2}\) (\(\oplus\) denotes the \"xor\" binary operation, e.g., \(0\oplus 0=0\), \(0\oplus 1=1\), \(1\oplus 0=1\), and \(1\oplus 1=0\)) and \(x_{2}\) form valid secret shares of \(x\), as no information of \(x\) is inferred with either \(x_{1}\) or \(x_{2}\) alone, but together, they can reconstruct \(x\) because \(x=x_{1}\oplus x_{2}\).  
Computing the outputs of a function \(F\) with private inputs using secret sharing-based MPC consists of the following steps: (i) represent \(F\) as a Boolean circuit \(C\); (ii) generate secret shares of the private inputs of \(C\) and disseminate them to all players; (iii) evaluate \(C\) gate by gate (\"gate\" here refers to the Boolean gate), such that secret sharing is valid for each wire (\"wires\" connect the Boolean gates and transmit the outputs of upstream gates to the downstream gates as inputs); and (iv) reconstruct the function outputs on the output wires. For example, suppose two vehicles want to report to an off-ramp RSU regarding how many vehicles in total are taking the off-ramp without revealing their trips to each other using MPC. They can use a binary adder as shown in Figure 4. The Boolean circuit on the left side of Figure 4 takes two bits \(x\) and \(y\) as private indicators of whether two vehicles will take the off-ramp. The circuit consists of an \"and\" gate and an \"xor\" gate. The output consists of two bits \(p\) and \(z\), which can form a binary representation of the total number of vehicles taking the off-ramp. Both \(x\) and \(y\) can be secret-shared, as Figure 4 shows such that vehicles \(1\) and \(2\) hold \((x_{1},\ y_{1})\) and \((x_{2},\ y_{2})\), respectively. Here, we illustrate how secret sharing remains valid on the output wire of the \"xor\" gate. Vehicle \(1\) applies the \"xor\" operation on \(x_{1}\) and \(y_{1}\) to get \(z_{1}=x_{1}\oplus y_{1}\) and, similarly, vehicle \(2\) obtains\(z_{2}=x_{2}\oplus y_{2}\). Since \(z_{1}\oplus z_{2}=(x_{1}\oplus y_{1})\oplus(x_{2}\oplus y_{2})=(x_{1}\oplus x_{2}) \oplus(y_{1}\oplus y_{2})=x\oplus y=z\); that is, we can reconstruct \(z\) with \(z_{1}\) and \(z_{2}\) while inferring no information about \(z\) solely with \(z_{1}\) or \(z_{2}\). Therefore, secret sharing holds for the \"xor\" gate. And secret sharing for the \"and\" gate also exists [34], though it is not as intuitive as that for the \"xor\" gate. Therefore, vehicles 1 and 2 can send all the secret shares (\(p_{1},\ z_{1}\)) and (\(p_{2},\ z_{2}\)), respectively, to the RSU to compute the total number of vehicles taking the off-ramp.  
For more complicated \(F\), as in our proposed schemes, there are MPC compilers that can generate the corresponding circuit \(C\), which is how we generate the MPC protocols in our numerical studies.