Introduction
We are delighted to introduce our group project: Beaver Multiplication Triples in Oblivious Transfer (OT). This project has been completed by A S M Nazimuddoullah and Fahim Uddin
Very recently, the Bipartisan Senate AI Working Group pronounced substantially $32 billion per year being requisite [1] for AI safety research which pivots on privacy. A Cisco study[2] states that 1 in 4 organizations has already prohibited the use of Generative AI, and about 40 percent have experienced breaches of AI privacy already[3]. These incidents further support the need to mitigate the risk of data and model insecurity in AI.
Some of the private-enhancing technologies include but are not limited to differential privacy, federated learning, Zero-knowledge Machine Learning, Fully Homomorphic Encryption Machine Learning, Trusted execution environments, and finally, secure multiparty computation (MPC [4]). In this project, with both theoretical insight and mathematical examples, we will show how MPC can be utilized to build robust, secure, and scalable Privacy Preserving solutions while navigating the complex regulatory landscapes of safety and privacy, specially in pre-processing phase of establishing communication.
Beaver Triples in MPC
Secure multi-party computation (MPC) is a cryptographic technique that enables several parties to perform a calculation on their private inputs without revealing these inputs to each other. The key word here is that the computation should be divided into steps; each party executes a portion of the computation [4].
The computation generally consists of the following steps
1. Function Agreement: The parties agree on a function f to compute, represented as in the figure 1: f(x1, x2,., xn).
2. Input Sharing: Each party provides its private input (as depicted in the figure 1 with x1, x2, x3, x4, x5), but they are kept private to themselves.
3. Protocol Execution: Using some specially constructed protocol, the parties interact in such a way as to compute the output. In the process, this interaction has to ensure that no party learns anything whatsoever over what the output y=f(x1,x2,.,xn) reveals.
4. Computation of Output: Finally, the output, y is computed and revealed to all parties.
Two basic properties that any MPC protocol should support are privacy and correctness. For stronger security, the protocols also need to guarantee independence of inputs, guaranteed output delivery, and fairness to all parties [4].
In our project although we will compute multiplication values using precomputed beaver triples to establish a connection between parties as multiplication computation is costly during online/training phase rather than pre-processed phase, we will review how to perform private data mining Inference(pre-processed) and training in a privacy-preserving manner using MPC based on secret-sharing. The main idea is that data and model are shared and computations occur on shares, not raw data (although for simplified computations we will do in this project).
In a two-party secret sharing scheme, the parties can use, for the computation of multiplications (Figure 2) in inference, a secure protocol based on Beaver triples[5]. Both parties compute shares x1,x2,y1,y2 and the data provider gets x1,y1, and the model provider gets x2,y2. Now a Beaver triple(a,b,c) is generated c=ab using oblivious transfer[6] or homomorphic encryption[7]. Now the data provider computes ϵ1=x1-a and δ1=y1-b and the model provider computes ϵ2=x2-a and δ2=y2-b. They communicate these numbers and reconstruct ϵ=ϵ1+ϵ2 and δ=δ1+δ2. Then the data provider can compute r1=c+ϵ·b+δ·a+δ·ϵ and the model provider can compute r2=c+ϵ·b+δ·a+δ·ϵ.
For training phase in the case of a 2-party protocol (Figure3), for each private value x, the data provider must split it into shares x1,x2 and it gives x2 to the other data provider. Similarly as in the inference case, a Beaver triple is computed and shared between each data provider. In general, for n data providers, each input is partitioned into n shares.
Conclusion
Beaver triples are generated during the pre-processing phase of OT or any other scheme of MPC for efficiency and performance in secure multi-party computations. The overall communication costive in the online phase due to the precomputation of triples is drastically reduced, whereby the multiplication operations turn out faster; while most of the operations during the online phase are lightweight additions and subtractions that enhance speed in computation. Similarly, some pre-processing might be done in parallel. Hence, the resources used and, therefore, the cost will be remunerated over multiple computations. Preprocessing is independent of the actual inputs; hence, the precomputed triples are flexible, which can then be reused under different computations.
Happy learning
Please have a look at our teaching aide, Worksheet 6 Practice and discussion questions in below.
Teaching Aide: (Due to the limitation of this blog posting please follow the following link)
Worksheet 6: (Due to the limitation of this blog posting please follow the following link)
https://drive.google.com/file/d/14Dmnm5B9xXb1pCdTzEC1hEq5mTmeDwfG/view?usp=drive_link
Discussion Questions:
Q1. What is a Beaver Triple in multi-party computation?
Q2. In secure MPC, what is the difference between random share (recall the class lecture) and Beaver triples?
Q3. How can you prove the correctness of Beaver Triples ?
References
- https://www.mayerbrown.com/en/insights/publications/2024/05/senate-ai-working-group-releases-roadmap-for-artificial-intelligence-policy
- https://www.cisco.com/c/dam/en_us/about/doing_business/trust-center/docs/cisco-privacy-benchmark-study-2024.pdf
- https://edgedelta.com/company/blog/data-security-statistics
- https://eprint.iacr.org/2020/300.pdf
- https://link-springer-com.ezproxy.lib.ucalgary.ca/chapter/10.1007/3-540-46766-1_34
- https://en.wikipedia.org/wiki/Oblivious_transfer
- https://en.wikipedia.org/wiki/Homomorphic_encryption
- https://blog.bagel.net/p/with-great-data-comes-great-responsibility
Cover Image: https://miro.medium.com/v2/resize:fit:1400/1*FTiDKtVc6XDtLeqIdA1QpQ.png
