Inspiration

Splitting a secret with Shamir's scheme is elegant, but applied to a whole file it makes every share as large as the file itself: \( n \) holders means \( n\times \) the storage. Krawczyk's 1993 "Secret Sharing Made Short" fixes that by encrypting the file once and sharing only the key. When we looked at how that idea is used in practice, three gaps kept appearing: nothing stops someone from silently editing the threshold, shares from different files can be mixed, and a single corrupted share produces a garbage key that is only discovered after a wasted decryption. ShardVault closes all three without inventing a new cipher.

What it does

ShardVault protects a file so that any \( t \) of \( n \) holders can open it, while any group of \( t-1 \) learns nothing except the file's length.

  1. Draw a fresh 256-bit key \( K \) and encrypt the file with AES-256-GCM.
  2. Split \( K \) with Shamir's scheme over the Mersenne field \( \mathbb{F}_p,\ p = 2^{521}-1 \).
  3. Hand each holder one 244-byte share, the same size whether the file is 1 KB or 1 GB.

Three hardening measures on top of the classical construction:

  • Header binding. The threshold, file ID and parameters are authenticated as GCM associated data, so any edit breaks decryption.
  • Pre-decryption cheater detection. A domain-separated key-check value \( H(\texttt{"sv-key-check"} | K) \) rejects inconsistent or tampered shares before the cipher runs.
  • Share namespacing. Every share carries a per-file ID, so shares from another vault are filtered out.

The math

Shares are points on a random polynomial \( f(X) = K + a_1X + \dots + a_{t-1}X^{t-1} \). Any \( t \) of them recover \( K \) by Lagrange interpolation:

$$ K = \sum_{i \in S} y_i \prod_{j \in S \setminus {i}} \frac{-x_j}{x_i - x_j} \pmod p $$

Any \( t-1 \) shares are uniformly distributed and independent of \( K \), because the map from coefficients to shares is a bijection (a Vandermonde argument). We prove three things:

  • Correctness: \( t \) honest shares always recover the file.
  • Privacy: \( \mathrm{Adv}^{\text{priv}} \le \mathrm{Adv}^{\text{ind-cpa}}_{\text{GCM}} + q/2^{256} \), so breaking ShardVault means breaking AES-GCM.
  • Integrity: an accepted plaintext is the original, by GCM's ciphertext integrity and the key-check.

How we built it

  • A reference implementation in Python (shardvault.py, about 130 lines) using the cryptography library for AES-GCM and native big integers for field arithmetic, with a command-line tool: seal file -t 3 -n 5 and open vault share1 share3 share5.
  • A test suite that checks every 3-of-5 subset recovers the key, that 2 shares do not, and that tampered shares, tampered ciphertext and foreign shares are all rejected. All tests pass.
  • Measured performance: a 16 MiB file seals in 5.9 ms and opens in 8.4 ms; the vault adds a constant 143 bytes.
  • A 5-page LaTeX paper with full proofs and an attack-surface analysis of 9 attack classes.

Challenges

  • Resisting a "new" cipher. A brand-new primitive designed in days will not survive real cryptanalysis. We put the novelty in how proven primitives are composed, so every security claim reduces to AES-GCM or Shamir sharing.
  • Detecting a cheater without verifiable secret sharing. Full Feldman or Pedersen VSS needs public commitments in a discrete-log group. A domain-separated hash of the key detects bad shares at a fraction of the cost. It doesn't identify which holder cheated, which we list as a limitation.
  • Edge cases in interpolation: duplicate indices, reconstructed values at or above \( 2^{256} \), and shares from the wrong file all have to be rejected explicitly.

What we learned

Most real-world failures of secret sharing aren't about the math of the polynomial. They come from unauthenticated metadata and silent share corruption. Binding everything public into the AEAD's associated data turned out to be the cheapest, strongest fix.

What's next

  • Verifiable shares (Pedersen VSS) to protect against a malicious dealer
  • Cheater identification with Berlekamp–Welch decoding
  • Constant-time field arithmetic
  • Proactive share refresh for long-lived vaults

Built With

  • aes-gcm
  • cryptography
  • latex
  • pytest
  • python
  • sha-256
  • shamir-secret-sharing
Share this project:

Updates

Submission history