Visual Secret Sharing & Additive Schemes

Visual secret sharing (Naor & Shamir, 1994) splits an image into n transparencies such that overlaying k transparencies reveals the secret image, while any fewer reveal nothing — even to a computationally unbounded adversary.

Each pixel of the secret is expanded into a 2x2 block. For a black pixel: both shares get complementary patterns (when stacked, all black). For a white pixel: both shares get the same pattern (when stacked, 50% black = grey). The eye perceives the difference.

For bit strings: share secret S by generating random R_1, R_2, ..., R_{n-1}. Set R_n = S XOR R_1 XOR ... XOR R_{n-1}. All n shares XORed together = S. Any subset of n-1 shares is uniformly random — reveals nothing about S.

XOR/additive sharing is n-of-n (all shares required). Shamir SSS is k-of-n (any k shares). Additive sharing is simpler and faster; Shamir handles arbitrary thresholds. MPC protocols often use additive sharing for arithmetic operations.

For integer secrets: share S as S = s_1 + s_2 + ... + s_n (mod p). Each s_i is a random element of Z_p. To add two shared values A+B: each party locally adds their shares: (a_i + b_i) mod p. No communication needed for addition.

Multiplying secret-shared values requires interaction. The classic Beaver triple method: pre-compute shared random (a, b, c=ab). To multiply x*y: reveal (x-a) and (y-b) to all parties (these reveal nothing about x,y), then compute x*y using the triple.

A Linear Secret Sharing Scheme (LSSS) realizes any monotone access structure. Shamir is an LSSS. LSSS are the building block for attribute-based encryption (ABE) and multi-authority access control systems.

Packed Shamir shares multiple secrets in one polynomial: encode k secrets as coefficients of a degree-(n-k) polynomial. Allows amortized communication cost in MPC protocols when many values need to be shared simultaneously.

Basic sharing schemes offer no protection against malicious shareholders submitting invalid shares. Verifiable Secret Sharing (VSS) adds commitments; Robust Secret Sharing adds error correction so even with t bad shares, reconstruction succeeds.

Visual cryptography: printed document authentication, secure voting ballots. Additive sharing: SPDZ MPC, Secure aggregation in federated learning (Google). Threshold schemes: hardware wallet seed backup, enterprise key management.

A (k,n) ramp scheme is weaker: fewer than k-d shares reveal partial information (d levels of secrecy). Used when perfect secrecy of partial shares is not required but storage efficiency is critical. Allows shorter shares than Shamir.

In XOR-based additive n-of-n sharing, how many shares are needed to reconstruct the secret?

Visual cryptography splits images into transparencies; additive sharing uses XOR for n-of-n schemes; Shamir handles k-of-n. MPC uses additive sharing with Beaver triples for multiplication. Next: threshold signatures and real-world use.