Shamir's Secret Sharing (SSS) For Data Blobs

Untrace uses Shamir's Secret Sharing as the foundational primitive for splitting and distributing data across the decentralized node network. This document explains the algorithm, how Untrace applies it to arbitrary data blobs, and the security guarantees it provides.

What Is Shamir's Secret Sharing?

Shamir's Secret Sharing is a cryptographic algorithm invented by Adi Shamir in 1979. It splits a secret S into N shares such that:

Any K or more shares can reconstruct S (the threshold)
Any K - 1 or fewer shares reveal zero information about S

This is called a (K, N) threshold scheme. The security is information-theoretic — not computational — meaning it cannot be broken even with unlimited compute.

The Math

Given a secret S (a number in a finite field GF(p)):

Choose a random polynomial of degree K−1 with S as the constant term:

$$f(x) = S + a_1 x + a_2 x^2 + \cdots + a_{K-1} x^{K-1} \pmod{p}$$

Generate N shares by evaluating the polynomial at N distinct points:

$$\text{share}_i = (i,\ f(i)) \quad \text{for } i = 1, \ldots, N$$

Any K shares reconstruct S via Lagrange interpolation:

$$S = f(0) = \sum_{j=1}^{K} y_j \prod_{\substack{m=1 \ m \neq j}}^{K} \frac{0 - x_m}{x_j - x_m} \pmod{p}$$

Applying SSS to Arbitrary Data Blobs

Raw data (documents, files, JSON payloads) cannot be fed directly into the polynomial — it operates over finite field elements. Untrace handles this through a chunked encryption pipeline:

Pipeline

[ Raw Data Blob ]
      ↓
[ AES-256-GCM Encryption (client-side, ephemeral symmetric key) ]
      ↓
[ Encrypted Blob + Symmetric Key K ]
      ↓
[ SSS applied to Key K → N key shares ]
      ↓
[ Encrypted Blob split into N data segments ]
      ↓
[ Each node receives: one key share + one data segment ]
      ↓
[ Commitment anchored on-chain (hash of all shares + metadata) ]

Critical property: No single node ever holds enough information to decrypt the data. Reconstructing the original blob requires:

K of N valid key shares (to reconstruct K)
Reassembling the data segments
Decrypting with the reconstructed K

Threshold Parameters

Untrace uses configurable (K, N) parameters depending on the sensitivity level:

| Sensitivity | Threshold K | Total Shards N | Notes | | ------------ | ----------- | -------------- | ----------------------------------- | | Standard | 3 | 5 | Default for most vault data | | High | 5 | 9 | Regulated data (HIPAA, GDPR, PCI) | | Maximum | 7 | 13 | Financial instruments, key material |

Higher thresholds increase redundancy and fault tolerance at the cost of slightly higher reconstruction latency.

Node Selection

When distributing shards, Untrace's protocol selects nodes to maximize geographic and jurisdictional diversity:

Nodes in different autonomous systems (AS numbers)
Nodes across different legal jurisdictions
No two shards on nodes operated by the same entity

This ensures that even a coordinated legal attack across multiple jurisdictions cannot retrieve enough shards to reconstruct data.

Security Guarantees

| Property | Guarantee | | ------------------------ | -------------------------------------------------------------- | | Data confidentiality | K−1 compromised nodes reveal zero bits about the original data | | Integrity | Each shard is MAC'd; tampering is detected on reconstruction | | Availability | Data survives up to N−K simultaneous node failures | | Forward secrecy | Ephemeral symmetric keys are rotated per vault write | | Quantum resistance | SSS is information-theoretic; immune to quantum attacks |

Reconstruction Flow

Reconstruction is gated by the ZK identity layer. A client cannot even request shard delivery without first proving identity.

[ Client requests vault reconstruction ]
      ↓
[ ZK Proof of ownership generated locally ]
      ↓
[ Proof submitted to on-chain verifier contract ]
      ↓
[ Verifier emits approval event ]
      ↓
[ K nodes release their encrypted shards ]
      ↓
[ Client reassembles segments + reconstructs K via SSS ]
      ↓
[ Decrypt blob with K → original data ]

Nodes release shards only after the on-chain verifier confirms a valid proof — they never communicate directly with clients about the proof validity.