CNF-FSS and Its Applications: PKC 2022 March 08

Explore the Background, Applications, and Summary of CNF-FSS, focusing on Function Secret Sharing, Distributed Point Function, CNF Key-Sharing, and more. Learn about the efficiency of multiparty sharing and 1-out-of-3 CNF-FSS constructions for certain classes of functions. Discover how CNF Key-Sharing is used in various applications like Verifiable Secret Sharing, Fault Tolerance, and more.

• CNF-FSS
• Applications
• Efficiency
• Multiparty
• Function Secret Sharing

zaynah Follow

Uploaded on Jul 23, 2024 | 1 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. CNF-FSS and its Applications Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky PKC 2022 March 08, 2022

2. Outline o Background o Application 1: CNF-FSS More Efficient Multiparty FSS o Application 2: 1-out-of-3 CNF-FSS o Summary

3. Outline o Background o Application 1: CNF-FSS More Efficient Multiparty FSS o Application 2: 1-out-of-3 CNF-FSS o Summary

4. Background: Function Secret Sharing [GI15] Sharing a function Sharing a secret -3 7 4

5. Background: Function Secret Sharing o Consists of Dealer and N-Parties, and three algorithms: o Gen( , f) o Eval(kP, x) o Reconstruct({Eval(kP)}) o Known FSS constructions for certain classes of functions DPF(i, v) o Distributed Point Function (DPF) [GI14,BGI15,BGI16] v o Solved for 2-party DPF o Open for p > 2: Less communication (for Gen algorithm) o Step-Functions, Intervals i

6. Background: CNF Key-Sharing o Introduced in [ISN87] oAlso known as replication-based and multiple assignment secret sharing o In our work, a (t, p) CNF-sharing means: oS S denotes set of all subsets of size t o Assign a unique key to each subset T S S o For each index i, let TiS S denotes sets that do not include index i o For each party i, assign keys {kTi} o Observation: o No t parties can reconstruct o Any (t+1) parties can reconstruct

7. Background: CNF Key-Sharing (continued) o For this talk, we consider cases: o (t, p) = (2, 5) o (t, p) = (1, 3) o CNF Key Sharing has been used in several applications, including: o Verifiable Secret Sharing and MPC protocols o Fault tolerance/redundancy o PIR o Other generalizations (when viewed as a special case of formula-based secret sharing)

8. Outline o Background o Application 1: CNF-FSS More Efficient Multiparty FSS o Application 2: 1-out-of-3 CNF-FSS o Summary

9. Application 1: CNF-FSS More Efficient Multiparty FSS Background: o (1, p)-FSS: Solved ([GI14,BGI15,BGI16]) o (t, p)-FSS with t > 1: o Best known: O( ?) communication ([GI14,BGI15,BGI16]) o O(4?) communication for special case: p = p1 p2 ([BGI18]) o E.g. p1 = p2 = 3, t = 2: (2, 9)-FSS scheme with O(4?) communication

10. Application 1: CNF-FSS More Efficient Multiparty FSS Our Results: oTheorem 1(Informal): For any parameters t, p, d such that p dt + 1, there exists a (t, p)-FSS scheme with communication O(n1/2d) o Proof: Constructive o Example: t = 2, p = 5, d = 2: (2, 5)-FSS with communication O(4?) o Previous best [BGI15] for (2, 5)-FSS was communication O( ?) oTheorem 2(Informal): For any parameters t, p, d such that p dt + 1, there exists a (t, p)-FSS information-theoretically secure scheme with communication O(n1/d) o Proof: Constructive

11. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2)

12. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2) 5 2 , so let {Tj} denote subsets of size 2. o Step 2: Notice 10 = Associate keys kj and Kj to each subset Tj

13. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2) 5 2 , so let {Tj} denote subsets of size 2. o Step 2: Notice 10 = Associate keys kj and Kj to each subset Tj o Step 3 (KeyGen): Deal keys to each party i [1, 5] (as per standard CNF-sharing rules) (Each party receives 6 keys from {kj} and {Kj})

14. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2) 5 2 , so let {Tj} denote subsets of size 2. o Step 2: Notice 10 = Associate keys kj and Kj to each subset Tj o Step 3 (KeyGen): Deal keys to each party i [1, 5] (as per standard CNF-sharing rules) (Each party receives 6 keys from {kj} and {Kj}) o Step 4 (Eval): Notice: f(y) = f1(y1) f2(y2) = (Eval(k1, y1) + + Eval(k10, y1)) (Eval(K1, y2) + + Eval(K10, y2))

15. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2) 5 2 , so let {Tj} denote subsets of size 2. Correctness. Cross-terms: Eval(ki, y1) Eval(Kj, y2) - 3 (out of 5) know ki - 3 (out of 5) know Kj o Step 2: Notice 10 = Associate keys kj and Kj to each subset Tj o Step 3 (KeyGen): Deal keys to each party i [1, 5] (as per standard CNF-sharing rules) (Each party receives 6 keys from {kj} and {Kj}) o Step 4 (Eval): Notice: f(y) = f1(y1) f2(y2) = (Eval(k1, y1) + + Eval(k10, y1)) (Eval(K1, y2) + + Eval(K10, y2)) (At least) one party knows both

16. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2) 5 2 , so let {Tj} denote subsets of size 2. o Step 2: Notice 10 = Associate keys kj and Kj to each subset Tj o Step 3 (KeyGen): Deal keys to each party i [1, 5] (as per standard CNF-sharing rules) (Each party receives 6 keys from {kj} and {Kj}) o Step 4 (Eval): Notice: f(y) = f1(y1) f2(y2) = (Eval(k1, y1) + + Eval(k10, y1)) (Eval(K1, y2) + + Eval(K10, y2)) Security. For any 2 Parties (i, j) the set Ti, So cross-term: Eval(kTi, j contains both indices. j, y1) Eval(KTi, j, y2)

17. Application 1: CNF-FSS More Efficient Multiparty FSS Intuition: o Step 1: DPF(x, v); write x = (i, j) [1, ?] x [1, ?] and v = v1 v2. Use [BGI15] for (9, 10)-DPF keys {ki} for DPF(i, v1) and {Ki} for DPF(j,v2) 5 2 , so let {Tj} denote subsets of size 2. o Step 2: Notice 10 = Associate keys kj and Kj to each subset Tj o Step 3 (KeyGen): Deal keys to each party i [1, 5] (as per standard CNF-sharing rules) (Each party receives 6 keys from {kj} and {Kj}) o Step 4 (Eval): Notice: f(y) = f1(y1) f2(y2) = (Eval(k1, y1) + + Eval(k10, y1)) (Eval(K1, y2) + + Eval(K10, y2)) o f1 and f2 have domain size ?, so keys {ki} and {Ki} are O(4?) Cost. Communication is O(4?) : o Each party gets 6 keys {ki} and 6 keys {Ki}

18. Outline o Background o Application 1: CNF-FSS More Efficient Multiparty FSS o Application 2: 1-out-of-3 CNF-FSS o Summary

19. Application 2: 1-out-of 3 CNF-FSS Background: o 1-out-of-2 solved in [GI14,BGI15,BGI16] (O(log n)) o Implies O(log n) for 1-out-of-3

20. Application 2: 1-out-of 3 CNF-FSS Background: o 1-out-of-2 solved in [GI14,BGI15,BGI16] (O(log n)) o Implies O(log n) for 1-out-of-3 o 2-out-of-3: O( ?) ([GI14,BGI15,BGI16,BKKO20]) o Gap remains: lower-bound O(log n); upper-bound O( ?)

21. Application 2: 1-out-of 3 CNF-FSS Background: o 1-out-of-2 solved in [GI14,BGI15,BGI16] (O(log n)) o Implies O(log n) for 1-out-of-3 o 2-out-of-3: O( ?) ([GI14,BGI15,BGI16,BKKO20]) o Gap remains: lower-bound O(log n); upper-bound O( ?) o 1-out-of-3 CNF-FSS lies between 1-out-of-3 and 2-out-of-3: o 1-out-of-3 CNF-FSS: 3 keys total, each party receives two of them o 2-out-of-3 FSS: 3 keys total, knowledge of any two of them reveals nothing o2-out-of-3 FSS 1-out-of-3 CNF-FSS

22. Application 2: 1-out-of 3 CNF-FSS Background: o 1-out-of-2 solved in [GI14,BGI15,BGI16] (O(log n)) o Implies O(log n) for 1-out-of-3 o 2-out-of-3: O( ?) ([GI14,BGI15,BGI16,BKKO20]) o Gap remains: lower-bound O(log n); upper-bound O( ?) o 1-out-of-3 CNF-FSS lies between 1-out-of-3 and 2-out-of-3: o 1-out-of-3 CNF-FSS: 3 keys total, each party receives two of them o 2-out-of-3 FSS: 3 keys total, knowledge of any two of them reveals nothing o2-out-of-3 FSS 1-out-of-3 CNF-FSS o 1-out-of-3 CNF-FSS sufficient in some settings o For example DORAM ([BKKO20])

23. Application 2: 1-out-of 3 CNF-FSS Background: o 1-out-of-2 solved in [GI14,BGI15,BGI16] (O(log n)) o Implies O(log n) for 1-out-of-3 o 2-out-of-3: O( ?) ([GI14,BGI15,BGI16,BKKO20]) o Gap remains: lower-bound O(log n); upper-bound O( ?) o 1-out-of-3 CNF-FSS lies between 1-out-of-3 and 2-out-of-3: o 1-out-of-3 CNF-FSS: 3 keys total, each party receives two of them o 2-out-of-3 FSS: 3 keys total, knowledge of any two of them reveals nothing o2-out-of-3 FSS 1-out-of-3 CNF-FSS o 1-out-of-3 CNF-FSS sufficient in some settings o For example DORAM ([BKKO20]) o So: 1-out-of-2: O(log n) 1-out-of-3 CNF-FSS 2-out-of-3: O( ?) . but where?

24. Application 2: 1-out-of 3 CNF-FSS Our Results: oTheorem 3 (Informal): There exists a (1, 3)-CNF-DPF scheme with communication O(log2n) oProof: Constructive

25. Application 2: 1-out-of 3 CNF-FSS (x0, y0) Intuition: (x1, y1) (z1, z1) o 1-out-of-2: O(log n) (z2, z2) (x2, y2) . .. (xi, yi) (xi+1, yi+1) (zi+1, zi+1) . ..

26. Application 2: 1-out-of 3 CNF-FSS (x0, y0) Intuition: (x1, y1) (z1, z1) o 1-out-of-2: O(log n) (z2, z2) (x2, y2) Deal information on each level to maintain variant: On-Path Seeds Distinct Off-Path Seeds Match . .. (xi, yi) (xi+1, yi+1) (zi+1, zi+1) . ..

27. Application 2: 1-out-of 3 CNF-FSS Intuition: P1: (ai, di) P2: (bi, di) P3: (ci, di) P1: (a P2: (b P3: (c ?, b ?, c ?, a ?) ?) ?) P1: (a1, b1) P2: (b1, c1) P3: (c1, a1) o 1-out-of-2: O(log n) . . . . . . . . . . . . ... ... o 2-out-of-3: O( ?) i ? ? ?

28. Application 2: 1-out-of 3 CNF-FSS Intuition: P1: (ai, di) P2: (bi, di) P3: (ci, di) P1: (a P2: (b P3: (c ?, b ?, c ?, a ?) ?) ?) P1: (a1, b1) P2: (b1, c1) P3: (c1, a1) o 1-out-of-2: O(log n) . . . . . . . . . . . . ... ... o 2-out-of-3: O( ?) i ? ? ? o ? PRG seeds satisfy invariant: Off-Path ( j i ) keys overlap P1: (aj, bj) P1: (ai, di) P2: (bj, cj) P3: (cj, aj) On-Path ( j = i ) keys don t overlap P2: (bi, di) P3: (ci, di)

29. Application 2: 1-out-of 3 CNF-FSS P1: (a0, d0, b0) P2: (b0, d0, c0) P3: (c0, d0, a0) Intuition: o 1-out-of-2: O(log n) P1: (a1, d1, b1) P2: (b1, d1, c1) P3: (c1, d1, a1) P1: (a1, b1, c1) P2: (b1, c1, a1) P3: (c1, a1, b1) o 2-out-of-3: O( ?) o Combine these approaches . .. . ..

30. Application 2: 1-out-of 3 CNF-FSS P1: (a0, d0, b0) P2: (b0, d0, c0) P3: (c0, d0, a0) Intuition: o 1-out-of-2: O(log n) P1: (a1, d1, b1) P2: (b1, d1, c1) P3: (c1, d1, a1) P1: (a1, b1, c1) P2: (b1, c1, a1) P3: (c1, a1, b1) o 2-out-of-3: O( ?) o Combine these approaches . .. Deal information on each level to maintain variant: On-Path: 4 Distinct seeds: 1 common to all, each pair has 1 overlapping Off-Path: 3 Distinct seeds: Each pair has all three . ..

31. Outline o Background o Application 1: CNF-FSS More Efficient Multiparty FSS o Application 2: 1-out-of-3 CNF-FSS o Summary

32. Summary o Our Results: o Defined CNF FSS o Demonstrated utility of CNF-FSS for making better (standard) t-out-of-p FSS o Construction of (1, 3) CNF-FSS, with near-optimal communication (and superior to (standard) 2-out-of-3 FSS) o Applications: o More efficient (t, p)-FSS protocols o DORAM [BKKO20] o Fault tolerance/redundancy o Open Problems: o (2, 3)-FSS in o( ? ) communication o More efficient (t, p)-FSS protocols (close remaining gap) o Other applications of CNF-FSS?

33. Questions? Thank You!