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:

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.

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:

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:

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:

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.