[Cryptography] About Secret Sharing Schemes and a Question

[Osman Kuzucu]

Phillip Hallam-Baker <phill at hallambaker.com<mailto:phill at hallambaker.com>> şunları yazdı (4 Haz 2019 23:10):
On Tue, Jun 4, 2019 at 2:12 AM Bill Cox <waywardgeek at gmail.com<mailto:waywardgeek at gmail.com>> wrote:
On Mon, Jun 3, 2019 at 8:39 AM Osman Kuzucu <bizbucaliyiz at hotmail.com<mailto:bizbucaliyiz at hotmail.com>> wrote:

Also, as for the application of the scheme, I wanted to ask one more situation. Assuming we have a secret S (a private key maybe?) distributed to n different secret share holders by using a secret sharing scheme, and we are periodically (say every month) producing data, namely D1, D2, D3 ... Dn. Our rule is, if k amount of people come together, they should be able to produce a data Di, which would be verifiable by the public that it was generated by at least k amount of share holders' collaboration. However, we do not want any share holder, or anyone from public to learn the actual secret S, so that no share holder, who contributed to the data production, will not be able to produce any other data Di+1 in the future without other share holders' help. As far as I know, at all secret sharing schemes collaborating once is enough for share holders to learn the main secret S (in the case of the papers, it was almost an integer number). Is there a way that we could use, or maybe combine public-private viewkeys, or make the secret S some encrypted data, or any other thing that would allow such real life application?

Sure, you can use partially-homomorphic ElGamal threshold encryption based on Shamir secret sharing.  You want to add a way for each member to prove they did their end of the computation honestly, so you'll need some custom zero-knowledge proofs.  There are frameworks for generating them for code like this.  You can encrypt, decrypt, re-encrypt to a new public key, or sign which such a scheme.  No member learns anything about the shared secret, and every so often the group can re-key, so if an attacker has some shares < t, those shares become useless.

There are some very nice theoretical schemes but when you start to implement them for real, they tend to collapse down to all being variants of the same thing.

This is a work in progress.
https://datatracker.ietf.org/doc/draft-hallambaker-mesh-architecture/

I use Shamir Secret sharing for the purpose of providing a key escrow mechanism that does not depend on hardware for key recovery.

I also use a very simple key splitting mechanism where I require m of m keys to be used to decrypt. This covers the case where Alice wants to read her end-to-end encrypted mail on her mobile phone but have some means of disabling access if the phone is lost, she is passing through customs, etc. So if her private key a = x+y, she puts x on her phone and y in the cloud. The cloud machine cannot encrypt on its own and neither can her mobile. They must both co-operate.
Now I can imagine extending the same approach to allow the key to be split so that n<m keys are required to decrypt. It is just a matter of working out the math. I am sure someone has done it. What I find harder to understand is a real world use case or how to construct a user experience that is viable.

Sure call the result homomorphic encryption if you like but I don't think it comes close to meeting the criteria. In fact, the technique I am using was probably developed before the term homomorphic encryption was established. For a system to be called homomorphic, I want to be able to give it a non-trivial calculation to perform on that data and get back a result. Otherwise it is just a threshold key scheme and those problems were solved to my satisfaction back in the 1990s and all the patents therof have expired.


Thanks a lot for the reply!

I think at this point I realized that, whatever I do, there is no way of me knowing if some malicious share holder revealed their key to other third parties, or leaked information or not. We can know if they are honestly giving us their share, but we can not know if they did something else with it, or not. Because we are doing digital encryption, and not giving real physical amulets to any knight, we can't know some things for certain.

And I realized it all depends on the real life applications of above mentioned protocols, because when I think about it, there has to be a person first, who decides what is the SECRET. So actually, one man on the earth already knows what's the secret, and distributes the keys before the key owners themselves see the key. It all comes down to a point, where a centralized server would ask for the keys from each share holder, and verify their integrity.

even better application could be, generating a master private key K, and a secret S, encrypt the secret S with the private master key K to getencrypted data Se. Later, divide that Se to how many parts we want, according to any secret sharing scheme and distribute them. Once enough share holders come together, they can reveal only the encrypted data Se, but not the actual secret S. And as for verification, the key master, or the centralized official app, could just use their own master view key (view key of K) to make sure those share holders actually collaborated. And at any point, if the key master is worried about the shares being leaked (so the generation of Se from those shares actually don't prove that real share holders collaborated ) key master can simply change the private keyK to some other private key K', then generate a new S'e by using that K', and re-distribute new shares for the S'e. This way allows key master to make sure, even if all share holders act malicious and they publicly announce their shares, no one still can reach the main secret S, because it never got revealed in any way. Of course, by adding extra security measures as in your e-mail, we can add more cryptographic measures (threshold encryption or better distribution way) to make it as secure as possible. But our standing point of secret not being revealed at all allows us to secure our secret even if all shares get leaked. This eliminates the risk of malicious share holders selling their keys or other stuff. As once key master realizes such activity, key master changes the master private key and even if people calculate Se from the previous shares, no problem at all.

As for verifying the message from public, I believe it is better for them to trust one authorized person's approval (key master claiming that everyone collaborated) than trusting n different share holders about their honesty. Key master can lie to the public, but at the end, he was the one who created and distributed shares. If key master wanted to lie to others, he wouldn't share the keys with others at the first place.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190605/4b96b0e7/attachment.html>