Shamir's Secret Sharing (SSS) For Data Blobs

Untrace uses Shamir's Secret Sharing as the foundational primitive for splitting encryption keys across the decentralized node network. This document explains the algorithm, how Untrace applies it to encrypted 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, meaning the missing secret cannot be recovered from fewer than K shares even with unlimited compute.

The Math

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

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

f(x) = S + a1x + a2x^2 + ... + a(K-1)x^(K-1) (mod p)

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

share_i = (i, f(i)) for i = 1, ..., N

3. Any K shares reconstruct S via Lagrange interpolation.

Applying SSS to Arbitrary Data Blobs

Raw data such as documents, files, and JSON payloads should not be placed directly into an SSS polynomial. Untrace handles arbitrary data through a client-side encryption pipeline:

[ Raw Data Blob ]
      ↓
[ Symmetric encryption with an ephemeral key K ]
      ↓
[ Encrypted Blob + Symmetric Key K ]
      ↓
[ SSS applied to Key K -> N key shares ]
      ↓
[ Encrypted Blob erasure-coded into N recoverable payload shards ]
      ↓
[ Each node receives one encrypted shard bundle ]
      ↓
[ Manifest commitment anchored on-chain ]

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

1. K of N valid key shares to reconstruct K
2. Enough payload shards to recover the encrypted blob
3. Successful integrity checks against shard commitments
4. Local decryption with the reconstructed key

SSS protects the key. Erasure coding protects payload availability. Both are needed for a reliable K-of-N data vault.

Threshold Parameters

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

Higher thresholds increase resilience and privacy at the cost of retrieval latency and operational complexity.

Node Selection

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

• Nodes in different autonomous systems
• Nodes across different legal jurisdictions
• No two shards on nodes operated by the same entity

This reduces the chance that one operator, cloud provider, or jurisdiction can obtain enough shards to reconstruct a vault.

Security Guarantees

Reconstruction Flow

Reconstruction is gated by wallet-signed retrieval requests. A client cannot request shard delivery without signing a fresh request that nodes can verify.

[ Client requests vault reconstruction ]
      ↓
[ Client signs vault ID, shard generation, nonce, expiry, and action ]
      ↓
[ Storage nodes verify signature, freshness, assignment, and policy ]
      ↓
[ K authorized nodes return encrypted shard bundles ]
      ↓
[ Client reconstructs K via SSS and recovers payload via erasure decoding ]
      ↓
[ Decrypt blob with K -> original data ]

Nodes release shards only after independently verifying the wallet signature, request freshness, and authorization for the requested vault and shard generation.

Relationship to ZK Proofs

ZK proofs are separate from SSS reconstruction. In Untrace, ZK is used for dashboard proof workflows after a user already has access to their files. For example, a user can prove a fact from a bank statement PDF without revealing the PDF itself, then optionally sign an attestation or mint a soulbound token representing that claim.