[Cryptography] About Secret Sharing Schemes and a Question

Phillip Hallam-Baker phill at hallambaker.com
Wed Jun 5 14:37:47 EDT 2019


On Wed, Jun 5, 2019 at 10:41 AM Osman Kuzucu <bizbucaliyiz at hotmail.com>
wrote:

>
>
>
> Phillip Hallam-Baker <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> wrote:
>
>> On Mon, Jun 3, 2019 at 8:39 AM Osman Kuzucu <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 *D*i+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
> get*encrypted 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 key*K* 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.
>

This discussion was very useful as I have suddenly realized I can in fact
support pretty much exactly the use case that I believe likely to turn up
in practice.

First to rewind, I divide the traditional CRM/DRM problem into two parts:
Confidential Document Control and Redistribution Control. I define the
first problem to be meeting requirements concerning controlled release of
documents etc. to a user and the second to be requirements governing what
they can do with the material after they have acquired it.

My strong belief is that obsessing about the redistribution problem has
caused us to effectively punt on the control problem. Redistribution is a
really really hard problem that requires trustworthy hardware and imposes
serious usability obstacles on users. So we have documents that are
unencrypted and available to 20,000 people in an organization instead of
just the 200 that might actually need them because we can't get a handle on
the theoretical problem of one of the 200 misusing them.

I do have an answer to the redistribution issue but it is an accountability
approach, not a control approach: Log access to the documents in real time,
put a value on each one and flag excessive consumption on access. If a low
level tech is reading every diplomatic cable, find out why.


But anyway, the way I (may) end up implementing Shamir Secret Sharing in
the Mesh is a fairly simple twist on the code already written which shares
a decryption key x between two parties x = a + b. So to calculate e^y^x we
calculate e^y^a . e ^y^b.

In the existing code, the private key a typically lives in the cloud on a
server and is called the recryption key. Its partner decryption key b is
encrypted under the user's decryption key and can be registered on the
cloud server along with a. The effect being that the user can only decrypt
if the cloud service permits this by using the recryption key to do its
part of the work but the recryption service cannot decrypt by itself.


So let us consider the problem where we want a particular document to be
available if 3 out of 5 recryption services permit. We encrypt the document
under a master key m as usual and then split the master key using Shamir
secret sharing 3 of 5 times and encrypt each share under the master key of
a different service.

This is a lot simpler than the schemes I have seen written up in the lit.
But it meets the needs I see which have much more to do with being robust
in the face of service failures or mitigating coercion attacks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190605/e34bf4e7/attachment.html>


More information about the cryptography mailing list