Introducing the Nillion Non-Interactive MPC Protocol for Non-Linear Computations

PUBLISHED

11.22.2023

AUTHOR

Nillion

CATEGORY

Tech Updates

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.

Let’s dive into the report and the implementation.

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

  1. 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.
  2. 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.

The tinynmc 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.

An example Implementation with tinynmc

The basic example involves three contributors ab, and c (parties submitting private input values) and three nodes 01, and 2 (parties performing a computation)

>>> nodes = [node(), node(), node()]

The overall sum-of-products expression being computed is (1 * 2 * 3) + (4 * 5). First, the contributors agree on a workflow signature. The signature lists the number of factors in each term:

>>> signature = [3, 2]

The signature must be shared with every node so that the nodes can collectively perform the preprocessing phase (this can be accomplished using any MPC protocol that supports multiplication of secret-shared values, such as the SPDZ protocol that is implemented as part of TinySMPC library):

>>> preprocess(signature, nodes)

Next, each factor in the workflow is contributed by one of three contributors a, b, or c, with the ownership pattern (a * b * c) + (a * b). Each factor is referenced by the contributors according to its (term_index, factor_index) coordinate within the overall expression: ((0, 0) * (0, 1)) + ((1, 0) * (1, 1) * (1, 2)).

Each contributor can convert its coordinate-value pairs into masked factors by (1) requesting the multiplicative shares of the masks for each coordinate, and (2) masking its factors at each coordinate using those masks:

>>> coords_to_values_a = {(0, 0): 1, (1, 0): 4}
>>> masks_from_nodes_a = [node.masks(coords_to_values_a.keys()) for node in nodes]
>>> masked_factors_a = masked_factors(coords_to_values_a, masks_from_nodes_a)

>>> coords_to_values_b = {(0, 1): 2, (1, 1): 5}
>>> masks_from_nodes_b = [node.masks(coords_to_values_b.keys()) for node in nodes]
>>> masked_factors_b = masked_factors(coords_to_values_b, masks_from_nodes_b)

>>> coords_to_values_c = {(0, 2): 3}
>>> masks_from_nodes_c = [node.masks(coords_to_values_c.keys()) for node in nodes]
>>> masked_factors_c = masked_factors(coords_to_values_c, masks_from_nodes_c)

Each contributor then broadcasts all of its masked factors to every node, so every node receives all of the masked factors from all of the contributors:

>>> broadcast = [masked_factors_a, masked_factors_b, masked_factors_c]

Then, every node can locally compute its share of the overall result:

>>> result_share_at_node_0 = nodes[0].compute(signature, broadcast)
>>> result_share_at_node_1 = nodes[1].compute(signature, broadcast)
>>> result_share_at_node_2 = nodes[2].compute(signature, broadcast)

Finally, the result can be reconstructed via summation from the result shares received from the nodes:

>>> int(sum([result_share_at_node_0, result_share_at_node_1, result_share_at_node_2]))
26

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

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.

Related readings

About Nillion

Nillion is humanity’s first Blind Computer. It is powered by a decentralized network of nodes that enables “Blind Computation” through the coordination and orchestration of privacy enhancing technologies (PETs) such as multi-party computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proofs (ZKP). Nillion believes Blind Computation will become the internet’s base layer for all private data as PETs continue to mature. Nillion has attracted a notable initial cohort of Blind Computation builders across AI, DeFi, medical data, custody, wallets, global identity, messaging, and more.

The Nillion development company, Nilogy, was incubated by CoinList’s seed program. Nilogy’s Founding CTO was the Founding Engineer of Uber (Conrad Whelan), the Chief Strategy Officer was the Founding CMO of Hedera Hashgraph (Andrew Masanto), the Chief Business Officer is the Founder of Indiegogo (Slava Rubin), the General Counsel was the Associate General Counsel of Coinbase (Lindsay Danas Cohen), along with builders hailing from Consensys, LayerZero, Polygon and Google.

Learn more by visiting the Nillion website or following us on Twitter, Telegram or Discord.