How can I have a message signed by other shares of a private key without revealing it?

nl flag

I am looking for guidance on implementing a protocol where a BLS private key is split into 2 out of 3 shares using Shamir's Secret Sharing, and signatures must be obtained without revealing the original message to the other parties.

Here's my current approach:

Alice has a BLS private key. She splits this private key into 3 shares, $s_a$, $s_b$, and $s_c$, using Shamir's Secret Sharing. Alice then sends Bob the share $s_b$, retaining $s_a$ and $s_c$ herself. Alice can forget the full private key as she can recover it at any time with $s_c$.

When Alice wants to sign a message $m$ under the original full private key, she signs it with her share $s_a$ and gets a partial signature $\text{sig}_a$. Alice needs Bob to sign the same message $m$ with $s_b$ to get another partial signature $\text{sig}_b$, and send it back to her. She then adds $\text{sig}_a$ and $\text{sig}_b$ to get the full signature $\text{sig}$, which is as if it has been signed by the full private key.

However, I am facing a problem. Alice doesn't want Bob to know the message $m$ she wants to sign. If she sends the plain text message $m$ to Bob for signing, Bob will know the content of the message.

I considered using Paillier encryption to encrypt the message $m$ with a public key, sending Bob the encrypted message $\text{enc}_m$. In this scenario, Bob would sign the encrypted message $\text{enc}_m$ with his share $s_b$, sending the partial signature $\text{sig}_{\text{enc}_m}$ back to Alice.

But I see another issue here. As Bob's partial signature $\text{sig}_{\text{enc}_m}$ is signed on the encrypted message, when Alice decrypts Bob's partial signature, she isn't necessarily getting what she expects, i.e., if I understood correctly, she won't get the partial signature of the raw message $m$ signed with Bob’s share $s_b$. Or will she?

How should I implement such a protocol while not revealing the message to Bob? Would this be even feasible to do so?

PS: I've used BLS here only because I'm not sure if ECDSA signature scheme would even be possible as I have read about its non-linear nature. If ECDSA is easier and more feasible, I'm happy to change.

nl flag
BTW, I'm rather new to crypto and I'm still learning. I will surely appreciate any details and explanations! And will be great if there is a least complex solution that still works to achieve this for an app developer who is new to crypto. :)
Richard Thiessen avatar
mx flag
This feels like an extreme [XY problem]( What are your actual requirements? Why are you using Shamir secret sharing? Do you need to split the signing key between many participants or only two? Only three? Is this a 2 of 3 situation where Alice can sign on her own and Bob and Carol can collaborate? What are you actually trying to accomplish? BLS isn't necessary. Blind Schnorr signatures are straightforward if you need to hide `M` even with key shares.

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.