Actively Secure Arithmetic Computation and VOLE Study

Exploring actively secure arithmetic computation and VOLE with constant computational overhead at Tel Aviv University. Understanding how functions are represented in secure computation using arithmetic circuits over boolean circuits. Efficiently evaluating arithmetic circuits over large finite fields to minimize costs. Introduction to passively secure 2-party arithmetic MPC with constant computational overhead. Studying statistical security against multiple parties in arithmetic scenarios.

• Secure Computation
• Arithmetic Circuits
• Computational Overhead
• Secure MPC
• VOLE Study

cayal Follow

Uploaded on Sep 11, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Actively Secure Arithmetic Computation and VOLE with Constant Computational Overhead Benny Applebaum Niv Konstantini Tel Aviv University Available Positions

2. Secure Computation How is the function represented? Classically: Boolean circuits [Yao86, GMW87,...]

3. Secure Computation How is the function represented? The harsh reality

4. Secure Computation How is the function represented? Boolean circuits are universal

5. Secure Computation How is the function represented? Boolean circuits are universal Good luck with that

6. Secure Arithmetic Computation How is the function represented? A better alternative: arithmetic circuits Over a large enough field

7. Secure Arithmetic Computation How is the function represented? A better alternative: arithmetic circuits

8. The Model Goal: minimize cost of securely evaluating an arithmetic circuit over a large finite field F. Convenient model: Protocols with black-box access to F [IPS09,AAB15] Computational cost: # field operations (boolean operations are dominated) Communication cost: # field elements

9. Passively-Secure 2-Party Arithmetic MPC [A-Damg rd-Ishai-Nielsen-Zichron 17] Thm: constant computational overhead Circuit with s gates: O(s)+poly(k) field op s

10. Passively-Secure 2-Party Arithmetic MPC [A-Damg rd-Ishai-Nielsen-Zichron 17] Thm: constant computational overhead Circuit with s gates: O(s)+poly(k) field op s Black-box access to the field Hybrid OT-model Well-studied Assumptions Statistical Security against one party Extends to O(1) parties Arithmetic Alekhnovich LPN over sparse matrix with constant noise VOLE vector-by-scalar multiplication Arithmetic Goldreich local PRG with poly-stretch constant overhead constant round

11. Passively-Secure 2-Party Arithmetic MPC [A-Damg rd-Ishai-Nielsen-Zichron 17] Thm: constant computational overhead Circuit with s gates: O(s)+poly(k) field op s Black-box access to the field Hybrid OT-model Well-studied Assumptions Statistical Security against one party Extends to O(1) parties Many Applications Secure linear algebra Arithmetic garbling Keyword search Set intersection ZK-proofs Noninteractive-MPC [MW08, AIK14,FIPR05, GN17, BCGI18, CDI+19, DIO21, WYKW21, BMRS21,CDI+19, DIO21]. Concrete Efficiency Arithmetic Alekhnovich LPN over sparse matrix with constant noise VOLE vector-by-scalar multiplication Arithmetic Goldreich local PRG with poly-stretch constant overhead constant round

12. Passively-Secure 2-Party Arithmetic MPC [A-Damg rd-Ishai-Nielsen-Zichron 17] Today: Can we achieve a similar result with Active Security? Thm: constant computational overhead Circuit with s gates: O(s)+poly(k) field op s Black-box access to the field Hybrid OT-model Well-studied Assumptions Statistical Security against one party Extends to O(1) parties Concrete Efficiency Arithmetic Alekhnovich LPN over sparse matrix with constant noise VOLE vector-by-scalar multiplication Arithmetic Goldreich local PRG with poly-stretch constant overhead constant round

13. Passively-Secure 2-Party Arithmetic MPC [A-Damg rd-Ishai-Nielsen-Zichron 17] Today: Can we achieve a similar result with Active Security? Thm: constant computational overhead Circuit with s gates: O(s)+poly(k) field op s Black-box access to the field Hybrid OT-model Well-studied Assumptions Statistical Security against one party Extends to O(1) parties Can t use the GMW compiler (e.g., ADINZ + BCGGHJ17) Concrete Efficiency Arithmetic Alekhnovich LPN over sparse matrix with constant noise VOLE vector-by-scalar multiplication Arithmetic Goldreich local PRG with poly-stretch constant overhead constant round

14. Our Results: Theory Thm: constant computational overhead with Active security Circuit with s gates: O(s)+poly(k) field op s Black-box access to the field Hybrid OT-model Well-studied Assumptions Statistical Security against one party Extends to O(1) parties Arithmetic Alekhnovich LPN over sparse matrix with constant noise VOLE vector-by-scalar multiplication Arithmetic Goldreich local PRG with poly-stretch constant overhead constant round

15. Our Results: Theory Thm: constant computational overhead with Active security Circuit with s gates: O(s)+poly(k) field op s Black-box access to the field Hybrid OT-model Well-studied Assumptions Statistical Security against one party Extends to O(1) parties Even for VOLE alone: Existing solution [BCGI18,BCGIKRS19] requires strong assumptions optimal rate but no stat-security Arithmetic Alekhnovich LPN over sparse matrix with constant noise VOLE leaky-LPN sub-const. noise less studied matrices vector-by-scalar multiplication constant overhead constant round correlation robust hashing

16. Our Results: Practice Thm: VOLE with Active security and Concrete Efficiency Arithmetic Alekhnovich LPN over sparse matrix with constant noise New Variant: Hard to find Correlated Noisy-Codeword VOLE vector-by-scalar multiplication

17. Our Results: Practice Thm: VOLE with Active security and Concrete Efficiency First (?) implementation over large fields (16, ,128 bits) Parameters as in passive-ADINZ17 only minor overhead ~20% New optimizations (Sparse LU-decomposition)

18. Our Results: Practice Thm: VOLE with Active security and Concrete Efficiency Communication: 3 rounds 4 field elements per VOLE element Computation: Amortization kicks-in Fast 10K-long vectors: pay 4 OT s + 300 arithmetic op s (ADD/MUL) Constant improves for longer vectors Offline Phase: Non-interactive local Fast Online Phase: Online Receiver: 4 OT s + 10 arithmetic op s Online Sender: 4 OT s + 80 arithmetic op s VOLE-based ZK-proof (e.g., DIO21) with Super-Fast Online-Verification

19. Our Results: Practice Thm: VOLE with Active security and Concrete Efficiency Communication: 3 rounds 4 field elements per VOLE element Computation: Amortization kicks-in Fast 10K-long vectors: pay 4 OT s + 300 arithmetic op s (ADD/MUL) Constant improves for longer vectors Offline Phase: Non-interactive local Fast Online Phase: Online Receiver: 4 OT s + 10 arithmetic op s Online Sender: 4 OT s + 80 arithmetic op s For medium-size vectors & fast network we seem to beat existing approaches (e.g., compressed-VOLE [BCGI18, BCGIKRS19]) Generating Solving Sparse Linear Equations vs short VOLE-correlations

20. Few Words About the Techniques 2 VOLE vector-by-scalar multiplication 3 1

21. The ADINZ Core Protocol ? ?? ? ? Reverse VOLE Bob Alice ? ?? ? ? + ? ?? Secret sharing of ? ? 21

22. The ADINZ Core Protocol Noisy-linear mapping ? = ? ? + ????? Alice Bob ? = ? ? + ? ? = ? ? ? + ? + ? ????? Should send only the non-noisy entries 22

23. The ADINZ Core Protocol Noisy-linear mapping ? = ? ? + ????? Linear-time Alice Bob ? = ? ? + ? ? = ? ? ? + ? + ? ????? ? = set of clean coordinates ? ? ? + ? Linear-time ? ? + ? ?? 23

24. Insecurity Against Cheating Bob Noisy-linear mapping ? = ? ? + ????? Alice Bob Challenge 1: Force honest behavior Without knowing the noise Efficiently (Linear-time) BB-access to OT s ? = ? ? + ? ? = ? ? ? + ? + ? ????? ? = set of clean coordinates + noisy coordinate ? ????? ? 24

25. Insecurity Against Cheating Bob Noisy-linear mapping ? = ? ? + ????? Alice Bob Obs: Security holds if ? ? ???? (?[?]) Sol: Use Generalized OT [IK97] ? = ? ? + ? ? = ? ? ? + ? + ? ????? ? = set of clean coordinates + noisy coordinate ? ????? ? Pass information only if ? ? ???? (?[?]) 25

26. Insecurity Against Cheating Bob Noisy-linear mapping ? = ? ? + ????? Alice Bob New construction: Conditional Disclosure of Secrets Linear-Time encoding/decoding Information-Theoretic Security ? = ? ? + ? ? = ? ? ? + ? + ? ????? ? = set of clean coordinates + noisy coordinate secret-shares ? ????? If condition fails, leaks information about ? but this is simulatable ? Pass information only if ? ? ???? (?[?]) 26

27. Security Against Cheating Alice??? Noisy-linear mapping ? = ? ? + ????? Alice Bob Does not lead to privacy leakage but may affect correctness ? = Crazy ( ?) Simulation problem! ? = set of clean coordinates ? ? ? + ? ? ? + ? ?? Depending on ?????[1] 27

28. Security Against Cheating Alice??? Noisy-linear mapping ? = ? ? + ????? Alice Bob Several alternative solutions: Heuristic Silent Cut-&-Choose linear-time exposure-resilient function Intermediate: Use new assumption ? = Crazy ( ?) ? = set of clean coordinates ? ? ? + ? ? ? + ? ?? Depending on ?????[1] 28

29. The Noisy-Correlated Codeword Assumption Adversary Challenger ? = ? ? + ????? Clean area remains clean Far from any wins if: scalar-multiple of original noise ? = Image E + ??????????_????? We show: Reduces to LPN in the binary setting

30. Summary: Constant Overhead MPC PASSIVE ACTIVE ??? IKOS08 Boolean ADINZ17 This work Arithmetic

31. Take-Home Message Arithmetic setting allows efficient passive->active compilation Exploit: Linear Algebraic Structure of the protocol Honest parties are low-degree polynomial Unexpected feature of arithmetic-BB model Garbler Active protocol Honest Evaluator Low-Degree Polynomial

32. Further Research Study security and efficiency of building blocks New Correlated-Noisy-Codeword assumption Local arithmetic PRGs Improve concrete cost of vector-OLE protocol Other error-correcting codes/LPN matrices/noise models? Concretely efficient Arithmetic secure computation Better OT-extension in the arithmetic setting Currently relies on arithmetic variant of Beaver Active Security Constant overhead for Boolean Circuits??

34. Arithmetic complexity benchmark In order to fairly compare, we used the same two sets of parameters as in the ADINZ tests and the same noise fraction of ? = 0.25. Concrete amortized arithmetic complexity (divided by VOLE width - ?): ? = 182,? = 10000 ? = 240,? = 20000 Offline Online Total Offline Online Total Alice 114.06 7.62 121.69 104.94 6.76 111.7 Bob 91.49 78.23 169.72 107.48 73.09 180.57 Total 205.55 85.86 291.41 212.43 79.85 292.28 34

35. Time Benchmark Our setup consists of a computer with 32GB RAM and a 64-bit i7-13700K CPU running at 3.4GHz. Bob s measurements (in ????): ? = 182,? = 10000 ? = 240,? = 20000 Field Offline Online Total Offline Online Total 16 bit 298.54 75.04 373.58 485.91 89.15 575.06 32 bit 324.7 105.95 430.65 506.57 129.18 635.75 64 bit 369.63 147.29 516.92 578.88 212.67 791.55 128 bit 381.22 166.41 547.63 606.79 249.37 856.16 35

36. Time Benchmark Our setup consists of a computer with 32GB RAM and a 64-bit i7-13700K CPU running at 3.4GHz. Alice s measurements (in ????): ? = 182,? = 10000 ? = 240,? = 20000 Field Offline Online Total Offline Online Total 16 bit 171.89 72.09 243.98 173.56 79.44 253 32 bit 186.71 78.36 265.07 198.93 88 286.93 64 bit 270.57 89.71 360.28 344.98 102.15 447.13 128 bit 284.53 90.23 374.76 373.78 106.05 479.83 36