tinynmc module

Minimal pure-Python implementation of a secure multi-party computation (MPC) protocol for evaluating arithmetic sum-of-products expressions via a non-interactive computation phase.

class tinynmc.tinynmc.node[source]

Bases: object

Data structure for maintaining the information associated with a node in a protocol instantiation.

Suppose that a protocol instance involves three contributors (parties submitting private input values) and three nodes (parties performing the computation). The node objects would be instantiated locally by each of the parties performing the computation.

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

Any sum-of-products expression that can be computed can be described by a signature: a list of integers in which each entry specifies the number of factors (i.e., multiplicands) in each term (i.e., addend of the overall summation). For example, suppose the expression to be computed is (1 * 2 * 3) + (4 * 5). This would correspond to the signature below because the term (1 * 2 * 3) has three factors and the term (4 * 5) has two factors.

>>> signature = [3, 2]

All contributors must agree on the signature, and the signature must be shared with the nodes. The preprocessing phase that the nodes must execute (using an existing MPC protocol that supports multiplication operations on secret-shared values, such as SPDZ) can be simulated using the preprocess function.

>>> preprocess(signature, nodes)

The contributors must also agree on which factors in the sum-of-products each of them is submitting to the overall computation. In this example, we assume that 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)).

Agreeing on the above, each contributor can then request from the nodes the multiplicative shares of the masks it must use to protect its values (organized by the coordinates of the inputs to which they correspond). Each node constructs responses to such requests using the node.masks method.

>>> 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]

>>> 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]

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

Each node can then mask its input values using the masks via the masked_factors function. This function organizes the process of masking the input values at each coordinate using the mask for that coordinate. The output of this function consists of the masked factors that are safe to broadcast to the nodes.

>>> masked_factors_a = masked_factors(coords_to_values_a, masks_from_nodes_a)
>>> masked_factors_b = masked_factors(coords_to_values_b, masks_from_nodes_b)
>>> masked_factors_c = masked_factors(coords_to_values_c, masks_from_nodes_c)

Then, each contributor broadcasts all of its masked factors to every node. Every node receives all the masked factors from all the contributors. Then, each node can locally perform its computation (using the node.compute method) to obtain its share of the overall result.

>>> broadcast = [masked_factors_a, masked_factors_b, masked_factors_c]
>>> 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 simple 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

correlate(signature, exponents, shares_)[source]

Generate masks for the given signature from the existing mask exponents. This method is used by the preprocess function to prepare the correlated masks and shares that are maintained by each node.

Parameters

signature (Sequence[int]) – Signature of the sum-of-products expression to be evaluated by the nodes.
exponents (Sequence[modulo]) – Mask exponents (one per term) to be used for constructing masks for contributed factors.
shares_ (Sequence[modulo]) – Additive shares of the overall mask for each term (to be stored locally by each node and used during the computation phase).

masks(coordinates_from_contributor)[source]

Return a dictionary mapping a set of (term_index, factor_index) coordinates to their corresponding masks.

Parameters: coordinates_from_contributor (Sequence[tuple[int, int]]) – Collection of coordinates corresponding to particular factors in an expression that are from an individual contributor.
Return type: dict[tuple[int, int], modulo]

compute(signature, masked_factors_from_contributors)[source]

Compute a secret share of the result of evaluating the sum-of-products expression.

Parameters

signature (Sequence[int]) – Signature of the sum-of-products expression to be evaluated by the nodes.
masked_factors_from_contributors (Sequence[dict[tuple[int, int], modulo]]) – Collection of mappings (one per contributor), where each mapping associates the coordinates of an expression with the masked factors for that coordinate received from a specific node.

tinynmc.tinynmc.preprocess(signature, nodes)[source]

Simulate a preprocessing phase for the supplied signature and collection of nodes.

Parameters

signature (Sequence[int]) – Signature of the sum-of-products expression to be evaluated by the nodes.
nodes (Sequence[node]) – Collection of nodes that will compute the sum-of-products expression.

In full implementations of a protocol instance, a scheme that supports multiplication operations involving secret-shared values (such as SPDZ) would be used to prepare the correlated exponent and mask shares across all nodes.

>>> nodes = [node(), node(), node()]
>>> signature = [1, 2]
>>> preprocess(signature, nodes)

After this function is executed, the supplied nodes are ready to respond to requests for masks from contributors.

tinynmc.tinynmc.masked_factors(coordinates_to_values, masks_from_nodes)[source]

Build up a dictionary that maps each coordinate to a value that is masked using the product of the masks (from all nodes) at that coordinate.

Parameters

coordinates_to_values (dict[tuple[int, int], int]) – Mapping from the coordinates of an expression to the corresponding values (all originating from one contributor).
masks_from_nodes (Iterable[dict[tuple[int, int], modulo]]) – Iterable of mappings (one per node), where each mapping associates the coordinates of an expression with the masks for that coordinate obtained from a specific node.

A contributor applies this method to their input values in order to prepare them for broadcast to the nodes. For example, suppose that there are three nodes and a contributor is supplying two of the factors in an expression with the signature below.

>>> nodes = [node(), node(), node()]
>>> signature = [1, 2]
>>> preprocess(signature, nodes)

The contributor would build up a mapping from the coordinates for which it is contributing values to the values themselves, and then would obtain the corresponding masks for those values from each of the nodes.

>>> coords_to_values = {(0, 0): 123, (1, 0): 456}
>>> masks_from_nodes = [node.masks(coords_to_values.keys()) for node in nodes]

Finally, the contributor would supply to this function both the mapping to its values and the mappings to the masks. This would yield the masked factors.

>>> masked_factors = masked_factors(coords_to_values, masks_from_nodes)

Return type: dict[tuple[int, int], modulo]