# Copyright 2021 National Technology & Engineering Solutions
# of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with NTESS,
# the U.S. Government retains certain rights in this software.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Functionality for creating, manipulating, and revealing shamir-shared secrets."""
from math import ceil
from random import randrange
import numpy
from cicada.arithmetic import Field
from cicada.communicator.interface import Communicator
from cicada.encoding import FixedPoint, Identity, Boolean
[docs]
class ShamirArrayShare(object):
"""Stores the local share of a Shamir-shared secret array.
Instances of :class:`ShamirArrayShare` should only be created using
:class:`ShamirBasicProtocolSuite` or :class:`ShamirProtocolSuite`.
"""
def __init__(self, storage):
self.storage = storage
def __repr__(self):
return f"cicada.shamir.ShamirArrayShare(storage={self._storage})" # pragma: no cover
def __getitem__(self, index):
return ShamirArrayShare(numpy.array(self._storage[index], dtype=self._storage.dtype)) # pragma: no cover
@property
def storage(self):
"""Private storage for the local share of a secret shared array.
Access is provided only for serialization and communication -
callers must use :class:`ShamirBasicProtocolSuite` or
:class:`ShamirProtocolSuite` to manipulate secret shares.
"""
return self._storage
@storage.setter
def storage(self, storage):
if not isinstance(storage, numpy.ndarray):
raise ValueError(f"Expected numpy.ndarray, got {type(storage)}.") # pragma: no cover
self._storage = numpy.array(storage, dtype=object)
[docs]
class ShamirBasicProtocolSuite(object):
"""Protocol suite implementing limited computation with Shamir-shared secrets.
:class:`ShamirBasicProtocolSuite` implements a limited set of operations
that can be performed on Shamir-shared secrets, chosen so that the minimum
number of shares :math:`k` needed to recover a secret is :math:`k <= n`,
where :math:`n` is the number of players.
If you need a full set of operations including multiplication, use
:class:`ShamirProtocolSuite` instead.
Note
----
Creating the protocol is a collective operation that *must*
be called by all players that are members of `communicator`.
Parameters
----------
communicator: :class:`cicada.communicator.interface.Communicator`, required
The communicator that this protocol will use for communication.
threshold: :class:`int`, required
The minimum number of shares :math:`k` needed to recover a secret,
where :math:`k <= n` and :math:`n` is the number of players.
seed: :class:`int`, optional
Seed used to initialize random number generators. For privacy, this
value should be different for each player. By default, the seed will
be chosen at random, and is guaranteed to be different even on forked
processes. If you specify `seed` yourself, the actual seed used will
be the sum of this value and the value of `seed_offset`.
seed_offset: :class:`int`, optional
Value added to the value of `seed`. This value defaults to the player's
rank.
order: :class:`int`, optional
Field size for storing encoded values. Defaults to the largest prime
less than :math:`2^{64}`.
encoding: :class:`object`, optional
Default encoding to use for operations that require encoding/decoding.
Uses an instance of :any:`FixedPoint` with 16 bits of
floating-point precision if :any:`None`.
indices: sequence of :class:`int`, optional
The :math:`x`-values where coefficients for secret shares generated by
this protocol are defined. The default is the integers :math:`[1, n]`
where :math:`n` is the number of players.
"""
def __init__(self, communicator, *, threshold, seed=None, seed_offset=None, order=None, encoding=None, indices=None):
if not isinstance(communicator, Communicator):
raise ValueError("A Cicada communicator is required.") # pragma: no cover
if threshold < 2:
raise ValueError("threshold must be >= 2") # pragma: no cover
if threshold > communicator.world_size:
raise ValueError("threshold must be <= world_size") # pragma: no cover
self._d = threshold-1
if seed is None:
seed = numpy.random.default_rng(seed=None).integers(low=0, high=2**63-1, endpoint=True)
else:
if seed_offset is None:
seed_offset = communicator.rank
seed += seed_offset
self._generator = numpy.random.default_rng(seed=seed)
if encoding is None:
encoding = FixedPoint()
if indices is None:
indices = numpy.array(communicator.ranks) + 1
self._communicator = communicator
self._field = Field(order=order)
self._encoding = encoding
self._indices = self._field(indices)
self._revealing_coef = self._lagrange_coef()
def _assert_binary_compatible(self, lhs, rhs, lhslabel, rhslabel):
self._assert_unary_compatible(lhs, lhslabel)
self._assert_unary_compatible(rhs, rhslabel)
if lhs.storage.shape != rhs.storage.shape:
raise ValueError(f"{lhslabel} and {rhslabel} must be the same shape, got {lhs.storage.shape} and {rhs.storage.shape} instead.") # pragma: no cover
def _assert_unary_compatible(self, share, label):
if not isinstance(share, ShamirArrayShare):
raise ValueError(f"{label} must be an instance of ShamirArrayShare, got {type(share)} instead.") # pragma: no cover
def _lagrange_coef(self, indices=None):
# Given a set of indices, it returns an array containing the lagrange coefficients
# with respect to each index given, keyed by those indices
from math import prod
if indices is None:
indices = self.indices
coefs = self.field.zeros_like(indices)
for i in numpy.arange(len(coefs)):
coefs[i]=prod([-indices[j]*pow(indices[i]-indices[j], self.field.order-2, self.field.order) for j in numpy.arange(len(coefs)) if indices[j] != indices[i]])%self.field.order
return coefs
def _require_encoding(self, encoding):
if encoding is None:
encoding = self._encoding
return encoding
[docs]
def add(self, lhs, rhs, *, encoding=None):
"""Privacy-preserving elementwise sum of arrays.
This method can be used to perform private-private, public-private,
and private-public addition. The result is the secret shared
elementwise sum of the operands. Note that public-public addition
isn't allowed, as it isn't privacy-preserving!
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public values to be added.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public values to be added.
encoding: :class:`object`, optional
Encodes public operands. The protocol's :attr:`encoding`
is used by default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared sum of `lhs` and `rhs`.
"""
encoding = self._require_encoding(encoding)
# Private-private addition.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
return self.field_add(lhs, rhs)
# Private-public addition.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
return self.field_add(lhs, encoding.encode(rhs, self.field))
# Public-private addition.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
return self.field_add(encoding.encode(lhs, self.field), rhs)
raise NotImplementedError(f"Privacy-preserving addition not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def bit_compose(self, operand):
"""Compose an array of secret-shared bits into an array of corresponding integer field values.
The result array will will have one fewer dimensions than the operand,
which must contain bits in big-endian order in its last dimension.
Note that the input must contain the field values :math:`0` and :math:`1`.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array containing bits to be composed.
Returns
-------
result: :class:`ShamirArrayShare`
Share of the resulting field values.
"""
self._assert_unary_compatible(operand, "operand")
result = numpy.empty(operand.storage.shape[:-1], dtype=object)
shift = numpy.power(2, numpy.arange(operand.storage.shape[-1], dtype=self.field.dtype)[::-1])
shifted = self.field.multiply(operand.storage, shift)
result = numpy.sum(shifted, axis=-1, out=result)
result %= self.field.order
return ShamirArrayShare(result)
@property
def communicator(self):
"""The :class:`~cicada.communicator.interface.Communicator` used by this protocol."""
return self._communicator
@property
def encoding(self):
"""Default encoding to use for operations that require encoding/decoding."""
return self._encoding # pragma: no cover
@property
def field(self):
"""Integer :any:`Field` used for arithmetic on and storage of secret shared values."""
return self._field
[docs]
def field_add(self, lhs, rhs):
"""Privacy-preserving elementwise sum of arrays.
This method can be used to perform private-private, public-private,
and private-public addition. The result is the secret shared
elementwise sum of the operands. Note that public-public addition
isn't allowed, as it isn't privacy-preserving!
Unlike :meth:`add`, :meth:`field_add` only operates on field
values, no encoding is performed on its inputs.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be added.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be added.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared sum of `lhs` and `rhs`.
"""
# Private-private addition.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
return ShamirArrayShare(self.field.add(lhs.storage, rhs.storage))
# Public-private addition.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
return ShamirArrayShare(self.field.add(lhs, rhs.storage))
# Private-public addition.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
return ShamirArrayShare(self.field.add(lhs.storage, rhs))
raise NotImplementedError(f"Privacy-preserving subtraction not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def field_subtract(self, lhs, rhs):
"""Privacy-preserving elementwise difference of arrays.
This method can be used to perform private-private, public-private, and
private-public subtraction. The result is the secret shared
elementwise difference of the operands. Note that public-public
subtraction isn't allowed, as it isn't privacy-preserving!
Unlike :meth:`subtract`, :meth:`field_subtract` only operates on field
values, no encoding is performed on its inputs.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be subtracted.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be subtracted.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared difference of `lhs` and `rhs`.
"""
# Private-private subtraction.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
return ShamirArrayShare(self.field.subtract(lhs.storage, rhs.storage))
# Public-private subtraction.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
return ShamirArrayShare(self.field.subtract(lhs, rhs.storage))
# Private-public subtraction.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
return ShamirArrayShare(self.field.subtract(lhs.storage, rhs))
raise NotImplementedError(f"Privacy-preserving subtraction not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
@property
def indices(self):
"""Return the :math:`x`-values used by this protocol to reveal secrets.
Returns
-------
indices: :class:`numpy.ndarray`
One dimensional array of :math:`x`-values where coefficients
for secret shares generated by this protocol are defined.
"""
return self._indices
[docs]
def negative(self, operand):
"""Privacy-preserving elementwise additive inverse of a secret shared array.
Returns the additive inverse of a secret shared array
in the context of the underlying finite field. Explicitly, this
function returns a same shape array which, when added
elementwise with `operand`, will return a same shape array comprised
entirely of zeros.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared operand to be additively inverted.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise additive inverse of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
return self.field_subtract(self.field.full_like(operand.storage, self.field.order), operand)
[docs]
def reshare(self, operand):
"""Privacy-preserving re-randomization of a secret shared array.
This method returns a new set of secret shares that contain different
random values than the input but represent the same secret value.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared operand which should be re-randomized.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared, re-randomized version of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
dst=self.communicator.ranks
ldst=len(dst)
recshares = []
for i in dst:
recshares.append(self.share(src=i, secret=operand.storage, shape=operand.storage.shape, encoding=Identity()))
acc = numpy.zeros(operand.storage.shape, dtype=self.field.dtype)
for i, s in enumerate(recshares):
acc += self._revealing_coef[i]*s.storage
acc %= self.field.order
return ShamirArrayShare(acc)
[docs]
def reveal(self, share, *, dst=None, encoding=None):
"""Reveals a secret shared value to a subset of players.
Note
----
This is a collective operation that *must* be called by all players
that are members of :attr:`communicator`, whether they are receiving
the revealed secret or not.
Parameters
----------
share: :class:`ShamirArrayShare`, required
The local share of the secret to be revealed.
dst: sequence of :class:`int`, optional
List of players who will receive the revealed secret. If :any:`None`
(the default), the secret will be revealed to all players.
encoding: :class:`object`, optional
Encoding used to extract the revealed secret from field values. The
protocol's default encoding will be used if `None`.
Returns
-------
value: :class:`numpy.ndarray` or :any:`None`
The revealed secret, if this player is a member of `dst`, or :any:`None`.
"""
if not isinstance(share, ShamirArrayShare):
raise ValueError("share must be an instance of ShamirArrayShare.") # pragma: no cover
# Identify who will be receiving shares.
if dst is None:
dst = self.communicator.ranks
encoding = self._require_encoding(encoding)
src = self.communicator.ranks
n=len(src)
if n == len(self._indices):
revealing_coef = self._revealing_coef
else:
revealing_coef = None
# Send data to the other players.
secret = None
for recipient in dst:
received_shares = self.communicator.gatherv(src=src, value=share, dst=recipient)
if received_shares:
received_storage = numpy.array([x.storage for x in received_shares], dtype=self.field.dtype)
if self.communicator.rank == recipient:
if revealing_coef is None:
revealing_coef = self._lagrange_coef([self._indices[x] for x in src])
secret = []
for index in numpy.ndindex(received_storage[0].shape):
secret.append(self._field.sum(numpy.array([self._field.multiply(numpy.array(revealing_coef[i], dtype=object), numpy.array(received_storage[i][index], dtype=object)) for i in range(len(revealing_coef))], dtype=object)))
if secret is None:
return secret
else:
ret = numpy.array([x%self.field.order for x in secret], dtype=self.field.dtype).reshape(share.storage.shape)
return encoding.decode(ret, self.field)
[docs]
def share(self, *, src, secret, shape, encoding=None):
"""Convert an array of scalars to an additive secret share.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
src: :class:`int`, required
The player providing the private array to be secret shared.
secret: :class:`numpy.ndarray` or :any:`None`, required
The secret array to be shared. This value is ignored for all
players except `src`.
shape: :class:`tuple`, required
The shape of the secret. Note that all players must specify the
same shape.
encoding: :class:`object`, optional
Encoding used to convert `secret` into field values. The protocol's
default encoding will be used if `None`.
Returns
-------
share: :class:`ShamirArrayShare`
The local share of the secret shared array.
"""
if not isinstance(shape, tuple):
shape = (shape,)
encoding = self._require_encoding(encoding)
dst=self.communicator.ranks
ldst=len(dst)
shares = []
sharesn = numpy.zeros(shape+(ldst,))
if self.communicator.rank == src:
if not isinstance(secret, numpy.ndarray):
raise ValueError("secret must be an instance of numpy.ndarray.") # pragma: no cover
if secret.shape != shape:
raise ValueError(f"Expected secret.shape {shape}, got {secret.shape} instead.") # pragma: no cover
secret = encoding.encode(secret, self.field)
coef = self.field.uniform(size=shape+(self._d,), generator=self._generator)
for index in numpy.ndindex(shape):
for x in self._indices:
shares.append((numpy.dot(numpy.power(numpy.full((self._d,), x),numpy.arange(1, self._d+1)), coef[index])+secret[index])%self.field.order)
sharesn = numpy.array(shares, dtype=self.field.dtype).reshape(shape+(ldst,)).T
share = numpy.array(self.communicator.scatter(src=src, values=sharesn), dtype=self.field.dtype).T
return ShamirArrayShare(share)
[docs]
def subtract(self, lhs, rhs, *, encoding=None):
"""Privacy-preserving elementwise difference of arrays.
This method can be used to perform private-private, public-private, and
private-public addition. The result is the secret shared elementwise
difference of the operands. Note that public-public subtraction isn't
allowed, as it isn't privacy-preserving!
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public values to be subtracted.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public values to be subtracted.
encoding: :class:`object`, optional
Encodes public operands. The protocol's :attr:`encoding`
is used by default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared difference of `lhs` and `rhs`.
"""
encoding = self._require_encoding(encoding)
# Private-private subtraction.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
return self.field_subtract(lhs, rhs)
# Private-public subtraction.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
return self.field_subtract(lhs, encoding.encode(rhs, self.field))
# Public-private subtraction.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
return self.field_subtract(encoding.encode(lhs, self.field), rhs)
raise NotImplementedError(f"Privacy-preserving subtraction not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def sum(self, operand):
"""Privacy-preserving sum of a secret shared array's elements.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array containing elements to be summed.
Returns
-------
value: :class:`ShamirArrayShare`
Secret-shared sum of `operand`'s elements.
"""
self._assert_unary_compatible(operand, "operand")
return ShamirArrayShare(self.field.sum(operand.storage))
@property
def threshold(self):
"""Return the threshold (minimum number of players required to reveal a secret)."""
return self._d + 1
def _verify_storage(self, operand):
"""Verify the storage in a secret share.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array to be verified.
Returns
-------
value: :class:`ShamirArrayShare`
The secret shared array.
Raises
------
:class:`ValueError`
If `operand` can't be verified.
"""
self._assert_unary_compatible(operand, "operand")
self.field._verify(operand.storage)
return operand
[docs]
class ShamirProtocolSuite(ShamirBasicProtocolSuite):
"""Protocol suite implementing a full set of operations on Shamir-shared secrets.
:class:`ShamirProtocolSuite` provides a complete set of operations on
Shamir-shared secrets including multiplication and logical comparisons.
However, in order to do this, the minimum number of shares :math:`k` needed
to recover a secret must be constrained to :math:`k <= \\frac{n+1}{2}`, where
:math:`n` is the number of players.
If you don't need multiplication or logical comparisons, and do need a less
restrictive threshold :math:`k`, use :class:`ShamirBasicProtocolSuite`
instead.
Multiplication is based on "Simplified VSS and fast-track multiparty
computations with applications to threshold cryptography" by Gennaro,
Rabin, and Rabin, which provides semi-honest security and does not require
Beaver triples or other offline computation.
Comparisons are based on "Multiparty computation for interval, equality,
and comparison without bit-decomposition protocol" by Nishide and Ohta, and
inherit the semi-honest security model from multiplication.
Note
----
Creating the protocol is a collective operation that *must*
be called by all players that are members of `communicator`.
Parameters
----------
communicator: :class:`cicada.communicator.interface.Communicator`, required
The communicator that this protocol will use for communication.
threshold: :class:`int`, required
The minimum number of shares :math:`k` needed to recover a secret,
where :math:`k <= \\frac{n+1}{2}` and :math:`n` is the number of players.
seed: :class:`int`, optional
Seed used to initialize random number generators. For privacy, this
value should be different for each player. By default, the seed will
be chosen at random, and is guaranteed to be different even on forked
processes. If you specify `seed` yourself, the actual seed used will
be the sum of this value and the value of `seed_offset`.
seed_offset: :class:`int`, optional
Value added to the value of `seed`. This value defaults to the player's
rank.
order: :class:`int`, optional
Field size for storing encoded values. Defaults to the largest prime
less than :math:`2^{64}`.
encoding: :class:`object`, optional
Default encoding to use for operations that require encoding/decoding.
Uses an instance of :any:`FixedPoint` with 16 bits of
floating-point precision if :any:`None`.
indices: sequence of :class:`int`, optional
The :math:`x`-values where coefficients for secret shares generated by
this protocol are defined. The default is the integers :math:`[1, n]`
where :math:`n` is the number of players.
"""
def __init__(self, communicator, *, threshold, seed=None, seed_offset=None, order=None, encoding=None, indices=None):
super().__init__(communicator=communicator, threshold=threshold, seed=seed, seed_offset=seed_offset, order=order, encoding=encoding, indices=indices)
max_threshold = (communicator.world_size+1) // 2
if threshold > max_threshold:
min_world_size = (2 * threshold) - 1
raise ValueError(f"threshold must be <= {max_threshold}, or world_size must be >= {min_world_size}")
[docs]
def absolute(self, operand):
"""Elementwise absolute value of a secret shared array.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared value to which the absolute value function should be applied.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise absolute value of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
ltz = self.less_zero(operand)
nltz = self.logical_not(ltz)
addinvop = self.negative(operand)
ltz_parts = self.field_multiply(ltz, addinvop)
nltz_parts = self.field_multiply(nltz, operand)
return self.field_add(ltz_parts, nltz_parts)
[docs]
def bit_decompose(self, operand, bits=None):
"""Decompose operand into shares of its bitwise representation.
The result array will have one more dimension than the operand,
containing the returned bits in big-endian order. Note that the
results will contain the field values :math:`0` and :math:`1`.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array containing values to be decomposed.
bits: :class:`int`, optional
The number of rightmost bits in each value to extract. Defaults to
all bits (i.e. the number of bits used for storage by the protocol's
:attr:`field`.
Returns
-------
result: :class:`ShamirArrayShare`
Share of the bit decomposed secret.
"""
self._assert_unary_compatible(operand, "operand")
if bits is None:
bits = self.field.bits
list_o_bits = []
two_inv = numpy.array(pow(2, self.field.order-2, self.field.order), dtype=self.field.dtype)
for element in operand.storage.flat: # Iterates in "C" order.
loopop = ShamirArrayShare(numpy.array(element, dtype=self.field.dtype))
elebits = []
for i in range(bits):
elebits.append(self._lsb(loopop))
loopop = self.field_subtract(loopop, elebits[-1])
loopop = ShamirArrayShare(self.field.multiply(loopop.storage, two_inv))
list_o_bits.append(elebits[::-1])
return ShamirArrayShare(numpy.array([x.storage for y in list_o_bits for x in y]).reshape(operand.storage.shape+(bits,)))
[docs]
def divide(self, lhs, rhs, *, encoding=None, rmask=None, mask1=None, rem1=None, mask2=None, rem2=None, mask3=None, rem3=None):
"""Privacy-preserving elementwise division of arrays.
This method can be used to perform private-private and
private-public division. The result is the secret shared
elementwise quotient of the operands.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared value to be divided.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be divided.
encoding: :class:`object`, optional
Encodes public operands and determines the number of bits to
shift right from intermediate results. The protocol's
:attr:`encoding` is used by default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared quotient of `lhs` and `rhs`.
"""
encoding = self._require_encoding(encoding)
# Private-private division.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
zshare = self.share(src=0, secret=numpy.zeros_like(rhs.storage), shape=rhs.storage.shape)
check = self.reveal(self.equal(rhs, zshare), encoding=Boolean())
if not len(check.shape):
if check:
raise ZeroDivisionError()
else:
if check.any():
raise ZeroDivisionError()
oops = True
while oops:
if rmask is None:
_, rmask = self.random_bitwise_secret(bits=encoding.precision, shape=rhs.storage.shape)
else:
oops = False
if not len(rhs.storage.shape):
if self.reveal(self.equal(rmask, zshare), encoding=Boolean()):
rmask = None
else:
if self.reveal(self.equal(rmask, zshare), encoding=Boolean()).any():
rmask = None
rhsmasked = self.field_multiply(rmask, rhs)
if mask1 != None and rem1 != None:
rhsmasked = self.right_shift(rhsmasked, bits=encoding.precision, trunc_mask=mask1, rem_mask=rem1)
else:
rhsmasked = self.right_shift(rhsmasked, bits=encoding.precision)
revealrhsmasked = self.reveal(rhsmasked, encoding=encoding)
if mask2 != None and rem2 != None:
almost_there = self.right_shift(self.field_multiply(lhs, rmask), bits=encoding.precision, trunc_mask=mask2, rem_mask=rem2)
else:
almost_there = self.right_shift(self.field_multiply(lhs, rmask), bits=encoding.precision)
divisor = encoding.encode(numpy.array(1 / revealrhsmasked), self.field)
quotient = ShamirArrayShare(self.field.multiply(almost_there.storage, divisor))
if mask3 != None and rem3 != None:
return self.right_shift(quotient, bits=encoding.precision, trunc_mask=mask3, rem_mask=rem3)
else:
return self.right_shift(quotient, bits=encoding.precision)
# Private-public division.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
if rhs == numpy.zeros_like(rhs):
raise ZeroDivisionError()
divisor = encoding.encode(numpy.array(1 / rhs), self.field)
result = self.field_multiply(lhs, divisor)
result = self.right_shift(result, bits=encoding.precision)
return result
raise NotImplementedError(f"Privacy-preserving division not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def dot(self, lhs, rhs, *, encoding=None):
"""Privacy-preserving dot product of two secret shared vectors.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared vector.
rhs: :class:`ShamirArrayShare`, required
Secret shared vector.
encoding: :class:`object`, optional
Determines the number of bits to truncate from intermediate
results. The protocol's :attr:`encoding` is used by default if
:any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared dot product of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
encoding = self._require_encoding(encoding)
# The following implementation is efficient because
# it uses the distributive property so that only a
# single right shift is performed, regardless of
# input shape.
# result = self.field_dot(lhs, rhs)
# result = self.right_shift(result, bits=encoding.precision)
# return result
# The following folklore implementation is even better because
# reasons.
count = ceil((self.communicator.world_size - 1) / 2)
x = lhs.storage
y = rhs.storage
z = numpy.dot(x, y)
xy = numpy.array((z) % self.field.order, dtype=self.field.dtype)
lc = self._lagrange_coef()
dubdeg = numpy.zeros((len(lc),)+xy.shape, dtype=self.field.dtype)
for i, src in enumerate(self.communicator.ranks):
dubdeg[i]=self.share(src=src, secret=xy, shape=xy.shape, encoding=Identity()).storage #transpose
sharray = numpy.zeros(xy.shape, dtype=self.field.dtype)
for i in range(len(self.communicator.ranks)):
sharray = numpy.array((sharray + dubdeg[i]*lc[i]) % self.field.order, dtype=self.field.dtype)
return self.right_shift(ShamirArrayShare(sharray), bits=encoding.precision)
[docs]
def equal(self, lhs, rhs):
"""Elementwise probabilistic equality comparison between secret shared arrays.
The result is the secret shared elementwise comparison `lhs` == `rhs`. Note
that the results will contain the field values :math:`0` and :math:`1`.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared array to be compared.
rhs: :class:`ShamirArrayShare`, required
Secret shared array to be compared.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared result from comparing `lhs` == `rhs` elementwise.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
diff = self.field_subtract(lhs, rhs)
return self.logical_not(self.field_power(diff, self.field.order - 1))
[docs]
def field_dot(self, lhs, rhs):
"""Privacy-preserving dot product of two secret shared vectors.
Unlike :meth:`dot`, :meth:`field_dot` only operates on field values,
no right shift is performed on the results.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared vector.
rhs: :class:`ShamirArrayShare`, required
Secret shared vector.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared dot product of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
result = self.field_multiply(lhs, rhs)
result = self.sum(result)
return result
[docs]
def field_multiply(self, lhs, rhs):
"""Privacy-preserving elementwise multiplication of arrays.
This method can be used to perform private-private, public-private, and
private-public multiplication. The result is the secret shared
elementwise sum of the operands. Note that public-public
multiplication isn't allowed, as it isn't privacy-preserving!
Unlike :meth:`multiply`, :meth:`field_multiply` only operates on field
values, no encoding is performed on its inputs, and no right shift
is performed on the results.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be multiplied.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be multiplied.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared product of `lhs` and `rhs`.
"""
# Private-private multiplication.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
count = ceil((self.communicator.world_size - 1) / 2)
x = lhs.storage
y = rhs.storage
xy=self._field.multiply(x,y)
lc = self._lagrange_coef()
dubdeg = numpy.zeros((len(lc),)+lhs.storage.shape, dtype=self.field.dtype)
for i, src in enumerate(self.communicator.ranks):
dubdeg[i]=self.share(src=src, secret=xy, shape=xy.shape, encoding=Identity()).storage #transpose
sharray = self._field.full_like(lhs.storage, 0)
for i in range(len(self.communicator.ranks)):
sharray = self._field.add(sharray, self._field.multiply(dubdeg[i], numpy.array(lc[i], dtype=self.field.dtype)))
return ShamirArrayShare(sharray)
# Public-private multiplication.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
return ShamirArrayShare(self.field.multiply(lhs, rhs.storage))
# Private-public multiplication.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
return ShamirArrayShare(self.field.multiply(lhs.storage, rhs))
raise NotImplementedError(f"Privacy-preserving multiplication not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def field_power(self, lhs, rhs):
"""Privacy-preserving elementwise exponentiation.
Raises secret shared array values to public integer values. Unlike :meth:`power`,
:meth:`field_power` only operates on field values, no right shift is performed on the
results.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared values which iwll be raised to a power.
rhs: :class:`int` or integer :class:`numpy.ndarray`, required
Public integer power(s) to which each element in `lhs` will be raised.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared result of raising `lhs` to the power(s) in `rhs`.
"""
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, (numpy.ndarray, int)):
if isinstance(rhs, int):
rhs = self.field.full_like(lhs.storage, rhs)
ans = []
for lhse, rhse in numpy.nditer([lhs.storage, rhs], order="C", flags=(["refs_ok"])):
rhsbits = [int(x) for x in bin(int(rhse))[2:]][::-1]
tmp = ShamirArrayShare(lhse)
it_ans = self.share(src = 0, secret=self.field.full_like(lhse, 1), shape=lhse.shape, encoding=Identity())
limit = len(rhsbits)-1
for i, bit in enumerate(rhsbits):
if bit:
it_ans = self.field_multiply(it_ans, tmp)
if i < limit:
tmp = self.field_multiply(tmp,tmp)
ans.append(it_ans)
return ShamirArrayShare(numpy.array([x.storage for x in ans], dtype=self.field.dtype).reshape(lhs.storage.shape, order="C"))
raise NotImplementedError(f"Privacy-preserving exponentiation not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def floor(self, operand, *, encoding=None):
"""Privacy-preserving elementwise floor of encoded, secret-shared arrays.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared values to which floor should be applied.
encoding: :class:`object`, optional
Determines the number of fractional bits used for encoded values.
The protocol's :attr:`encoding` is used by default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared floor of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
encoding = self._require_encoding(encoding)
one = self.share(src=0, secret=self.field.full_like(operand.storage, 2**encoding.precision), shape=operand.storage.shape, encoding=Identity())
shift_op = self.field.full_like(operand.storage, 2**encoding.precision)
pl2 = self.field.full_like(operand.storage, self.field.order-1)
abs_op = self.absolute(operand)
frac_bits = encoding.precision
lsbs = self.bit_decompose(abs_op, bits=encoding.precision)
lsbs_composed = self.bit_compose(lsbs)
lsbs_inv = self.negative(lsbs_composed)
two_lsbs = ShamirArrayShare(self.field.multiply(lsbs_composed.storage, self.field.full_like(lsbs_composed.storage, 2)))
ltz = self.less_zero(operand)
ones2sub = ShamirArrayShare(self.field.multiply(self.field_power(lsbs_composed, pl2).storage, shift_op))
sel_2_lsbs = self.field_multiply(self.field_subtract(two_lsbs, ones2sub), ltz)
return self.field_add(self.field_add(sel_2_lsbs, lsbs_inv), operand)
[docs]
def less(self, lhs, rhs):
r"""Privacy-preserving elementwise less-than comparison.
The result is the secret shared elementwise comparison :math:`lhs \lt rhs`.
Note that the results will contain the field values :math:`0` or
:math:`1`, which do not require decoding if revealed.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared values to be compared.
rhs: :class:`ShamirArrayShare`, required
Secret shared values to be compared.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared comparison :math:`lhs \lt rhs`.
"""
one = self.field.full_like(lhs.storage, 1)
two = self.field.full_like(lhs.storage, 2)
twolhs = self.field_multiply(two, lhs)
tworhs = self.field_multiply(two, rhs)
diff = self.field_subtract(lhs, rhs)
twodiff = self.field_multiply(two, diff)
w = self.field_subtract(one, self._lsb(twolhs))
x = self.field_subtract(one, self._lsb(tworhs))
y = self.field_subtract(one, self._lsb(twodiff))
wxorx = self.logical_xor(w,x)
notwxorx = self.field_subtract(one, wxorx)
xwxorx = self.field_multiply(x, wxorx)
noty = self.field_subtract(one, y)
notwxorxnoty = self.field_multiply(notwxorx, noty)
return self.field_add(xwxorx, notwxorxnoty)
[docs]
def less_zero(self, operand):
r"""Privacy-preserving elementwise less-than-zero comparison.
The result is the secret shared elementwise comparison :math:`operand \lt 0`.
Note that the results will contain the field values :math:`0` or
:math:`1`, which do not require decoding if revealed.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared values to be compared.
rhs: :class:`ShamirArrayShare`, required
Secret shared values to be compared.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared comparison :math:`operand \lt 0`.
"""
self._assert_unary_compatible(operand, "operand")
two = self.field.full_like(operand.storage, 2)
result = self.field_multiply(two, operand)
return self._lsb(result)
[docs]
def logical_and(self, lhs, rhs):
"""Privacy-preserving elementwise logical AND of secret shared arrays.
The operands *must* contain the field values :math:`0` or :math:`1`.
The result will be the secret shared elementwise logical AND of `lhs`
and `rhs`, and will also contain the field values :math:`0` or
:math:`1`, which do not require decoding if revealed.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared array for logical AND.
rhs: :class:`ShamirArrayShare`, required
Secret shared array for logical AND.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise logical AND of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
return self.field_multiply(lhs, rhs)
[docs]
def logical_not(self, operand):
"""Privacy-preserving elementwise logical NOT.
The operand *must* contain the field values :math:`0` or :math:`1`.
The result will be the secret shared elementwise logical NOT of
`operand`, and will also contain the field values :math:`0` or
:math:`1`, which do not require decoding if revealed.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array for logical NOT.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise logical NOT of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
return self.field_subtract(self.field.ones_like(operand.storage), operand)
[docs]
def logical_or(self, lhs, rhs):
"""Privacy-preserving elementwise logical OR of secret shared arrays.
The operands *must* contain the field values :math:`0` or :math:`1`.
The result will be the secret shared elementwise logical OR of `lhs`
and `rhs`, and will also contain the field values :math:`0` or
:math:`1`, which do not require decoding if revealed.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared array for logical OR.
rhs: :class:`ShamirArrayShare`, required
Secret shared array for logical OR.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise logical OR of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
total = self.field_add(lhs, rhs)
product = self.field_multiply(lhs, rhs)
return self.field_subtract(total, product)
[docs]
def logical_xor(self, lhs, rhs):
"""Privacy-preserving elementwise logical XOR of secret shared arrays.
The operands *must* contain the field values :math:`0` or :math:`1`.
The result will be the secret shared elementwise logical XOR of `lhs`
and `rhs`, and will also contain the field values :math:`0` or
:math:`1`, which do not require decoding if revealed.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared array for logical XOR.
rhs: :class:`ShamirArrayShare`, required
Secret shared array for logical XOR.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise logical XOR of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
total = self.field_add(lhs, rhs)
product = self.field_multiply(lhs, rhs)
twice_product = self.field_multiply(self.field(2), product)
return self.field_subtract(total, twice_product)
def _lsb(self, operand):
"""Return the elementwise least significant bit of a secret shared array.
When revealed, the result will contain the values `0` or `1`, which do
not need to be decoded.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array from which the least significant bits will be extracted
Returns
-------
lsb: :class:`ShamirArrayShare`
Additive shared array containing the elementwise least significant
bits of `operand`.
"""
one = numpy.array(1, dtype=self.field.dtype)
lop = ShamirArrayShare(storage = operand.storage.flatten())
tmpBW, tmp = self.random_bitwise_secret(bits=self.field.bits, shape=lop.storage.shape)
maskedlop = self.field_add(lop, tmp)
c = self.reveal(maskedlop, encoding=Identity())
comp_result = self._public_bitwise_less_than(lhspub=c, rhs=tmpBW)
c = (c % 2)
c0xr0 = numpy.empty(c.shape, dtype = self.field.dtype)
for i, lc in enumerate(c):
if lc:
c0xr0[i] = self.field_subtract(lhs=one, rhs=ShamirArrayShare(numpy.array(tmpBW.storage[i][-1], dtype=self.field.dtype))).storage
else:
c0xr0[i] = tmpBW.storage[i][-1]
c0xr0 = ShamirArrayShare(c0xr0)
result = self.field_multiply(lhs=comp_result, rhs=c0xr0)
result = ShamirArrayShare(storage=self.field.multiply(lhs=self.field.full_like(result.storage, 2), rhs=result.storage))
result = self.field_subtract(lhs=c0xr0, rhs=result)
result = self.field_add(lhs=comp_result, rhs=result)
return ShamirArrayShare(result.storage.reshape(operand.storage.shape))
[docs]
def matvec(self, lhs, rhs, *, encoding=None):
"""Privacy-preserving product of a matrix and a vector.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be multiplied.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be multiplied.
encoding: :class:`object`, optional
Encodes public operands and determines the number of bits to shift
right the results. The protocol's :attr:`encoding` is used by
default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared product of `lhs` and `rhs`.
"""
encoding = self._require_encoding(encoding)
# Private-private matrix-vector multiplication.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
lshape = lhs.storage.shape
rshape = rhs.storage.shape
if lshape[1] != rshape[0]:
raise ValueError("Incompatible shapes of operands for this operation: got {lshape} and {rshape}.")
if len(lshape) != 2:
raise ValueError("Incompatible shapes of operands for this operation: got {lshape} and lhs must be 2d.")
result = ShamirArrayShare(numpy.zeros((lshape[0],)))
for j in range(lshape[0]):
x = lhs.storage[j]
y = rhs.storage
z = numpy.dot(x, y)
xy = numpy.array((z) % self.field.order, dtype=self.field.dtype)
lc = self._lagrange_coef()
dubdeg = numpy.zeros((len(lc),)+xy.shape, dtype=self.field.dtype)
for i, src in enumerate(self.communicator.ranks):
dubdeg[i]=self.share(src=src, secret=xy, shape=xy.shape, encoding=Identity()).storage #transpose
sharray = numpy.zeros(xy.shape, dtype=self.field.dtype)
for i in range(len(self.communicator.ranks)):
sharray = numpy.array((sharray + dubdeg[i]*lc[i]) % self.field.order, dtype=self.field.dtype)
result.storage[j] = self.right_shift(ShamirArrayShare(sharray), bits=encoding.precision).storage
return result
# Private-public matrix-vector multiplication.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
lshape = lhs.storage.shape
rshape = rhs.shape
if lshape[1] != rshape[0]:
raise ValueError("Incompatible shapes of operands for this operation: got {lshape} and {rshape}.")
if len(lshape) != 2:
raise ValueError("Incompatible shapes of operands for this operation: got {lshape} and lhs must be 2d.")
result = ShamirArrayShare(numpy.zeros((lshape[0],)))
for i in range(lshape[0]):
x = lhs.storage[i]
y = encoding.encode(rhs, self.field)
z = numpy.dot(x, y)
xy = numpy.array((z) % self.field.order, dtype=self.field.dtype)
result.storage[i] = self.right_shift(ShamirArrayShare(xy), bits=encoding.precision).storage
return result
# Public-private matrix-vector multiplication.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
result = self.field_multiply(encoding.encode(lhs, self.field), rhs)
result = self.right_shift(result, bits=encoding.precision)
lshape = lhs.shape
rshape = rhs.storage.shape
if lshape[1] != rshape[0]:
raise ValueError("Incompatible shapes of operands for this operation: got {lshape} and {rshape}.")
if len(lshape) != 2:
raise ValueError("Incompatible shapes of operands for this operation: got {lshape} and lhs must be 2d.")
result = ShamirArrayShare(numpy.zeros((lshape[0],)))
for i in range(lshape[0]):
x = encoding.encode(lhs[i], self.field)
y = rhs.storage
z = numpy.dot(x, y)
xy = numpy.array((z) % self.field.order, dtype=self.field.dtype)
result.storage[i] = self.right_shift(ShamirArrayShare(xy), bits=encoding.precision).storage
return result
raise NotImplementedError(f"Privacy-preserving multiplication not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
[docs]
def maximum(self, lhs, rhs):
"""Privacy-preserving elementwise maximum of secret shared arrays.
The result is the secret shared elementwise maximum of the operands.
Note: the magnitude of the field elements should be less than one
quarter of the field order for this method to be accurate in general.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared operand.
rhs: :class:`ShamirArrayShare`, required
Secret shared operand.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise maximum of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
max_share = self.field_add(self.field_add(lhs, rhs), self.absolute(self.field_subtract(lhs, rhs)))
shift_right = self.field.full_like(lhs.storage, pow(2, self.field.order-2, self.field.order))
max_share = self.field_multiply(max_share, shift_right)
return max_share
[docs]
def minimum(self, lhs, rhs):
"""Privacy-preserving elementwise minimum of secret shared arrays.
The result is the secret shared elementwise minimum of the operands.
Note: the magnitude of the field elements should be less than one
quarter of the field order for this method to be accurate in general.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared operand.
rhs: :class:`ShamirArrayShare`, required
Secret shared operand.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise minimum of `lhs` and `rhs`.
"""
self._assert_binary_compatible(lhs, rhs, "lhs", "rhs")
diff = self.field_subtract(lhs, rhs)
abs_diff = self.absolute(diff)
min_share = self.field_subtract(self.field_add(lhs, rhs), abs_diff)
shift_right = self.field.full_like(lhs.storage, pow(2, self.field.order-2, self.field.order))
min_share = self.field_multiply(min_share, shift_right)
return min_share
[docs]
def multiplicative_inverse(self, operand):
"""Privacy-preserving elementwise multiplicative inverse of a secret shared array.
Returns the multiplicative inverse of a secret shared array
in the context of the underlying finite field. Explicitly, this
function returns a same shape array which, when multiplied
elementwise with `operand`, will return a same shape array comprised
entirely of ones, assuming `operand` is entirely non-trivial elements.
This function does not take into account any field-external symantics.
There is a potential for information leak here if `operand` contains any
zero elements, that will be revealed. There is a small probability,
2^-operand.storage.size, for this approach to fail by zero being randomly
generated by the parties as the mask.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared operand to be multiplicatively inverted.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise multiplicative inverse of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
mask = self.field_uniform(shape=operand.storage.shape)
masked_op = self.field_multiply(mask, operand)
revealed_masked_op = self.reveal(masked_op, encoding=Identity())
nppowmod = numpy.vectorize(lambda a, b, c: pow(int(a), int(b), int(c)), otypes=[self.field.dtype])
inv = numpy.array(nppowmod(revealed_masked_op, self.field.order-2, self.field.order), dtype=self.field.dtype)
op_inv_share = self.field.multiply(inv, mask.storage)
return ShamirArrayShare(op_inv_share)
[docs]
def multiply(self, lhs, rhs, *, encoding=None):
"""Privacy-preserving elementwise multiplication of arrays.
This method can be used to perform private-private, public-private, and
private-public multiplication. The result is the secret shared
elementwise sum of the operands. Note that public-public
multiplication isn't allowed, as it isn't privacy-preserving!
Unlike :meth:`field_multiply`, :meth:`multiply` is encoding aware:
encoding is performed on its public inputs, and the results are
shifted right to produce correct results when decoded.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be multiplied.
rhs: :class:`ShamirArrayShare` or :class:`numpy.ndarray`, required
Secret shared or public value to be multiplied.
encoding: :class:`object`, optional
Encodes public operands and determines the number of bits to shift
right the results. The protocol's :attr:`encoding` is used by
default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared product of `lhs` and `rhs`.
"""
encoding = self._require_encoding(encoding)
# Private-private multiplication.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, ShamirArrayShare):
result = self.field_multiply(lhs, rhs)
result = self.right_shift(result, bits=encoding.precision)
return result
# Private-public multiplication.
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
result = self.field_multiply(lhs, encoding.encode(rhs, self.field))
result = self.right_shift(result, bits=encoding.precision)
return result
# Public-private multiplication.
if isinstance(lhs, numpy.ndarray) and isinstance(rhs, ShamirArrayShare):
result = self.field_multiply(encoding.encode(lhs, self.field), rhs)
result = self.right_shift(result, bits=encoding.precision)
return result
raise NotImplementedError(f"Privacy-preserving multiplication not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
# def pade_approx(self, func, operand,*, encoding=None, center=0, degree=12, scale=3):
# """Return the pade approximation of `func` sampled with `operand`.
#
# Note
# ----
# This is a collective operation that *must* be called
# by all players that are members of :attr:`communicator`.
#
# Parameters
# ----------
# func: callable object, required
# The function to be approximated via the pade method.
# operand: :class:`ShamirArrayShare`, required
# Secret-shared values where `func` should be evaluated.
# center: :class:`float`, optional
# The value at which the approximation should be centered. Sample
# errors will be larger the further they are from this point.
#
# Returns
# -------
# result: :class:`ShamirArrayShare`
# Secret shared result of evaluating the pade approximant of func(operand) with the given parameters.
# """
# from scipy.interpolate import approximate_taylor_polynomial, pade
# num_deg = degree%2+degree//2
# den_deg = degree//2
#
# self._assert_unary_compatible(operand, "operand")
# encoding = self._require_encoding(encoding)
#
# func_taylor = approximate_taylor_polynomial(func, center, degree, scale)
# func_pade_num, func_pade_den = pade([x for x in func_taylor][::-1], den_deg, n=num_deg)
# enc_func_pade_num = encoding.encode(numpy.array([x for x in func_pade_num]), self.field)
# enc_func_pade_den = encoding.encode(numpy.array([x for x in func_pade_den]), self.field)
# result_list=[]
# for op in operand.storage:
# single_op_share = ShamirArrayShare(numpy.array(op, dtype=object))
# op_pows_num_list = [self.share(src=1, secret=numpy.array(1), shape=())]
# for i in range(num_deg):
# op_pows_num_list.append(self.multiply(single_op_share, op_pows_num_list[-1]))
# if degree%2:
# op_pows_den_list=[thing for thing in op_pows_num_list[:-1]]
# else:
# op_pows_den_list=[thing for thing in op_pows_num_list]
# op_pows_num = ShamirArrayShare(numpy.array([x.storage for x in op_pows_num_list]))
# op_pows_den = ShamirArrayShare(numpy.array([x.storage for x in op_pows_den_list]))
#
# result_num_prod = self.field_multiply(op_pows_num, enc_func_pade_num)
# result_num = self.right_shift(self.sum(result_num_prod), bits=encoding.precision)
#
# result_den_prod = self.field_multiply(op_pows_den, enc_func_pade_den)
# result_den = self.right_shift(self.sum(result_den_prod), bits=encoding.precision)
# result_list.append(self.divide(result_num, result_den))
# return ShamirArrayShare(numpy.array([s.storage for s in result_list], dtype=object))
[docs]
def power(self, lhs, rhs, *, encoding=None):
"""Privacy-preserving elementwise exponentiation.
Raises secret shared array values to public integer values. Unlike
:meth:`field_power`, :meth:`power` operates on encoded values, shifting
the results right to ensure correct decoded results.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
lhs: :class:`ShamirArrayShare`, required
Secret shared values which will be raised to a power.
rhs: :class:`numpy.ndarray` containing integers, required
Public non-negative integer power to which each element in `lhs` will be raised.
Normal numpy broadcasting rules apply, so `rhs` can be any shape that
is compatible with `lhs`.
encoding: :class:`object`, optional
Determines how far to right shift the results. The protocol's
:attr:`encoding` is used by default if :any:`None`.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared result of raising `lhs` to the power(s) in `rhs`.
"""
encoding = self._require_encoding(encoding)
if isinstance(lhs, ShamirArrayShare) and isinstance(rhs, numpy.ndarray):
results=[]
with numpy.nditer([lhs.storage, rhs], order="C", flags=["refs_ok"]) as iterator:
for value, power in iterator:
value = ShamirArrayShare(value)
result = self.share(src=0, secret=numpy.array(1.0), shape=(), encoding=encoding)
# # Naive implementation performs n multiplications when raising to the n-th power.
# for i in range(power):
# result = self.field_multiply(result, value)
# result = self.right_shift(result, bits=encoding.precision)
# Fancy implementation performs exponentiation by squaring.
while True:
if power & 1:
result = self.field_multiply(result, value)
result = self.right_shift(result, bits=encoding.precision)
if not power:
break
value = self.field_multiply(value, value)
value = self.right_shift(value, bits=encoding.precision)
power = power >> 1
results.append(result)
return ShamirArrayShare(numpy.array([result.storage.item() for result in results], dtype=self.field.dtype).reshape(lhs.storage.shape, order="C"))
raise NotImplementedError(f"Privacy-preserving exponentiation not implemented for the given types: {type(lhs)} and {type(rhs)}.") # pragma: no cover
def _public_bitwise_less_than(self, *, lhspub, rhs):
"""Comparison Operator
Parameters
----------
lhs: :class:`ndarray`, required
a publically known numpy array of integers and one of the two objects to be compared
rhs: :class:`ShamirArrayShare`, required
bit decomposed shared secret(s) and the other of the two objects to be compared
the bitwidth of each value in rhs (deduced from its shape) is taken to be the
bitwidth of interest for the comparison if the values in lhspub require more bits
for their representation, the computation will be incorrect
note: this method is private as it does not consider the semantic mapping of meaning
onto the field. The practical result of this is that every negative value will register as
greater than every positive value due to the encoding.
Returns
-------
a shamir shared array containing the element wise result of the comparison: result[i] = 1 if lhspub[i] < rhs[i] and 0 otherwise
"""
if lhspub.shape != rhs.storage.shape[:-1]:
raise ValueError('rhs is not of the expected shape - it should be the same as lhs except the last dimension') # pragma: no cover
bitwidth = rhs.storage.shape[-1]
lhsbits = []
for val in lhspub:
tmplist = [int(x) for x in bin(val)[2:]]
if len(tmplist) < bitwidth:
tmplist = [0 for x in range(bitwidth-len(tmplist))] + tmplist
lhsbits.append(tmplist)
lhsbits = numpy.array(lhsbits, dtype=self.field.dtype)
assert(lhsbits.shape == rhs.storage.shape)
one = numpy.array(1, dtype=self.field.dtype)
flatlhsbits = lhsbits.reshape((-1, lhsbits.shape[-1]))
flatrhsbits = rhs.storage.reshape((-1, rhs.storage.shape[-1]))
results=[]
for j in range(len(flatlhsbits)):
xord = []
preord = []
msbdiff=[]
rhs_bit_at_msb_diff = []
for i in range(bitwidth):
rhsbit=ShamirArrayShare(storage=numpy.array(flatrhsbits[j,i], dtype=self.field.dtype))
if flatlhsbits[j][i] == 1:
xord.append(self.field_subtract(lhs=one, rhs=rhsbit))
else:
xord.append(rhsbit)
preord = [xord[0]]
for i in range(1,bitwidth):
preord.append(self.logical_or(lhs=preord[i-1], rhs=xord[i]))
msbdiff = [preord[0]]
for i in range(1,bitwidth):
msbdiff.append(self.field_subtract(lhs=preord[i], rhs=preord[i-1]))
for i in range(bitwidth):
rhsbit=ShamirArrayShare(storage=numpy.array(flatrhsbits[j,i], dtype=self.field.dtype))
rhs_bit_at_msb_diff.append(self.field_multiply(rhsbit, msbdiff[i]))
result = rhs_bit_at_msb_diff[0]
for i in range(1,bitwidth):
result = self.field_add(lhs=result, rhs=rhs_bit_at_msb_diff[i])
results.append(result)
return ShamirArrayShare(numpy.array([x.storage for x in results], dtype=self.field.dtype).reshape(rhs.storage.shape[:-1]))
[docs]
def random_bitwise_secret(self, *, bits, shape=None, src=None, generator=None):
"""Return secret values created by combining randomly generated bits.
This method returns two outputs - a secret shared array of randomly
generated bits, and a secret shared array of values created by
combining the bits in big-endian order. It is secure against
non-colluding semi-honest adversaries. A subset of players (by
default: all) generate and secret share vectors of pseudo-random bits
which are then XOR-ed together elementwise. Communication and
computation costs increase with the number of bits and the number of
players, while security increases with the number of players.
The bit array will have one more dimension than the secret array,
containing the bits in big-endian order.
.. warning::
If you supply your own generators, be careful to ensure that each
has a unique seed value to preserve privacy (for example: a
constant plus the player's rank). If players receive generators
with identical seed values, even numbers of players will produce
all zero bits.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`, even
if they aren't participating in the random bit generation.
Parameters
----------
bits: :class:`int`, required
Number of bits to generate.
shape: sequence of :class:`int`, optional
Shape of the output `secrets` array. The output `bits` array will have this
shape, plus one extra dimension for the bits.
src: sequence of :class:`int`, optional
Players that will contribute to random bit generation. By default,
all players contribute.
generator: :class:`numpy.random.Generator`, optional
A psuedorandom number generator for sampling. By default,
`numpy.random.default_rng()` will be used.
Returns
-------
bits: :class:`ShamirArrayShare`
Secret shared array of randomly-generated bits, with shape
:math:`shape \\times bits`.
secrets: :class:`ShamirArrayShare`
Secret shared array of values created by combining the generated
bits in big-endian order, with shape `shape`.
"""
bits = int(bits)
shape_was_none = False
if bits < 1:
raise ValueError(f"bits must be a positive integer, got {bits} instead.") # pragma: no cover
if src is None:
src = self.communicator.ranks
if not src:
raise ValueError(f"src must include at least one player, got {src} instead.") # pragma: no cover
if generator is None:
generator = numpy.random.default_rng()
if shape is None:
shape = ()
shape_was_none = True
bit_res = []
share_res = []
numzeros = numpy.zeros(shape)
for loopop in numzeros.flat:
# Each participating player generates a vector of random bits.
if self.communicator.rank in src:
local_bits = generator.choice(2, size=bits).astype(self.field.dtype)
else:
local_bits = None
# Each participating player secret shares their bit vectors.
player_bit_shares = []
for rank in src:
player_bit_shares.append(self.share(src=rank, secret=local_bits, shape=(bits,), encoding=Identity()))
# Generate the final bit vector by xor-ing everything together elementwise.
bit_share = player_bit_shares[0]
for player_bit_share in player_bit_shares[1:]:
bit_share = self.logical_xor(bit_share, player_bit_share)
# Shift and combine the resulting bits in big-endian order to produce a random value.
shift = numpy.power(2, numpy.arange(bits, dtype=self.field.dtype)[::-1])
shifted = self.field.multiply(shift, bit_share.storage)
secret_share = ShamirArrayShare(numpy.array(numpy.sum(shifted), dtype=self.field.dtype))
bit_res.append(bit_share)
share_res.append(secret_share)
if shape_was_none:
bit_share = ShamirArrayShare(numpy.array([x.storage for x in bit_res], dtype=self.field.dtype).reshape(bits))
secret_share = ShamirArrayShare(numpy.array([x.storage for x in share_res], dtype=self.field.dtype).reshape(shape))
else:
bit_share = ShamirArrayShare(numpy.array([x.storage for x in bit_res], dtype=self.field.dtype).reshape(shape+(bits,)))
secret_share = ShamirArrayShare(numpy.array([x.storage for x in share_res], dtype=self.field.dtype).reshape(shape))
return bit_share, secret_share
[docs]
def relu(self, operand):
"""Privacy-preserving elementwise ReLU of a secret shared array.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared operand to which the ReLU function will be applied.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise ReLU of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
ltz = self.less_zero(operand)
nltz = self.logical_not(ltz)
nltz_parts = self.field_multiply(nltz, operand)
return nltz_parts
[docs]
def right_shift(self, operand, *, bits, src=None, generator=None, trunc_mask=None, rem_mask=None):
"""Privacy-preserving elementwise right-shift of a secret shared array.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Also, this approach may probabilstically introduce a small error in the least significant bits
of the result. The is that we generate masks for the two sections of the secret shared value
of interest, one to be used in clearing out the low order bits, the other for masking the
higher order bits that will remain. There is a chance that adding the masks in will generate
a carry into the region that will remain after the shift. Therefore there is a chance that the
effects of that carry will remain in the least significant bits of the final result, which,
with the default parameters and encoding, means there could be an error in the final result on
the order of 2^-16, and with decreasing probability 2^-15, or 2^-14 depending on how far the
carry propagates.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret-shared values to be shifted right.
bits: :class:`int`, optional
Number of bits to shift.
src: sequence of :class:`int`, optional
Players who will participate in generating random bits as part of
the shift process. More players increases security but
decreases performance. Defaults to all players.
generator: :class:`numpy.random.Generator`, optional
A psuedorandom number generator for generating random bits. By
default, `numpy.random.default_rng()` will be used.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared result of shifting `operand` to the right by `bits` bits.
"""
if not isinstance(operand, ShamirArrayShare):
raise ValueError(f"Expected operand to be an instance of ShamirArrayShare, got {type(operand)} instead.") # pragma: no cover
shift_left = self.field.full_like(operand.storage, 2**bits)
# Multiplicative inverse of shift_left.
shift_right = self.field.full_like(operand.storage, pow(2**bits, self.field.order-2, self.field.order))
if trunc_mask:
truncation_mask = trunc_mask
else:
# Generate random bits that will mask the region to be truncated.
_, truncation_mask = self.random_bitwise_secret(bits=bits, src=src, generator=generator, shape=operand.storage.shape)
if rem_mask:
remaining_mask = rem_mask
else:
# Generate random bits that will mask everything outside the region to be truncated.
_, remaining_mask = self.random_bitwise_secret(bits=self.field.bits-bits, src=src, generator=generator, shape=operand.storage.shape)
remaining_mask.storage = self.field.multiply(remaining_mask.storage, shift_left)
# Combine the two masks.
mask = self.field_add(remaining_mask, truncation_mask)
# Mask the array element.
masked_element = self.field_add(mask, operand)
# Reveal the element to all players (because it's masked, no player learns the underlying secret).
masked_element = self.reveal(masked_element, encoding=Identity())
# Retain just the bits within the region to be truncated, which need to be removed.
masked_truncation_bits = numpy.array(masked_element % shift_left, dtype=self.field.dtype)
# Remove the mask, leaving just the bits to be removed from the
# truncation region. Because the result of the subtraction is
# secret shared, the secret still isn't revealed.
truncation_bits = self.field_subtract(masked_truncation_bits, truncation_mask)
# Remove the bits in the truncation region from the element. The result can be safely truncated.
result = self.field_subtract(operand, truncation_bits)
# Truncate the element by shifting right to get rid of the (now cleared) bits in the truncation region.
result = self.field.multiply(result.storage, shift_right)
return ShamirArrayShare(result)
# def taylor_approx(self, func, operand,*, encoding=None, center=0, degree=7, scale=3):
# """Return the taylor approximation of `func` sampled with `operand`.
#
# Note
# ----
# This is a collective operation that *must* be called
# by all players that are members of :attr:`communicator`.
#
# Parameters
# ----------
# func: callable object, required
# The function to be approximated via the taylor method
# operand: :class:`ShamirArrayShare`, required
# Secret-shared values where `func` should be evaluated.
# center: :class:`float`, optional
# The value at which the approximation should be centered. Sample
# errors will be larger the further they are from this point.
#
# Returns
# -------
# result: :class:`ShamirArrayShare`
# Secret shared result of evaluating the taylor approximant of func(operand) with the given parameters
# """
# from scipy.interpolate import approximate_taylor_polynomial
#
# self._assert_unary_compatible(operand, "operand")
# encoding = self._require_encoding(encoding)
#
# taylor_poly = approximate_taylor_polynomial(func, center, degree, scale)
#
# enc_taylor_coef = encoding.encode(numpy.array([x for x in taylor_poly]), self.field)
# result_list=[]
# for op in operand.storage:
# single_op_share = ShamirArrayShare(numpy.array(op, dtype=object))
# op_pow_list = [self.share(src=1, secret=numpy.array(1), shape=())]
# for i in range(degree):
# op_pow_list.append(self.multiply(single_op_share, op_pow_list[-1]))
#
# op_pow_shares = ShamirArrayShare(numpy.array([x.storage for x in op_pow_list]))
#
# result = self.field_multiply(op_pow_shares, enc_taylor_coef)
# result = self.sum(result)
# result = self.right_shift(result, bits=encoding.precision)
# result_list.append(result)
# return ShamirArrayShare(numpy.array([s.storage for s in result_list], dtype=object))
def _verify_storage(self, operand):
"""Verify the storage in a secret share.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared array to be verified.
Returns
-------
value: :class:`ShamirArrayShare`
The secret shared array.
Raises
------
:class:`ValueError`
If `operand` can't be verified.
"""
self._assert_unary_compatible(operand, "operand")
self.field._verify(operand.storage)
return operand
[docs]
def zigmoid(self, operand, *, encoding=None):
r"""Privacy-preserving elementwise zigmoid of a secret shared array.
Zigmoid is a piecewise approximation to the popular sigmoid activation
function that is more efficient to compute in an MPC context:
.. math::
zigmoid(x) = \left\{
\begin{array}\\
0 & if\ x<-0.5 \\
x+0.5 & if\ -0.5\leq x \leq 0.5 \\
1 & if x>0.5
\end{array}
\right.
Note
----
This is a collective operation that *must* be called
by all players that are members of :attr:`communicator`.
Parameters
----------
operand: :class:`ShamirArrayShare`, required
Secret shared operand to which the zigmoid function will be applied.
Returns
-------
result: :class:`ShamirArrayShare`
Secret-shared elementwise zigmoid of `operand`.
"""
self._assert_unary_compatible(operand, "operand")
encoding = self._require_encoding(encoding)
ones = encoding.encode(numpy.full_like(operand.storage, 1.0), self.field)
half = encoding.encode(numpy.full_like(operand.storage, 0.5), self.field)
secret_plushalf = self.field_add(half, operand)
secret_minushalf = self.field_subtract(operand, half)
ltzsmh = self.less_zero(secret_minushalf)
nltzsmh = self.logical_not(ltzsmh)
ltzsph = self.less_zero(secret_plushalf)
middlins = self.field_subtract(ltzsmh, ltzsph)
extracted_middlins = self.field_multiply(middlins, operand)
extracted_halfs = self.field_multiply(middlins, half)
extracted_middlins = self.field_add(extracted_middlins, extracted_halfs)
ones_part = self.field_multiply(nltzsmh, ones)
return self.field_add(ones_part, extracted_middlins)