[Cryptography] About Secret Sharing Schemes and a Question

Phillip Hallam-Baker phill at hallambaker.com
Tue Jun 4 16:10:10 EDT 2019

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.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190604/605605f2/attachment.html>

More information about the cryptography mailing list