Secret sharing

Overview

In secret sharing, a value is split into parts, and each party holds one or more parts. Any party alone learns nothing about the value, while the parties together can reconstruct it or compute on it 1912.02631 §3.1. The only card so far uses several sharing types over one ring, Z_(2^64) in its implementation 1912.02631 §6. The types differ in how they support addition and multiplication. Conversions move a value from one type to another 1912.02631 §4.3.

Variants

Every variant below comes from one paper. Sharing types from other papers are left out until their cards exist.

Additive sharing

A value x is held as three parts that sum to x, one per party P1, P2 and P3 1912.02631 §3.1. Addition and multiplication by a public constant are local 1912.02631 §3.1. Card: Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning.

Replicated sharing

The same three values are held in a cycle. Each of P1, P2 and P3 holds two of the three parts, so no party holds the whole value 1912.02631 §3.1. Addition and multiplication by a public constant are local here too 1912.02631 §3.1.

Masked sharing

A masked value is a public mask m = x + pad, where the pad is a random value shared in replicated form. P1, P2 and P3 know the mask, and the pad parts are known to P0 in clear 1912.02631 §3.1. Addition of masked values uses the same linearity 1912.02631 §3.1. Masked sharing is the basis of the paper's multiplication gate, which costs 3 ring elements online per verified gate 1912.02631 §3.2, §1.

Verifiable sharing and dot product

A value shared in a verifiable way comes with a hash of its mask, which the other party checks 1912.02631 §4.2. The paper's dot product adds the multiplication terms locally and exchanges one message, so its communication does not grow with the vector length d: 3 ring elements offline and 3 online 1912.02631 §4.2, app. B.

Truncation with multiplication

After a fixed-point multiplication, the result is shifted right by d bits. The paper's combined step, multiplication with truncation, uses random masks that are shared in advance and checked with one message and one hash 1912.02631 §5.1. The value of d is not stated in the card 1912.02631 §5.

When to use which

The table reflects one paper. It names the setting the paper uses and the conditions under which each step is cheap there.

Trade-off: the paper's checks are postponed to output reconstruction, so a cheating party is detected late 1912.02631 §3.2. Fair reconstruction adds 4 rounds 1912.02631 app. B.

Implementation sketch

Language-agnostic outline of the common core. Only the additive and masked forms are shown. The sign convention in the first step is open; see Contradictions.

# Additive sharing of x into three parts that sum to x  [§3.1]
def share_additive(x, random_ring_element):
    # Two parts are random ring elements  [§3.1, πaSh]
    s1 = random_ring_element()
    s2 = random_ring_element()
    # Third part makes the three parts sum to x (sign: see Contradictions)  [§3.1]
    s3 = x - s1 - s2
    return s1, s2, s3

# Addition of masked values is local  [§3.1]
def add_masked(mask_x, mask_y):
    # Masks add; pad parts add in the same way, held by the same parties
    return mask_x + mask_y

# Reconstruction of a masked value  [§3.2, πRec]
def open_masked(mask, pad_1, pad_2, pad_3):
    # The value is the mask minus the three pad parts
    return mask - (pad_1 + pad_2 + pad_3)

Contradictions

Within the one paper that covers this concept, these points disagree or cannot be reconciled from the text. Each side is cited.

• Sign convention. The definition gives three additive parts that sum to x 1912.02631 §3.1. The share step for P0 sets the third part to minus the sum of the value and the other two parts, which makes the parts sum to minus x 1912.02631 §3.2, πaSh. The truncation step is consistent with that reading 1912.02631 §5.1, while the bit-to-arithmetic step negates the parts, which is not 1912.02631 §4.3, πBitA. Read literally, one of these steps is wrong. Pick one convention and test it.
• Headline speed-up. The abstract gives up to 187x for training and up to 158x for prediction. The text gives up to 251.84x for LAN linear-regression training 1912.02631 §1, §6.1. The table values give 251.1x for the same comparison 1912.02631 tab. 4. No table entry gives 187x.
• Communication gain for conversions. The abstract claims 18x less communication for bit-to-arithmetic. The conversion table, at ℓ = 64, gives about 21x 1912.02631 §1, app. C, tab. 9. The source of 18x is not stated.
• Baseline for semi-honest ABY3. The text quotes 2.5 iterations per second for neural-network training at batch 128. The authors' own measurement gives 1.01 1912.02631 §1, app. E, tab. 13. The two are not reconciled.

Papers

• Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning: a four-party framework that uses additive, replicated and masked sharings, with truncation and dot-product protocols.