Solving the First Learner Problem

• In any MPC protocol, outputs are always first learned upon receipt of some message
• Whoever receives that message will have the option to abandon the protocol without sharing the output

This is described in Pragmatic MPC p25:

In any message-based two-party protocol, one party will learn the final output before the other. If that party is corrupt and malicious, they may simply refuse to send the last message to the honest party and thereby prevent the honest party from learning the output.

Pragmatic MPC p25 also seems to suggest this is an unavoidable problem:

Usually the possibility of blocking outputs to honest parties is not written explicitly in the description of the functionality. Instead, it is generally understood that when discussing security against malicious adversaries, the adversary has control over output delivery to honest parties and output fairness is not expected.

Upon first inspection, this appears to be reasonable, but here I present 3 increasingly effective strategies for reducing it, with the third being close to a full solution.

Strategy 1: Randomize the Learner

• Add a private mask input for all parties
• Extend the MPC to choose one of the masks at random (eg masks[sum(masks) % |P|]) and compute output + random_mask
• Whoever would have been the learner before now only learns the masked output, and only the masker can uncover the output
  • Also requires some way to verify the unmasked output (eg commit to masks beforehand and assert the commits are correct inside the MPC)

Strategy 2: Progressive Reveal

• Instead of calculating output, calculate an alt_output for each participant such that the XOR of these alternate outputs is equal to output
• Use another MPC to calculate the bits of the output one at a time, this way each first learner (fair sharing sequence?) can abandon the protocol with at most one bit of extra information
• Each bit can also be made progressive by instead calculating the correct bit or its negation with some probability
  • This is repeated until both parties are statistically confident about the value, followed by an ordinary non-random calculation of that bit to confirm

Strategy 3: Progressive Key Reveal

• Add input k_i for each participant, each chooses their k_i randomly
• In the MPC, instead of calculating output, calculate hash(K), enc_K(output), where K is the bitwise XOR of all k_i values
• Use the progressive reveal technique on K (see strategy 2)
• If a participant learns the output and abandons the progressive reveal, then the pre-image of hash(K) must have become feasible to compute with their partial knowledge of K
• Other participants have at least this same knowledge of K less one bit, so computing the output is feasible in just double the time spent by the malicious participant
  • Need to also adjust for differences in computing power

Bonus Strategy 1: Trusted Hash Revealer

A trusted hash revealer (THR) is a trusted third party (TTP) who behaves as follows:

• Establish a set of hashes that all parties wish to be jointly revealed
  • (All parties redundantly send everyone's hashes, THR confirms they match)
• Receive pre-images of all hashes
• Verify all
• Distribute pre-images

By using only masking parameters as the pre-images, the THR learns no meaningful information.

Although a TTP is an unusual addition to an MPC protocol, this TTP only learns forbidden information in the presence of a malicious participant, which a malicious participant could have shared with them anyway. Therefore the addition of this TTP makes the MPC no less secure.

Bonus Strategy 2: Hash Reveal Staking

Instead of using a third party to manage hash reveals (see above), use a smart contract which allows users to commit to revealing a pre-image if the other required pre-images are revealed.

Users are required to deposit a stake. If one of the parties does not reveal their pre-image, the other parties reveal theirs on-chain. The non-compliant user must then reveal their pre-image on-chain within a certain deadline, otherwise their stake is slashed.

With a significant stake, and in combination with Progressive Reveal, this would require a user to pay a lot of money to conceal a single bit (or less!) of information.