Active Adversaries
Additive secret sharing
and Shamir secret sharing are popular sharing schemes provided by Cicada, but are secure only against semi-honest (also known as “honest but curious”) adversaries. With this security model, private information is secure against disclosure, but a malicious player (an “active adversary”) could deliberately alter a calculation to produce an invalid result, and none of the other players would know.
As a more robust (but slower) alternative, Cicada provides ActiveProtocolSuite
, which provides honest majority security with abort. In this case, private information is still secure against disclosure, and tampering with a calculation can be detected by an honest player, so long as there are less than \(\frac{n}{2}\) dishonest players.
ActiveProtocolSuite
supports the same mathematical and logical operations as AdditiveProtocolSuite
and ShamirProtocolSuite
, and its secret shares are implemented using a combination of additive and Shamir secret sharing. The security against malicious alteration in this case is derived from the fact that attempts to alter both types of share in parallel give rise to inconsistencies that can be detected.
Note that the identity of dishonest players may not be detectable by this scheme, nor is there any way to recover a correct value from the computation - the only resort for honest players is to discontinue the computation (abort) and restart it with a different (hopefully honest) group of players.
Let’s begin with an example of sharing and revealing a value, without any tampering, using additive secret sharing:
[1]:
import logging
logging.basicConfig(level=logging.INFO)
import numpy
from cicada.additive import AdditiveProtocolSuite
from cicada.communicator import SocketCommunicator
from cicada.logging import Logger
def main(communicator):
log = Logger(logging.getLogger(), communicator)
protocol = AdditiveProtocolSuite(communicator)
secret = numpy.array(42) if communicator.rank == 0 else None
secret_share = protocol.share(src=0, secret=secret, shape=())
result = protocol.reveal(secret_share)
log.info(f"Player {communicator.rank} revealed: {result}")
SocketCommunicator.run(world_size=3, fn=main);
INFO:root:Player 0 revealed: 42.0
INFO:root:Player 1 revealed: 42.0
INFO:root:Player 2 revealed: 42.0
This is all very straightforward, but let’s see what happens when player 1 tampers with its share of the secret so that the revealed value increases by one:
Note
Keep in mind that, no matter what player 1 does, the secret itself is still secure - although the tampering will cause the revealed value to increase by 1, the value itself isn’t known, until it’s explicitly revealed.
Warning
The following code uses the storage attribute to directly modify secret shares; under normal circumstances, you should never modify secret shares in this way, regardless of protocol suite. We do it here to model adversarial behavior only.
[2]:
def main(communicator):
log = Logger(logging.getLogger(), communicator)
protocol = AdditiveProtocolSuite(communicator)
secret = numpy.array(42) if communicator.rank == 0 else None
secret_share = protocol.share(src=0, secret=secret, shape=())
# Evil player behavior here!
if communicator.rank == 1:
secret_share.storage += 65536
result = protocol.reveal(secret_share)
log.info(f"Player {communicator.rank} revealed: {result}")
SocketCommunicator.run(world_size=3, fn=main);
INFO:root:Player 0 revealed: 43.0
INFO:root:Player 1 revealed: 43.0
INFO:root:Player 2 revealed: 43.0
Note that player 1 has successfully altered its share so that the revealed value is 43 instead of 42, and that - in the general case - the other players would have no way of knowing that the tampering occurred.
Note
For this trivial example, player 0 might notice that the revealed value doesn’t match the value that they originally provided, but for the vast majority of use-cases involving actual computation, this won’t be possible.
Now, let’s try the same experiment, but using ActiveProtocolSuite
instead:
[3]:
from cicada.active import ActiveProtocolSuite
def main(communicator):
log = Logger(logging.getLogger(), communicator)
protocol = ActiveProtocolSuite(communicator, threshold=2)
secret = numpy.array(42) if communicator.rank == 0 else None
active_share = protocol.share(src=0, secret=secret, shape=())
# Evil player behavior here!
if communicator.rank == 1:
additive_share, shamir_share = active_share.storage
additive_share.storage += 65536
result = protocol.reveal(active_share)
log.info(f"Player {communicator.rank} revealed: {result}")
SocketCommunicator.run(world_size=3, fn=main);
ERROR:cicada.communicator.socket:Comm world player 0 failed: ConsistencyError('Secret Shares are inconsistent in the first stage')
ERROR:cicada.communicator.socket:Comm world player 1 failed: ConsistencyError('Secret Shares are inconsistent in the first stage')
ERROR:cicada.communicator.socket:Comm world player 2 failed: ConsistencyError('Secret Shares are inconsistent in the first stage')
In this case, ActiveProtocolSuite
detects the tampering as soon as the players attempt to reveal the secret, and raises a cicada.active.ConsistencyError
exception. Checking for tampering when secrets are revealed keeps the cost of tamper detection low by amortizing it across the entire computation, while ensuring that invalid results cannot go undetected or ignored.
Players can also perform explicit checks for tampering instead of waiting for reveal: this can be useful to checkpoint correct results and/or avoid wasted effort by aborting a long-running computation if tampering is detected:
[4]:
def main(communicator):
log = Logger(logging.getLogger(), communicator)
protocol = ActiveProtocolSuite(communicator, threshold=2)
secret = numpy.array(42) if communicator.rank == 0 else None
active_share = protocol.share(src=0, secret=secret, shape=())
# Evil player behavior here!
if communicator.rank == 1:
additive_share, shamir_share = active_share.storage
additive_share.storage += 65536
# Explicitly test for tampering here.
if not protocol.verify(active_share):
log.error(f"Player {communicator.rank} detected tampering!")
return
result = protocol.reveal(actove_share)
log.info(f"Player {communicator.rank} revealed: {result}")
SocketCommunicator.run(world_size=3, fn=main);
ERROR:root:Player 0 detected tampering!
ERROR:root:Player 1 detected tampering!
ERROR:root:Player 2 detected tampering!
Let’s attempt a more subtle tamper:
[5]:
def main(communicator):
log = Logger(logging.getLogger(), communicator)
protocol = ActiveProtocolSuite(communicator, threshold=2)
secret = numpy.array(42) if communicator.rank == 0 else None
active_share = protocol.share(src=0, secret=secret, shape=())
# Evil player behavior here!
if communicator.rank == 0:
additive_share, shamir_share = active_share.storage
modulus = 2**64-59
additive_share.storage += 1
#shamir_share.storage = (shamir_share.storage + pow(5, modulus-2, modulus)) % modulus
shamir_share.storage = (shamir_share.storage + pow(3, modulus-2, modulus)) % modulus
# # Explicitly test for tampering here.
# if not protocol.verify(active_share):
# log.error(f"Player {communicator.rank} detected tampering!")
# return
result = protocol.reveal(active_share)
log.info(f"Player {communicator.rank} revealed: {result}")
SocketCommunicator.run(world_size=3, fn=main);
ERROR:cicada.communicator.socket:Comm world player 0 failed: ValueError("Expected numpy.ndarray, got <class 'int'>.")
ERROR:cicada.communicator.socket:Comm world player 1 failed: Timeout('Tag ALLGATHER from player 0 timed-out after 5s')
ERROR:cicada.communicator.socket:Comm world player 2 failed: Timeout('Tag ALLGATHER from player 0 timed-out after 5s')
Since ActiveProtocolSuite
provides the same operations as the additive and Shamir suites, you can use it to perform any computation that you would have performed with the latter, but with detection for the influences of active malicious adversaries. The cost of this security is roughly equal to the sum of the computational and communication cost of the additive and Shamir protocol suites individually.