Horcrux: Split your file into encrypted fragments

Not mine, but http://point-at-infinity.org/ssss/ is another good one, with Debian packages.

Except that there are problems with the emergency scenario on both sides:

- In an actual urgent emergency, getting in touch with the 3 people and getting the data might be difficult and take days/weeks. One is on vacation, another is going to take a couple of days to try to remember where they stored the USB key...

- And nothing limits it to emergencies. The 3 people can just get together immediately and examine the valuable information inside, whether it's account numbers, crypto keys, a will, etc.

So the only value here is in not having to remember a separate password. But I expect it's just as likely for people to lose the files entirely as much as it is for them to lose passwords. If you share a password-encrypted file with 5 friends, I wouldn't be surprised if 10 years later, only 1 of them still had it. In that case, better to store file+password per-person, rather than require 3 of them to keep it.

[dead]

You don't need FHE to do this – what you're describing is generically a multi-party compute scheme that can be solved by other means.

Since you have familiarity with signatures, I'll plant the seed of how this particular MPC scheme works, in parts: Distributed Key Generation, and Circuit Creation and Execution

The first step is securely generating a key – but how do you know it was done correctly with SSS? SSS follows what is called a "trusted dealer" model, where you assume what generates the Shamir splits has operated correctly, but can we do better than that? Thankfully, yes! Feldman Verifiable Secret Sharing is an enhancement over SSS, where the splits generated are committed to by raising the coefficients of the SSS polynomial to a public generator of an additively-homomorphic group, or in other words, treating the coefficients like private keys, and producing the public keys (as in elliptic curve cryptography, the private key is just a large scalar number, the public key is produced by performing scalar multiplication of the private key against a known public point – the generator, part of the public parameters of a particular curve). By having the public points (A_0, A_1, ..., A_n) corresponding to the coefficients (a_0, a_1, ..., a_n, where a_0 = secret), you can calculate the secret's commitment by using x=0, as P(x)=A_nx^n+...+A_1x+A_0 where x=0 cancels out all terms besides the secret's commitment. Similarly, you can verify your share split by using x=(your share identifier), then raise your share to the same generator. And finally, to prove that all shares are valid, each person of course must verify their share matches their commitment, but then you can do Lagrange interpolation in the exponent (because the only operations you do over the commitments are multiplying by publicly available scalars (the share identifiers), and adding public points together) across any threshold combination of commitments, they should all resolve to P(0). That's FVSS in a nutshell.

But this still requires a trusted dealer! You have to trust that the dealer itself is not corrupted and exfiltrating secrets. How can we remove the trust component? By having all share holders perform FVSS – each party creates a random polynomial, samples shares accordingly, sends the shares (securely, of course) to each corresponding party, then everyone individually adds their provided (and self-sampled) polynomial samples. Because polynomials can be added together, you have effectively combined the random polynomials of all parties, without any one party knowing the real coefficients. Then verification involves each party raising their shares to a generator like in FVSS, and publishing their public commitments. The same Lagrange interpolation process is performed to verify all threshold combinations of public points resolve to the same public point – essentially confirming the secret was generated correctly without having to reveal the secret.

Now, to use the secret – execution. The technique for this is called Oblivious Transfer – it essentially leverages the same intractability problem of a given cryptosystem (discrete log for elliptic curves) to bootstrap a circuit garbling technique. There's many ways to do this, I'll explain the simplest form, for two parties:

Party 1 generates a public key, private key pair (a, A), and has two choices for messages (m_0, m_1), and sends A to Party 2.

Party 2 generates a private key (b), and a choice bit (c), and depending on c:

  c == 0: Party 2 generates B = b \* A

  c == 1: Party 2 generates B = b \* G + A, where G is the generator of the curve.

Party 2 sends B to Party 1

Party 1 calculates:

  e_0 = Hash(a \* B)

  e_1 = Hash(a \* (B - A))

Party 1 encrypts m_0 with e_0, m_1 with e_1, and sends both encrypted messages.

Party 2 calculates:

  e_c = Hash(b \* A)

Party 2 decrypts m_c with e_c.

Because Party 2 does not know a, they cannot calculate the encryption key for the message they did not choose, as the encryption keys calculated by Party 1 are contingent on an operation on B that cancels out the respective values produced when creating B from the choice, multiplied by the private scalar a.

Additionally, because Party 1 does not know b, they cannot determine which choice Party 2 actually made.

Now, for a simple choice between messages this seems silly, but this is actually sufficient to bootstrap a logical circuit – any computable circuit can be evaluated through this process of oblivious transfer. What does that give us? The ability to jointly compute operations over data required to be kept private by each side, such as an HMAC. Since HMACs are generally used in idempotent operations, generating the HMAC for a request using an OT circuit is sufficient to do what you're wanting.

For basic authentication, you'd need to extend the OT circuit evaluation all the way out to TLS frame construction itself, but is still possible.

NB: I am creating a decentralized network, Quilibrium, to make it easy to build and deploy applications that evaluate as OT circuits – MPC TLS is on the roadmap.

The author of this tool basically took the Shamir code from Hashicorp Vault, which is pretty mainstream. If you're looking for a solid implementation, I would start there[0]. I wouldn't use the Shamir code from this repo, as it's an old version of the vault code using field arithmetic that doesn't run in constant time.

[0]: https://github.com/hashicorp/vault/blob/main/shamir/shamir.g...