Kavach-SS: Validated Threshold Sharing for Master Keys

Split a master key so t-1 shares reveal nothing and tampering is caught w.p. 1-2^-60, using only Cauchy matrices + GF(2^61-1). Branch-free, zero-dependency Rust.

Comment

Code: https://github.com/sarveshkh786/kavach-ss · Full paper with proofs (PDF): https://github.com/sarveshkh786/kavach-ss/blob/main/paper/kavach.pdf

Inspiration

A master key stored in one place is a single point of failure. Splitting it with Shamir's scheme removes that point of failure, but adds a new problem: one lying shareholder can silently change the key you reconstruct. The fixes people usually reach for (Feldman/Pedersen commitments) rely on discrete-log hardness, need large-group exponentiation, and fall to quantum computers. We wanted a scheme that protects the key, validates reconstruction, and resists side channels using nothing but number theory and linear algebra, with security that holds against an unbounded adversary.

What it does

Kavach-SS (kavach is Hindi for "armour") splits a master key \(K\) into \(n\) shares so that:

  • any \(t\) shares reconstruct \(K\);
  • any \(t-1\) shares reveal zero information about \(K\) (perfect secrecy);
  • the combiner validates the result. Any tampering by up to \(t-1\) liars is caught with probability \(\ge 1-2^{-60}\). When redundant shares are supplied, detection is certain;
  • shares can be proactively refreshed, so shares stolen in an earlier epoch become worthless.

No pre-existing cipher (AES, ChaCha, RSA, …) touches the plaintext.

How we built it: the algorithm

1. The field

We work in the Mersenne prime field \(\mathbb{F}_p\) with \(p = 2^{61}-1\). Because \(2^{61}\equiv 1 \pmod p\), every product \(x\lt 2^{122}\) reduces as

$$ x = x_{\text{hi}} 2^{61} + x_{\text{lo}} ~\equiv~ x_{\text{hi}} + x_{\text{lo}} \pmod p, $$

which takes one mask, one shift, one add, and a branch-free conditional subtraction. Inverses use Fermat: \(a^{-1} = a^{p-2}\).

2. The extended Cauchy generator

Fix nodes \(x_i = i\) for \(i=0,\dots,n\) and \(y_j = p-1-j\) for \(j=0,\dots,t-1\). The two sets are disjoint. Define the \((n+1)\times t\) matrix

$$ C_{ij} = \frac{1}{x_i - y_j}. $$

Row \(\mathbf c_0\) is the secret row; rows \(\mathbf c_1,\dots,\mathbf c_n\) are the share rows. By the Cauchy determinant formula

$$ \det C = \frac{\prod_{i\lt j}(x_j-x_i)(y_i-y_j)}{\prod_{i,j}(x_i-y_j)} \neq 0, $$

every square submatrix is non-singular. Both reconstruction and privacy follow from this one fact.

3. Dealing

Cut \(K\) into 56-bit limbs \(s_1,\dots,s_L\). Sample a MAC key \(\alpha \xleftarrow{R} \mathbb{F}_p^{\times}\) and form

$$ \mathbf w = (\alpha,~ s_1,~ \alpha s_1,~ \dots,~ s_L,~ \alpha s_L) \in \mathbb{F}_p^{2L+1}. $$

For each component \(w\), pick \(v_1,\dots,v_{t-1}\) uniformly and set \(v_0 = \big(w - \sum_{j\ge1} C_{0j}v_j\big)C_{00}^{-1}\), so that \(\mathbf c_0\cdot\mathbf v = w\). Holder \(i\) receives \(\sigma_i(w) = \mathbf c_i\cdot\mathbf v\).

4. Combining and validating

With indices \(I\) (\(|I|=t\)), compute the public vector \(\boldsymbol\lambda = \mathbf c_0 C_I^{-1}\) and set \(\hat w = \boldsymbol\lambda\cdot\boldsymbol\sigma_I(w)\). Each extra share \(e\) must satisfy \(\sigma_e = (\mathbf c_e C_I^{-1})\cdot\boldsymbol\sigma_I\). Finally, check in constant time:

$$ \hat\alpha \neq 0 ~\wedge~ \bigwedge_{l=1}^{L}\big(\hat\alpha \hat s_l = \hat\tau_l\big). $$

5. Proactive refresh

Add a fresh sharing of \(0\) to every component. The secret and the MAC relation are unchanged, the shares are fully re-randomised, and a new 128-bit epoch ID stops old and new shares from being mixed.

Security proofs (sketch; full proofs are in the PDF)

Theorem 1 (Correctness). \(C_I\) is an invertible Cauchy matrix, so \(\mathbf v = C_I^{-1}\boldsymbol\sigma_I\) and \(w=\mathbf c_0\mathbf v\). \(\blacksquare\)

Theorem 2 (Perfect secrecy). For \(|J| = t-1\), the matrix \(M=\begin{pmatrix}\mathbf c_0\\ C_J\end{pmatrix}\) is a \(t\times t\) Cauchy minor and therefore invertible. Here \(\mathbf v\) is uniform on the hyperplane \(H_w=\lbrace \mathbf c_0\cdot\mathbf v=w\rbrace \), and \(\mathbf v\mapsto M\mathbf v=(w,\boldsymbol\sigma_J)\) is a bijection \(H_w\to\lbrace w\rbrace \times\mathbb F_p^{t-1}\). So \(\boldsymbol\sigma_J\) is uniform for every \(w\): the coalition learns nothing about \(K\) or \(\alpha\). \(\blacksquare\)

Theorem 3 (Validation soundness). Reconstruction is linear, so a cheater can only add offsets: \(\hat\alpha=\alpha+\delta_\alpha\), \(\hat s_l=s_l+\delta_l\), \(\hat\tau_l=\alpha s_l+\varepsilon_l\). By Theorem 2, \(\alpha\) is uniform given the cheater's view, even if the cheater knows \(K\). Passing the check with \(\delta_l\neq0\) requires

$$ \alpha \delta_l = \varepsilon_l - \delta_\alpha s_l - \delta_\alpha\delta_l, $$

which pins \(\alpha\) to a single value. So \(\Pr[\text{forge}] \le \frac{1}{p-1} \lt 2^{-60}\). \(\blacksquare\)

Theorem 4 (Certain detection with redundancy). The share rows generate an MDS code with distance \(n-t+1\), so any error of weight \(\le n-t\) is detected with probability 1. \(\blacksquare\)

Vulnerability windows mitigated

Window Mitigation
Key at rest on one machine \(t-1\) shares are information-theoretically useless
Malicious or corrupted holder IT-MAC (\(2^{-60}\)); certain detection with redundancy
Slow compromise over months Proactive refresh plus epoch IDs
Timing side channel Branch-free arithmetic, fixed-schedule pow, all-limb constant-time tag check
Memory remanence write_volatile zeroisation of every secret buffer; output files created with mode 0600
Supply chain Zero third-party crates; kernel CSPRNG
Malformed input Canonical-encoding (\(\lt p\)), duplicate-index, cross-dealing, range and padding checks

Side-channel evidence. Compiled with rustc -O for x86-64, Fp::mul (22 instructions), add/sub (10), ct_eq (4) and the reduction (12) contain 0 conditional branches. pow has exactly one, its fixed 64-iteration loop counter. scripts/asm_audit.sh reproduces this. A dudect-style Welch \(t\)-test is also included (kavach ctcheck).

What makes it different

  • Shamir: no validation at all.
  • Feldman/Pedersen VSS: only computationally secure, and broken by quantum computers.
  • Rabin–Ben-Or: information-theoretic, but needs \(O(n^2)\) pairwise tags.
  • Kavach-SS: the extended Cauchy generator turns privacy into a single determinant condition, and one shared MAC key gives validation for just \(L+1\) extra field elements per share. Everything is information-theoretic and post-quantum.

Real-world use (extra point)

A working, zero-dependency Rust CLI (low-level-language bonus):

kavach genkey  -o master.key
kavach split   -t 3 -n 5 -i master.key -o shares/
kavach combine -o rec.key shares/share-2.kv shares/share-4.kv shares/share-5.kv
kavach verify  shares/*.kv     # validate without writing the key
kavach refresh shares/*.kv     # new epoch
kavach audit   -t 5 -n 12      # checks all 792 + 495 Cauchy minors
kavach demo                    # attack scenarios

The test suite has 11 tests, all passing: exhaustive subset reconstruction, a tamper test at every share position, targeted forgery (0 of 500 succeed), cross-dealing rejection, refresh, encoding fuzz, a \(\chi^2\) uniformity test on \(t-1\) shares, and exhaustive minor checks for every \(n\le 8\).

Challenges we ran into

Our first timing harness falsely reported leaks. It only called the RNG before measuring the random-input class, so it was measuring cache pollution, not arithmetic. We rebuilt it the way dudect does, generating all inputs up front, and added the assembly audit as the stronger guarantee.

Accomplishments we're proud of

Every security claim is either proved (Theorems 1–4) or machine-checked (exhaustive minors, branch counts, tests).

What we learned

The Cauchy determinant identity does a lot of work here: one identity gives MDS reconstruction, perfect privacy, and error detection.

Limitations (stated honestly)

The dealer and combiner briefly hold \(K\); that is the one remaining window, and it is minimised by zeroisation. Physical power and EM analysis are out of scope. \(t\) colluding holders can recover \(K\) by definition.

What's next

A fully distributed refresh protocol over the network, plus mlock'd memory for the combine step.

Built With

Share this project:

Updates

Submission history