Efficient and Privacy-Preserving Binary Dot Product via Multi-Party Computation Thanks: This work was supported in parts by the Army Research Lab (W911NF2420172), Army Research Office (W911NF2410049), the National Science Foundation (CCF-1942878, CNS-2148182, CNS-2112471). Fatemeh Jafarian Dehkordi, Elahe Vedadi, Alireza Feizbakhsh, Yasaman Keshtkarjahromi, Hulya Seferoglufjafar3@uic.edu, evedad2@uic.edu, afeizb2@uic.edu, yasaman.keshtkarjahromi@seagate.com, hulya@uic.edu Abstract Striking a balance between protecting data privacy and enabling collaborative computation is a critical challenge for distributed machine learning. While privacy-preserving techniques for federated learning have been extensively developed, methods for scenarios involving bitwise operations, such as tree-based vertical federated learning (VFL), are still underexplored. Traditional mechanisms, including Shamir’s secret sharing and multi-party computation (MPC), are not optimized for bitwise operations over binary data, particularly in settings where each participant holds a different part of the binary vector. This paper addresses the limitations of existing methods by proposing a novel binary multi-party computation (BiMPC) framework. The BiMPC mechanism facilitates privacy-preserving bitwise operations, with a particular focus on dot product computations of binary vectors, ensuring the privacy of each individual bit. The core of BiMPC is a novel approach called Dot Product via Modular Addition (DoMA), which uses regular and modular additions for efficient binary dot product calculation. To ensure privacy, BiMPC uses random masking in a higher field for linear computations and a three-party oblivious transfer ( triOT ) protocol for non-linear binary operations. The privacy guarantees of the BiMPC framework are rigorously analyzed, demonstrating its efficiency and scalability in distributed settings. I Introduction In today’s era of big data analytics and distributed machine learning, a critical challenge emerges: how to strike the right balance between protecting data privacy and harnessing distributed data for collaborative computation. The variety of data types and analysis techniques necessitates a differentiated approach to privacy. Privacy-preserving mechanisms are well-established for classical federated learning, which typically relies on floating-point operations. Notably, Shamir’s secret sharing [ 1 ] and multi-party computation (MPC) protocols based on Shamir’s approach have been widely explored in the literature to offer information-theoretic privacy guarantees for federated learning [ 2 , 3 , 4 , 5 , 6 ] . Additionally, techniques like classical homomorphic encryption [ 7 , 8 , 9 , 10 , 11 ] and differential privacy [ 12 , 13 , 14 , 15 , 16 ] have been widely used. However, privacy-preserving methods remain relatively underdeveloped for computing mechanisms that rely on bitwise operations such as tree-based vertical federated learning (VFL) [ 17 ] . Some privacy-preserving VFL approaches [ 18 , 19 , 20 , 21 , 22 , 23 ] have employed secure hardware, trusted third parties, or cryptographic MPC techniques. However, to the best of our knowledge, no efficient, information-theoretic MPC approach, specifically tailored to the bitwise operations common in VFL, has been proposed. This gap largely stems from the fact that standard oblivious transfer protocols are inherently cryptographic and do not offer information-theoretic security. In this paper, we focus on bitwise operations of multiple binary vectors, where each vector is held by a different party, and we aim to ensure the privacy of every individual element in all the vectors. While generic protocols like GMW [ 24 ] can provide computational security for VFL, they are often prohibitively expensive. Similarly, applying Shamir’s secret sharing to single-bit data is highly impractical, resulting in significant communication and computation overhead [ 25 ] . Moreover, our problem demands the privacy of each individual bit, meaning that we cannot treat each binary vector of length n as an n -bit number and apply Shamir’s scheme over a large field. Therefore, there is a need for a tailored secret sharing method that can preserve the privacy of each individual bit in binary secrets. To address this problem, we propose a binary multi-party computing (BiMPC) mechanism. BiMPC is a low complexity multi-party algorithm for privacy-preserving bitwise operations, with a particular focus on dot product computations of binary vectors, ensuring the privacy of each individual bit. BiMPC relies on a novel approach that we name Dot Product via Modular Addition (DoMA) to calculate binary matrix multiplication, which makes BiMPC efficient and scalable. DoMA calculates the dot product of binary vectors via regular and modular additions as further explained in Section IV-A . BiMPC is comprised of secure multi-party addition and XOR calculation for linear (regular addition) and non-linear (modular addition) operations of DoMA, respectively. BiMPC uses random masking for secure addition, and XOR operation is performed using a three-party oblivious transfer ( triOT ) protocol as further detailed in Section V . The privacy guarantees of BiMPC are provided in Section V . II Related Work The most widely known secret sharing scheme with information-theoretic security is Shamir’s algorithm [ 1 ] . Although Shamir’s scheme is efficient for sufficiently large finite fields, it is not directly applicable to binary secrets, where field size constraints become a limitation. This has motivated several adaptations for small-field secure computation. For example, Chen et al. [ 26 ] propose a generalization using algebraic curves. Unlike Shamir’s scheme, which requires the field size to exceed the number of parties, their approach leverages curves of higher genus to support more participants over smaller fields while still preserving strong multiplication properties. Nevertheless, the number of participants is still fundamentally constrained by the field size, so despite this refinement, the approach remains limited and does not scale for very small fields. To support MPC over binary vectors, secret sharing schemes based on error-correcting codes have been developed. Notably, Massey [ 27 , 28 ] introduced a scheme in which a secret is embedded in a random codeword from a binary linear code, while reconstruction relies on the dual code. Building on this, Chen et al. [ 29 ] extended Massey’s approach to support multiplication, making it more suitable for MPC. While this construction is efficient for computation, its security is limited: the access structure (i.e., the subsets of participants who can reconstruct the secret) is fixed by the codebook and does not support arbitrary authorized sets. Visual cryptography explores the sharing of binary secrets. A foundational method was introduced by Naor and Shamir [ 30 ] , in which the ”transparencies” of a secret binary image are distributed among n participants. The image can be revealed only when at least k participants combine their shares, forming a deterministic (k,n) scheme. However, this approach suffers from pixel expansion, significantly increasing storage requirements for each party. To address this, Wang et al. [ 31 ] proposed a deterministic scheme that avoids pixel expansion. It uses randomly generated Boolean matrices to produce shares, and the secret image is fully recovered by XORing all the shares. The same work also introduced a probabilistic scheme—similar to random grid methods such as [ 32 ] —in which dark pixels are accurately reconstructed, but bright pixels may occasionally appear as dark. This reconstruction relies partially on human visual perception and thus is unsuitable for scenarios requiring precise recovery. Furthermore, while these methods reduce storage overhead, they lack flexibility in the number of participants required for reconstruction. Deshmukh et al. [ 33 ] proposed a related approach using a full binary tree structure. The secret is divided into 2^{h} shares, where h is the height of the tree, and recovery requires XORing of all of them. Although efficient in some respects, this scheme also demands the participation of all shareholders, limiting its practicality in flexible threshold scenarios. Our proposed method addresses these limitations as it allows privacy-preserving bitwise operations efficiently. III System Model Notations. The set of real numbers, natural numbers, and integers are denoted by \mathbb{R} , \mathbb{N} , and \mathbb{Z} , respectively. The set of numbers from a finite field with q elements is shown by \mathbb{F}_{q} . We assume that \Omega_{u}^{v} refers to the set of integers between u and v , i.e., \Omega_{u}^{v}=\{u,\ldots,v\} , where u\leq v . Matrices and vectors are represented by \mathbf{A} and \mathbf{a} , respectively, i.e., for \mathbf{A}\in\mathbb{F}_{q}^{n\times d} and \mathbf{a}\in\mathbb{F}_{q}^{n\times 1} we have \displaystyle\mathbf{A}=\left[{\begin{array}[]{ccc}a_{1,1}&\ldots&a_{1,d}\\ \vdots&\ddots&\vdots\\ a_{n,1}&\ldots&a_{n,d}\end{array}}\right], for a_{i,j}\in\mathbb{F}_{q} , where i\in\Omega_{1}^{n} , j\in\Omega_{1}^{d} , and \displaystyle\mathbf{a}^{T}=(a_{1},a_{2},\dots,a_{n}), (4) for a_{i}\in\mathbb{F}_{q} . The logical “AND” function is shown by the \land symbol, and the “dot product” is shown by the \odot symbol. Moreover, concatenation of two vectors \mathbf{a} and \mathbf{b} is represented by [\mathbf{a}:\mathbf{b}] , and \overline{a} denotes bitwise complement: \overline{a}=1-a for a\in\{0,1\} . Problem Statement. We consider a federated setup with N clients (data owners) and a master device. The clients have data as binary vectors, e.g., client W_{u} holds binary vector \mathbf{a}_{u} . Clients want the master to calculate the dot product of their binary vectors without revealing the content and length of their vectors, neither to the master nor to any other clients. In other words, the master will learn y=\mathbf{a}_{1}\odot\mathbf{a}_{2}\odot\ldots\mathbf{a}_{N} without violating the privacy requirements of the clients. Attack Model. We consider a semi-honest system where all devices follow the defined protocols but are curious about each other’s data. We note that the master is a non-colluding device, and no subset of clients colludes as they have no incentive, so no collusion occurs. Privacy Requirements. Privacy requirements from the perspective of each client and the master device are defined as follows. • Client perspective: Each client should not learn anything about the private data of other clients from the perspective of information-theoretic security. • Master perspective: The master should not learn anything more than the final dot product. The formal definition of privacy requirements is provided in Section V . IV Building Blocks of BiMPC Algorithm In this section, we introduce the building blocks of our proposed BiMPC algorithm, which are (i) Dot Product via Modular Addition (DoMA) and (ii) Three-Party Oblivious Transfer ( triOT ). IV-A Dot Product via Modular Addition (DoMA) Let us consider our proposed system model, consisting of N clients and a master device. Our purpose is to compute the dot product of binary vectors owned by clients. Theorem 1 Consider \mathbf{a}_{1},\;\mathbf{a}_{2},\dots,\;\mathbf{a}_{l} as l vectors that are chosen from \mathbb{F}^{1\times n}_{2} . The AND function of these l vectors can be calculated as the following \displaystyle\mathbf{d} \displaystyle=\mathbf{a}_{1}\land\mathbf{a}_{2}\land\dots\land\mathbf{a}_{l} \displaystyle=\frac{1}{l}\bigg((\mathbf{a}_{1}+\dots+\mathbf{a}_{l})-\Big((\mathbf{a}_{1}+\dots+\mathbf{a}_{l})\;\text{mod}\;l\Big)\bigg). (5) Proof: Let us define \mathbf{d}\in\mathbb{F}^{1\times n}_{2} , \mathbf{s}\in\mathbb{F}^{1\times n}_{l+1} , and \mathbf{m}\in\mathbb{F}^{1\times n}_{l} as the following: \displaystyle\mathbf{d}:=\mathbf{a}_{1}\land\mathbf{a}_{2}\land\dots\land\mathbf{a}_{l}=(d_{1},d_{2},\dots,d_{n}), (6) \displaystyle\mathbf{s}:=\mathbf{a}_{1}+\dots+\mathbf{a}_{l}=(s_{1},s_{2},\dots,s_{n}), (7) \displaystyle\mathbf{m}:=(\mathbf{a}_{1}+\dots+\mathbf{a}_{l})\;\text{mod}\;l=(m_{1},m_{2},\dots,m_{n}), (8) where d_{i}\in\{0,1\} , s_{i}\in\Omega_{0}^{l} , and m_{i}\in\Omega_{0}^{l-1} , for i\in\Omega_{1}^{n} . From the definition of the AND function, we know that d_{i}=1 if and only if the i^{th} element of all of the \mathbf{a}_{1},\dots,\mathbf{a}_{l} vectors is equal to 1 ; otherwise, d_{i}=0 . Thus, we have \displaystyle d_{i}=\begin{cases}1&\text{if~}s_{i}=l\\ 0&\text{if~}0\leq s_{i}\leq l-1,\end{cases} (9) and \displaystyle d_{i}=\begin{cases}1&\text{if~}m_{i}=0\\ 0&0\leq m_{i}=s_{i}\leq l-1\end{cases} (10) Therefore, for i\in\Omega_{1}^{n} , if the i^{th} element of all of the \mathbf{a}_{1},\dots,\mathbf{a}_{l} vectors is equal to 1 , d_{i}=\frac{1}{l}(s_{i}-m_{i})=1 , otherwise d_{i}=s_{i}-m_{i}=0 , and it concludes the proof. \Box Corollary 2 Consider \mathbf{a}=(a_{1},a_{2},\dots,a_{n}) and \mathbf{b}=(b_{1},b_{2},\dots,b_{n}) as two binary vectors in \mathbb{F}^{1\times n}_{2} , where a_{i},\;b_{j}\in\{0,1\} for i,j\in\Omega_{1}^{n} . The dot product of these two vectors can be calculated as the following: \displaystyle y=\mathbf{a}\odot\mathbf{b}=\sum_{i=1}^{n}\frac{1}{2}\bigg((a_{i}+b_{i})-\Big((a_{i}+b_{i})\;\text{mod}\;2\Big)\bigg). (11) Proof: The proof can be directly derived from Theorem 1 and the definition of dot product. \Box The key advantage of DoMA is its ability to reduce dot product operations to regular and modular additions, significantly lowering communication, computation, and storage costs when applied to binary dot products in MPC. IV-B Three-Party Oblivious Transfer We use a three-party oblivious transfer ( triOT ) primitive introduced in our prior work [ 34 ] , as a core building block. triOT is inspired by PROXY-OT introduced in [ 35 ] providing information-theoretic privacy. In our three-party protocol shown in Fig. 1 , the three parties are the selector, sender, and receiver. The selector has a one-bit input m^{\prime} , and the sender has the input keys \beta_{0} and \beta_{1} . Furthermore, the receiver and the selector generate a random sample k^{m} using a pseudorandom generator with the same seed, and the receiver and the sender generate random samples \alpha_{0} and \alpha_{1} similarly. Here, m^{\prime},k^{m}\in\{0,1\} and \alpha_{j},\beta_{j}\in\mathbb{F}_{q} for j=0,1 . The goal is for the receiver to obtain \beta_{m^{\prime}} without learning any other information. First, the selector sends its masked input m^{\prime\prime}=m^{\prime}\oplus k^{m} to the sender. The sender then forwards the masked labels to the selector. The selector sends \gamma_{m^{\prime}}=\beta_{m^{\prime}}+\alpha_{k^{m}} to the receiver. The receiver can unmask the received key to obtain \beta_{m^{\prime}} . The privacy proof of the triOT protocol is provided in Appendix A of [ 34 ] . Receiver \alpha_{0},\alpha_{1},k^{m} Sender \beta_{0},\beta_{1},\alpha_{0},\alpha_{1} Selector m^{\prime},k^{m} m^{\prime\prime}=m^{\prime}\oplus k^{m} \gamma_{0}=\beta_{0}+\alpha_{m^{\prime\prime}} \gamma_{1}=\beta_{1}+\alpha_{1-m^{\prime\prime}} \gamma_{m^{\prime}}=\beta_{m^{\prime}}+\alpha_{k^{m}} Fig. 1: triOT protocol. V Binary Multi-Party Computation (BiMPC) In the previous section, we explained the foundational components of the BiMPC algorithm. This section explores their integration within an MPC framework, offering privacy proofs for operations conducted on binary secrets. For clarity, we first describe BiMPC for N=2 and then extend it to the general case N>2 . V-A BiMPC Algorithm for N=2 Clients In this system configuration, client W_{1} holds a binary input vector \mathbf{a}\in\mathbb{F}_{2}^{1\times n} , client W_{2} holds a binary input vector \mathbf{b}\in\mathbb{F}_{2}^{1\times n} , and a master device computes the dot product y=\mathbf{a}\odot\mathbf{b} in a privacy preserving manner. 1 1 1 While we articulate our algorithm for computing the dot product of two binary vectors, it can be extended to calculate the multiplication of any two binary matrices. This generalization holds as each matrix multiplication can be decomposed into dot products between the rows of the first matrix and the columns of the second matrix. To reduce the complexity of computation, communication, and storage, we employ the DoMA algorithm to calculate the dot product. Beginning with the definition of the dot product of two vectors, we first compute \mathbf{d}=\mathbf{a}\land\mathbf{b} and then derive the final result as y=\mathbf{a}\odot\mathbf{b}=\sum_{i=1}^{n}\mathbf{d}[i] . The DoMA algorithm provides the following expression for \mathbf{d} as \displaystyle\mathbf{d}=\mathbf{a}\land\mathbf{b}=\frac{1}{2}\bigg((\mathbf{a}+\mathbf{b})-\Big((\mathbf{a}+\mathbf{b})\;\text{mod}\;2\Big)\bigg), (12) which holds component-wise for binary vectors. Let \mathbf{s}:=(\mathbf{a}+\mathbf{b})\bmod q and \mathbf{m}:=\mathbf{a}\oplus\mathbf{b} . Therefore, the dot product can be written as \displaystyle y=\mathbf{a}\odot\mathbf{b}=\frac{1}{2}\sum_{i=0}^{n-1}\Bigl(\mathbf{s}[i]-\mathbf{m}[i]\Bigr). (13) This reduces the task to two sub-problems: (i) secure addition of shares (to obtain \sum_{i}\mathbf{s}[i] ) and (ii) secure XOR computation (to obtain \sum_{i}\mathbf{m}[i] ). To ensure the correctness of the final calculation, we carry out all operations (except XOR operations) in a prime field \mathbb{F}_{q} with q>2n , so that \bigl(2^{-1}\bmod q\bigr) exists and the reconstructed field element equals the integer dot product. 2 2 2 Noting that the calculation is correct, since \mathbf{a}[i],\mathbf{b}[i]\in\{0,1\} and q>2n , we have \mathbf{s}[i]\in\{0,1,2\} and \sum_{i}\mathbf{s}[i]2 Clients The BiMPC framework generalizes from the two-client case to accommodate an arbitrary number of clients, N>2 , through an iterative application of the core protocol. In this setting, each of the N clients holds a binary vector \mathbf{a}_{u} , and the objective is for the master to securely compute the final dot product y=\mathbf{a}_{1}\odot\mathbf{a}_{2}\odot\ldots\odot\mathbf{a}_{N} . The computation unfolds sequentially. Initially, the protocol is executed on the first two vectors, \mathbf{a}_{1} and \mathbf{a}_{2} , to compute their logical AND. The master receives the output of this step only in a securely masked form, which prevents it from learning the intermediate result. This masked value then serves as the first operand in the next iteration, where its logical AND is computed with the third vector, \mathbf{a}_{3} . This procedure is repeated for all remaining vectors up to \mathbf{a}_{N} . While the secure summation component of the protocol remains unchanged throughout this process, the secure XOR computation requires a minor adaptation. Specifically, the roles within the triOT protocol are reassigned to account for the master’s state. The master, now holding the masked intermediate result from the previous step, takes on the role of the sender in the triOT protocol. This is a key departure from the two-client case, where a client with a plaintext vector would act as a sender. This iterative design ensures that the master learns nothing more than the final dot product. The specifics of how the parties interact in this N -client setting are provided in the extended version of this paper. V-C Privacy Analysis The formal privacy requirements for the BiMPC algorithm from the perspective of each client and the master device are defined as the following: Client perspective: Each client should not learn anything about the private data of the other clients from the perspective of information-theoretic security. For each client W_{u} : \displaystyle\tilde{H}\big(\mathbf{a},\mathbf{b}|\text{view}_{W_{u}}\big) \displaystyle=\tilde{H}\big(\mathbf{a},\mathbf{b}\big), (27) where \tilde{H} denotes the Shannon entropy and view {}_{W_{u}} denotes the view of client W_{u} from the messages it receives from other parties. Master perspective : The master should not learn anything more than the final result y=\mathbf{a}\odot\mathbf{b} , i.e., \displaystyle\tilde{H}\big(\mathbf{a},\mathbf{b}|y,\text{view}_{M}\big)=\tilde{H}\big(\mathbf{a},\mathbf{b}|y\big), (28) where view M denotes the view of the master from the messages it receives from the clients. Theorem 3 Our proposed BiMPC algorithm satisfies privacy requirements from the perspective of both the clients and the master, presented in Equations ( 27 ) and ( 28 ). Proof: The proof of this theorem directly follows from the secrecy of random masking and triOT . VI Conclusion This paper introduced the Binary Multi-Party Computation (BiMPC) framework, addressing the privacy-preserving challenges in distributed machine learning involving binary data. BiMPC enables efficient and secure dot product computations on binary vectors, leveraging the novel Dot Product via Modular Addition (DoMA) approach. BiMPC ensures private computation on binary vectors by random masking and triOT protocol. The proposed solution is scalable and provides strong privacy guarantees for distributed machine learning methods that rely on bitwise operations, such as tree-based VFL applications.