Adventures in Boundary Conditions

Permeating the World in a Particularly Unsubtle Way

Secure Multi-party Communication

This is the first of two blog posts about secure multiparty communcation.

Secure multi-party communication (I'll refer to it as SPMC since it's a mouthful) is a topic that's pretty near and dear to my heart.

Well, maybe not that near and dear, but certainly a topic that I wrestled with over the course of a week trying to properly implement it. The issue I found is that there's a thousand different papers and mathematically leaning tutorials, but nothing that's easily approachable for a cryptography student without constant head-bashing.

So this is the post that I wish I could've read to get started on SMPC.

1 What Secure Multi-party Communication is

With the rise of Bitcoin and blockchain based cryptocurrencies (Ethereum and friends), it's become increasing necessary to have group communication that fufills two main goals: security and accuracy. Security refers to both the anonmitiy of this calcuation, each party partipating in the group should be secure in that their information won't be shared with everyone else in the clear. Accuracy refers to that the results of the group communication is correct and trustworthy. I'll illustrate these two points with a classic example: eBay.

1.1 Is eBay Trustworthy?

No, not the sellers on eBay, eBay itself. How do we know eBay honors the highest bid? We don't, but since eBay's profits are based on the bid amount, the consumer's and eBay's interests are aligned, and we can be resonable assured that eBay will honor the highest bids.

But this brings up a good question, would it be possible to have eBay without…eBay? That is, an aunction without an auctioneer? Well, it'd require two main features:

  1. Only the winner and the winning bid should be revealed, we shouldn't be sending bidding information in the clear.
  2. The declared winning bid should be the accurate winning bid.

In other words, we're computing a function of private inputs without revealing information about the inputs (beyond what's revealed by the function).

Overall, the goal of SMPC is to securely accomplish a great deal of things: such as distributed data mining, e-commerce, gaming, voting, secure function evaluation, etc.

With that in mind, we can discuss issues that we need to consider for our SMPC protocol.

2 Adversary

The term adversary is heavily used in cryptography and is generally an outside attacker. However, the term adversary usually has some strict boundaries on it, and I'll define the ones I'm using here:

  1. Adversary is computationally bound - the adversary can't just break through encryption at will, assuming we've set up encryption correctly.
  2. Adversary can corrupt any set of players - if the adversary finds holes in our protocol, they can use that information to influence the participants in said protocol.
  3. Adversary is static - The adversary will not corrupt partipants dynamically during/after the execution, which means that the adversary can only influence players before each round of the protocol. (Active adversaries is a post for another time).
  4. Adversary is passive - only read access to the internal state of the partipants, and can use that information in talking to the environment (also called honest-but-curious).

3 Trust Issues

Now we can get to the specific trust issues with our protocol:

  1. The protocol may leak a party's secrets
    • This is an issue even if we assume everyone is honest-but-curious.
    • A particular party may not be privvy to some data, and recieving that data is a liability
      • Medical data companies don't want the specifics of a patient's condition, for example
  2. The Protocol may the the adversary illegitimate influence on the outcome
    • In a poker game, we can't let the adversary influence the hands dealt.

Now that there's a basic understanding of what the issues are, let's take a look at simple applications of SMPC.

4 Applications: Confirmation and Oblivious Transfer

There's two extremely simple applications of SMPC: confirmation and oblivious transfer.

4.1 Commitment

Commitment is a simple "reactive" example of SMPC, which is that it maintains a state over multiple rounds. Imagine this:

Company X has information it wants to dissmenate a later time, such as the price of a corn future. Using SMPC it can commit this data into a third party, and then later send a message to the third party telling the third party to reveal the information. This is extremely similar to holding money in an escrow, except SMPC does this with arbitrary data.

4.2 Oblivious Transfer

Oblivious Transfer is similar to commitment, except that it involves choices. We'll take the same company X, who now has prices for two futures: corn and soybeans. A consumer would like to know the price of the corn future, but requires that company X doesn't know he wants the price of a corn future. To facilitate this, company X hands off both prices to a trusted third party, who then queries the consumer for which future he would like, and responds accordingly.

Sound familiar? Yep, it's like Smart Contracts for Ethereum, or effectively a third party who's both trustworthy and reliable. This third party needs to respond to both sides accurately, and can't be influenced by outside sources.

In the next post, I'll talk about real world implementations of SMPC, such as Yao's Garbled Circuit and the GMW/BGW Protocols.