Nillion Introduces a Non-Interactive MPC Protocol for Non-Linear Computations

Blockchains have blazed a path for decentralized transactions and value storage, disentangling these functionalities from the suites of services provided by traditional financial gatekeepers. The impact of this has changed the world and is continuing to play out. However, there is still a universe of data that lies beyond financial transactions that would also benefit greatly from the decentralization of trust — specifically, the secure computation and storage of what we call “high value data” (e.g. private keys, identity information, private AI model weights, proprietary business secrets, healthcare and compliance information, etc.).

Secure Multi-Party Computation (MPC) protocols decentralize and safeguard data by enabling collaborative computing over data that remains encrypted. Choosing the right MPC protocol for a use case requires navigating trade-offs between the complexity of the operations required, the communication overheads involved, and whether the work can be performed asynchronously. We’re excited to introduce a novel MPC protocol developed at Nillion that represents a new region in this trade-off space. Leveraging well-known existing schemes as a foundation, the protocol keeps data decentralized and secure. However, it shifts costs in a way that eliminates communication overheads for users and improves the performance of the computation process itself (after the inputs have arrived), even for some more complex, non-linear operations.

The Technical Report

Last week we released “Evaluation of Sum-of-Products Expressions in Linear Secret Sharing Schemes with a Non-Interactive Computation Phase.” Our technical report introduces an MPC protocol based on Linear Secret-Sharing Scheme (LSSS). The protocol can evaluate sums of products (SoP) of non-zero user inputs without compromising the confidentiality of these inputs. A longer form of the report is planned for release at a later date. Here's a closer look at how this approach maintains information-theoretic security (ITS) while efficiently running SoP programs.

Extending the Capabilities of LSSS

Basic Linear Secret Sharing Schemes can handle linear operations, such as adding or multiplying by a known number on hidden user inputs. However, they typically require a synchronous workflow that needs interactive communication between parties during computation. This means that all parties need to be actively online during the computation process, which can be a limiting factor for real world use cases.

The Nillion protocol is designed to perform some non-linear operations, specifically to evaluate a sum of products of hidden user inputs. It incorporates a phased workflow. The pre-processing phase is completed ahead of time, allowing for an asynchronous and non-interactive computation phase. This design eliminates the need for additional communication between parties during computation, significantly enhancing the speed and efficiency of the process.

Breaking Down the Two-Phase Protocol

Pre-processing Phase: This phase is input-independent and is completed in advance using standard MPC techniques. The objective is to create sharings (masks) for each factor and term in the SoP expression. While the pre-processing doesn’t depend on the private input values, it is influenced by the structure of the inputs, such as the number of factors and terms in the SoP expression.
Non-Interactive Computation Phase: Here, the computation is input-dependent but does not require any communication between parties. During this phase, parties combine shares generated in pre-processing with the inputs to create masked factors. These masked factors, which are broadcasted, are multiplicatively homomorphic and maintain ITS. Subsequently, parties perform local sum of products calculations and reveal the result.

Protocol Features at a Glance

Non-linear Arithmetic Capabilities: The protocol can evaluate non-linear arithmetic expressions, specifically a sum of products of hidden inputs, without leaking input information to any of the parties.
Efficient Pre-Processing: The creation of mask sharings is independent of input values and depends solely on the number of inputs in each term.
Asynchronous Computation: The non-interactive nature of the computation phase aligns with asynchronous workflows and accelerates the process, as it does not require message exchanges between parties.
ITS Security: The protocol upholds the information-theoretic security (ITS) inherent in LSSS.

Example Implementation: the tinynmc Python Library

We created the tinynmc library as a minimal, pure-Python example implementation of the protocol, illustrating how arithmetic sum-of-products expressions can be evaluated via a non-interactive computation phase. This library is available as a package on PyPI.

Summary

The new Nillion protocol marks a step forward in MPC, blending secure computing, data privacy, and efficiency for practical real-world applications. Its two-phased approach, involving pre-computing masks and enabling non-interactive computation, improves efficiency and fits into asynchronous workflows.

This is just the beginning. More technical papers, libraries, and implementation examples are on the way. Follow NillionNetwork on X to stay up to date on everything we are building.

Check out the tinynmc library's source code on Github.