Secure Messaging and Multiparty Computation Techniques

Sabre: Sender-Anonymous Messaging with Fast Audits Adithya Vadapalli1, Kyle Storrier2, and Ryan Henry2 1University of Waterloo, adithya.vadapalli@uwaterloo.ca 2University of Calgary, {kyle.storrier, ryan.henry}@ucalgary.ca

Outline Introduction Sabre-BB DPF verification protocol Sabre-M Sabre-M mailbox security Conclusion 1

Sender-Anonymous Messaging (SAM) Sender-anonymous bulletin board model Sender-anonymous mailbox model 2

Sabre Sabre-BB in the bulletin board model Sabre-M in the mailbox model Improved verification protocols 3

Secure Multiparty Computation (MPC) Mutually distrustful parties Jointly compute a function of their private inputs This paper focus on (2 + 1)-party MPC protocols Two computing parties A third assisting party 4

MPC-in-the-Head Converts a ?-private MPC protocol into a zero-knowledge proof of knowledge (ZKPoK) Simulates an MPC protocol Prover commits to the transcripts of the simulated parties Verifier requests up to ? parties to have their communications revealed 5

Additive Secret Sharing ? ? 6

Additive Secret Sharing ?0 ?? 7

Additive Secret Sharing ?1= ? ?0 8

Additive Secret Sharing ? = ?1+ ?0 9

Additive Secret Sharing ? = ?1+ ?0 ? = ?1+ ?0 10

Additive Secret Sharing ? + ? = ?1+ ?1 + ?0+ ?0 11

Additive Secret Sharing over 2 2 is the ring of integers modulo 2 Represented with -bit integers Addition and multiplication are simply the corresponding operations modulo 2 12

Additive Secret Sharing over 0,1 The set of length bitstrings Represented with -bit integers For addition we use bitwise XOR For multiplication we use bitwise AND 13

Additive Secret Sharing Databases Secret Database Server 1 Server 2 14

Additive Secret Sharing Databases Share 1 Share 2 Server 1 Server 2 15

Additive Secret Sharing Databases Share 1 Share 2 Server 1 Server 2 16

Additive Secret Sharing Databases Write ? at index 2 Share 1 Share 2 Server 1 Server 2 17

Additive Secret Sharing Databases Write ? at index 2 0 Share 1 Share 2 0 ? 0 0 0 Server 1 Server 2 18

Additive Secret Sharing Databases Write ? at index 2 00 00 ?0 00 00 00 01 01 ?1 01 01 01 Share 1 Share 2 00 00 00 00 00 00 01 01 01 01 01 01 Server 1 Server 2 19

Additive Secret Sharing Databases Write ? at index 2 Share 1 Share 2 00 00 00 00 00 00 01 01 01 01 01 01 00 00 ?0 00 00 00 01 01 ?1 01 01 01 + + Server 1 Server 2 20

Additive Secret Sharing Databases Write ? at index 2 Share 1 Share 2 00 00 ?0 00 00 00 01 01 ?1 01 01 01 Server 1 Server 2 21

Additive Secret Sharing Databases Write ? at index 4 0 Share 1 Share 2 0 00 00 ?0 00 00 00 01 01 ?1 01 01 01 0 0 ? 0 Server 1 Server 2 22

Additive Secret Sharing Databases Write ? at index 4 00 00 00 00 ?0 00 01 01 01 01 ?1 01 Share 1 Share 2 00 00 ?0 00 00 00 01 01 ?1 01 01 01 Server 1 Server 2 23

Additive Secret Sharing Databases Write ? at index 4 Share 1 Share 2 00 00 ?0 00 00 00 01 01 ?1 01 01 01 00 00 00 00 ?0 00 01 01 01 01 ?1 01 + + Server 1 Server 2 24

Additive Secret Sharing Databases Share 1 Share 2 00 00 ?0 00 ?0 00 01 01 ?1 01 ?1 01 Server 1 Server 2 25

Additive Secret Sharing Databases Reconstruct the database Share 1 Share 2 00 00 ?0 00 ?0 00 01 01 ?1 01 ?1 01 Server 1 Server 2 26

Additive Secret Sharing Databases Reconstruct the database 00 00 ?0 00 ?0 00 01 01 ?1 01 ?1 01 + Server 1 Server 2 27

Additive Secret Sharing Databases Reconstruct the database 0 0 ? 0 ? 0 Server 1 Server 2 28

Point Functions A point function ??,? ??,?? = ? ??,?? = 0 for ? ? 1-nodes and 0-nodes 1-path leading to the distinguished point ? 29

Distributed Point Functions (DPFs) Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In Proceedings of CCS 2016, pages 1292 1303, Vienna, Austria (Oct. 2016). 30

Distributed Point Functions (DPFs) Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In Proceedings of CCS 2016, pages 1292 1303, Vienna, Austria (Oct. 2016). 31

Riposte Sender-anonymous bulletin board model Uses DPFs to write to randomly selected buckets Henry Corrigan-Gibbs, Dan Boneh, and David Mazi res. Riposte: An anonymous messaging system handling millions of users. In Proceedings of IEEE S&P 2015, pages 321 338, San Jose, CA, USA (May 2015). 32

Express Sender-anonymous mailbox model Uses DPFs to write to pre- registered mailbox addresses Saba Eskandarian, Henry Corrigan-Gibbs, Matei Zaharia, and Dan Boneh. Express: Lowering the cost of metadata-hiding communication with cryptographic privacy. In Proceedings of USENIX Security 2021, Vancouver, BC, Canada (Aug. 2021). 33

Sabre-BB Uses DPFs for writing like Riposte Uses logarithmic size DPFs Improved DPF verification 34

DPF Verification MPC Protocol Traverse the 1-path of the DPF tree to the distinguished point 35

DPF Verification MPC Protocol Seeds ??,?,? ??,?,? 36

DPF Verification MPC Protocol ??,?,? ??,?,? ?0,?,? ?1,?,? ?0,?,? ?1,?,? 37

DPF Verification MPC Protocol ??,?,? ??,?,? ?0,?,? ?1,?,? ?0,?,? ?1,?,? 1-Node 0-Node 0-Node 1-Node 38

DPF Verification MPC Protocol ??,?,? ??,?,? ?1,?,? ?0,?,? ?1,?,? ?0,?,? 0-Node 1-Node 1-Node 0-Node 39

DPF Verification MPC Protocol 0-Node 1-Node ?1,?,? ?1,?,? ?0,?,? ?0,?,? 40

DPF Verification MPC Protocol 0-Node 1-Node ?1,?,? ?1,?,? 0 ?0,?,? ?0,?,? 41

DPF Verification MPC Protocol New Seeds ?0,?,? ?0,?,? 42

Multi-Verifier MPC-in-the-Head DPF verification protocol can be converted to a ZKPoK using MPC-in- the-head The Sabre servers already have DPF keys They cannot see the simulated party with the other key Different servers verify different simulated parties Two vs three verifier versions 43

Sabre-BB Experimental Analysis 44

Sabre-M Uses the same DPF verification protocol as Sabre-BB Novel mailbox address verification protocol 45

Sabre-M Addresses Mailbox ? is given an address addr?= F ?,? A client writing in ? must send shares of the ? and addr? with its DPF DPF targets are just the indices of the target mailbox Significant space improvement over previous solutions Can use efficient full-domain evaluation 46

PRF Mailbox Verification Each server has received shares ?? and addr? The servers use MPC to compute addr?= F ?,? The servers compute addr? addr? The result should be zero ? 47

Sabre-M Experimental Analysis 48

Sabre Denial of Service Resistance 49