spdz explanation details cryptography.pptx

Spdz

1. Multiparty computation SPDZ

2. MultiParty Computation n parties, holding private inputs x 1 ,..., x n wish to compute a given function f(x 1 ,..., x n ) each one gets (y 1 , ..., y n )

3. Security Requirements Privacy Correctness Example: auction Only information available will be current bidding price and not personal info of biter’s The result of the auction relates to the highest bid.

4. Practical Examples Private Information Retrieval => airline company Location-Sharing Applications Distributed Certificate Authority

5. MULTIPARTY COMPUTATION Boolean Circuits Arithmetic Circuits

6. Boolean Circuits B oolean functions like f : {0, 1} n → {0, 1} n Introduced from Yao in 1982

7. Boolean Circuits Garbled Circuit is created from Player 1 Player 1 sends circuit to Player 2 Oblivious transfer delivers key to Player 2, while Player 1 learns nothing. Player 2 evaluates the circuit with key to get output f (x, y). Then f (x, y) is sent back to P1 and both parties output this value.

8. Arithmetic C ircuits P erfect for representing and computing polynomials They can represent any functionality. Based on Secret Sharing.

9. SPDZ named after a clever permutation of the initials of the authors. uses fully homomorphic encryption and arithmetic circuit protocols to achieve secure multiparty computation efficient phase of securely calculating shared function has two distinct phases online phase actual circuit is evaluated offline-preprocessing phase generates some random data

10. Additive Secret Sharing Share value α Every player receives α i A ttacker must have every share to reconstruct the secret.

11. MAC (Message Authentication Code) Its created by combining a secret key with a hash algorithm U sed in authenticating messages (secure if key remains secret) In SPDZ, it validates the integrity of results of different calculations

12. Online phase - Initialization Assume each player has access to some preprocessed data from offline phase triplets (< a > ,< b >,< c >) with random values, such that c = a * b a secret key Input Shares value x will be noted as < x > =(x i , γ i ( x i ) )

13. Processing - Addition players simply sum their local shares < t>=<x>+<y>=(x i + y i ,γ xi + γ yi )=< x+y >

14. Processing - Multiply shares We can’t just multiply local shares < t > ∗ < z > Have to use the precomputed triples (< a >,< b >,< c >) Each player calculates < ε > = < t > − < a > and <ρ>= < z > − < b >. are partially open < ε > and <ρ> broadcasts value but not MACs Each player sum received shared to get ε = t − a and ρ = z − b ε and ρ are one- timepads encryption for t and z respectively Each player calculates < o >=< c > +ε∗ < b > +ρ∗ < a > +ε ∗ ρ

15. Multiplication Proof

16. Verification

17. Fully Homomorphic Encryption (FHE) Given c 1 = Enc pk ( m 1 ) and c 2 = Enc pk ( m 2 ) we have Assume each player has a public and private key Dec sk (c 1 + c 2 ) = m 1 + m 2 and Dec sk (c1 * c 2 ) = m 1 * m 2

18. Offline phase Players in offline phase can be different from players in online phase

19. Offline phase

20. Offline phase

21. Offline phase

22. SPDZ limits – UC Framework A ssumed to be given as part of the specification Generate a key pair Secret-share the secret key among the players using a secret- sharing scheme

23. SPDZ and the future Enigma Storage storage of both private a public data Private data stay encrypted on client-side in a distributed database Correctness scheme secure against n active adversaries Privacy

24. Implementation S ecure multiparty computation for mobile and IoT devices Μ ultiple devices with similar sensors monitor properties belonging to different individuals. For instance cctv monitoring warehouses or houses, fields in agriculture and in general sensors that are nearby and belong to more than one owners.

25. Off the grid SPDZ complex communication between participants synchronization issues many algorithms that carefully need to be implemented Based on open-source projects in SPDZ from s tudents at University of Minho

26. Beaconing Operation Devices calculate their significance based on a Local Connectivity (LC) value:   LC Value Residual Energy Normalization Factor Neighboring Devices Connected Devices

27. Overall easy computations communication overhead multiplication onetime pads ε and ρ require O(n 2 ) communication interactions Flooding In moving networks were nodes come and leave Need duplicates