(2025-12) UFOs; An Ultra-fast Toolkit for Multiparty Computation of Small Elements
2025-12-18
In most secure multiparty computation (MPC) scenarios, the data to be processed are much smaller than the underlying field size. The field is typically chosen to be large enough to guarantee security, e.g., a 128-bit prime field for 128-bit security, while the data can be as small as several bits, e.g. bits for a -category classification task. This size gap can result in significant waste of communication and computation in existing MPC protocols, which often treat data of different ranges indiscriminately.
We introduce UFO, an ultra-fast toolkit for multiparty computation (MPC) on small elements. UFO provides highly optimized protocols for three fundamental tasks: one-hot encoding, comparison and digit decomposition. While these protocols are designed specifically for small elements, as a demonstration of their power, we construct a radix sort protocol that sorts large field elements. Our experiments show significant performance improvements over state-of-the-art MPC implementations. In particular, our sorting protocol achieves up to a speedup in the online phase when sorting elements among parties.