[Cryptography] A discussion about secret sharing or multi-sig

[Osman Kuzucu]

Assume that I control a private key Apr that can generate the signed message MA and give it to local shelter and they can exchange for goods from a nearby grocery store. Later grocery store owner can show  MA to me and I would pay him how much the goods costed. I use that method because I want to make sure that store owner can verify that I am indeed going to be paying the stuff people buy with my signature. When I am away, I would want at least n of my m children to come together and generate new signed message MA' so that they can give it to the other shelter and the other shelter can also buy some food from the store.

Cryptographically I can use Shamir's secret sharing scheme, however once my children reveals the shares they have, one child can memorize the others' secret and later recombine them to get Apr and start buying things from the store which I or my other children didn't approve.

The way Bitcoin handles this is that every children signs the message and generates their own M1 M2 M3 ... etc. so in my scenario I would have to let the store owner know "either see MA from me or get at least n signed messages from m of my children". And I also would have to provide my children's public keys to the store owner upfront so they could know which signatures will be accepted. This solution might seem feasible but as the amount children I have (m) and signatures required (n) increases, it becomes a tough problem for the store owner to save each children's data and later validate each signature.

Is there a cryptographically secure way in threshold cryptography where at least n of my children can get together and create the signed message MA without directly accessing the private key Apr ?

I have thought about encapsulation like in the TOR protocol. Assuming that the youngest one of n children who are going to be signing starts first with the raw data, signs it to create Myoungest and later the second youngest signs the  Myoungest with their private key to generate new signed message and this keeps going on until the eldest one signs it. And they hand that final signed message + the order they signed to the store to get what they want. Now the store owner only receives one signed message but can verify that at least n out of m children signed the message. The downside of this method is that the message can't be synchroniously signed. However,  it reduces the amount of data transferred to the store. The store owner would still have to have all public keys for all of my children, but this time receives only one signed message instead of n signed messages.

What are your thoughts on this? Would it be efficient? Or it would be more efficient to deliver n messages separately instead of encapsulating? Both methods require the storage of m public keys and verifying individual signatures for n times.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210725/0e3ffc9f/attachment.htm>