Working on a test case to confirm an idea would improve the performance of the RPM paper and reduce round complexity – it also has a neat side effect that it also enables massive parallel gradient descent compute for secure ML in a completely MPC context

BDFL of Quilibrium, Eng @ Farcaster, ex-Coinbase, always opinionated, never hydrated

/quilibrium

The most immediate applicability would be social media applications running on Quilibrium, allowing efficient but fully private recommendation systems

when you increase the number of participants in the protocol. I had tuned Quilibrium to be relatively lower bounded on this so it wasn't a super painful issue, but in the spirit of research and downtime waiting between flights, I kept thinking... https://i.imgur.com/eA7rNCI.gif

Cue a paper from 1989, where Bar-Ilan and Beaver produced an approach for multiplying an arbitrary number of square matrices of equal dimension: https://dl.acm.org/doi/pdf/10.1145/72981.72995

The TL;DR version is, instead of computing triples, you instead compute n+1 fully random matrices, _and their inverse_. When secret sharing those, each party can multiply the share of the random matrix by the share of the intended matrix to multiply, then multiply that by the _next_ random matrix's inverse.

Recombining those, you get a series of n recombined matrices that are indistinguishable from random, which you can then multiply together. Finally, you multiply the share of the first inverse matrix by that resulting product, and then that with the final random matrix share.

This, when recombined, gets you the resulting dot product of all the intended matrices, and only requires a complexity of four rounds (constant, which is a much better improvement over log(n)).

So why does this apply to ML? This comes back around to the SecureML paper, which explicitly was focusing on 2PC. Using this approach, you can augment their protocols as well, enabling MPC versions of SGD that are still very efficient.

In the spirit of building in public, I'll share the approach I'm evaluating – the RPM paper referenced the SecureML paper, which suggested the use of Beaver triples to keep the polynomial degree bounded to the shares of matrices when computing dot products. This works great under 2PC but requires log(n) rounds...

c/acc - 🏴‍☠️🌊 Bring me that Horizon 🍹
Gold League of Legends player

http://icebreaker.xyz/syed.fc

I know 😅 it can feel daunting with the volume of papers that just build on top of each other. At the end of the day, the math itself remains relatively simple – a high schooler could definitely reason about the end result, though probably not the proofs involved.