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.