Show HN: Tandem – An Engine for Secure Multi-Party Computation (Written in Rust)(github.com)
github.com
Show HN: Tandem – An Engine for Secure Multi-Party Computation (Written in Rust)
https://github.com/sine-fdn/tandem
2 comments
How much overhead can you expect when executing code as a garbled circuit? Is there a limit to the amount of instructions before using garbled circuits becomes impractical?
Since all programs have to be compiled to boolean gates and these gates have to be encrypted, there is a difference of a few orders of magnitude between running programs natively on a CPU (which can of course use highly optimized arithmetical instructions) and running programs over MPC.
In the end, it all depends on the complexity of the program: For simple programs like the Wordle guess/solution comparison (about 40 lines of code, compiled to < 2k gates) the communication overhead is more significant than the computational overhead. The Garbled Circuits protocol used by Tandem needs 7 rounds of communication, so with a round-trip time of 50ms the whole execution takes 350ms.
For more complicated programs, the computational overhead becomes a bit more significant. For programs of > 100k gates, the time to execute a program can range from a few seconds to about a minute. For example, an AES 256 computation requires ~ 9k AND gates and 40k XOR gates.
Right now I would not use it for programs with more than a couple 100k gates, but the engine has not yet been optimized very much, at the moment the focus is on providing a good UX and an easy way for people to experiment with MPC. I'm pretty sure that with a bit of optimization efforts it will be possible to speed it up significantly.
In the end, it all depends on the complexity of the program: For simple programs like the Wordle guess/solution comparison (about 40 lines of code, compiled to < 2k gates) the communication overhead is more significant than the computational overhead. The Garbled Circuits protocol used by Tandem needs 7 rounds of communication, so with a round-trip time of 50ms the whole execution takes 350ms.
For more complicated programs, the computational overhead becomes a bit more significant. For programs of > 100k gates, the time to execute a program can range from a few seconds to about a minute. For example, an AES 256 computation requires ~ 9k AND gates and 40k XOR gates.
Right now I would not use it for programs with more than a couple 100k gates, but the engine has not yet been optimized very much, at the moment the focus is on providing a good UX and an easy way for people to experiment with MPC. I'm pretty sure that with a bit of optimization efforts it will be possible to speed it up significantly.
MPC has in the past been mostly confined to academia, but thanks to some recent papers has finally become fast enough for practical applications. Tandem uses Garbled Circuits, encrypted circuits consisting of boolean gates. While there have been other implementations based on these ideas, Tandem tries to provide a much better user experience than previous attempts. For example, the Tandem repo includes a server, a command line client and client libs for wasm and native architectures. To make it easier to run practical applications, programs can be written in Garble, a custom Rust-like programming language that compiles to Garbled Circuits.
(The most practical application to date using Tandem is "Encryptle", a Wordle clone that runs entirely over MPC. Depending on latency, a client/server exchange takes about 400ms, which makes the UX very similar to the real Wordle, with the twist that the server cannot see the guess in plain text and the browser cannot see the solution in plain text. Instead, guess and solution are kept private and compared using MPC.)