Library doesn't seem to support adding shares to an existing shared secret

[samuel-allan]

Hi!
I am implementing a system, where it is required to generate extra shares once the initial quantity was generated, which can then be used in combination with some of the existing shares in order to retrieve the secret.

Basically what I'm looking for is the ability to do the following:

1. Share a secret 'foo' with a required share count 'quorum' of 2, and generate 5 initial shares: s1, s2, s3.. s5.
2. Suddenly, I want to generate another share in the collection (i.e. s6), which would remain consistent with both the secret and the rest of the existing shares 1-5
3. For example, now I can provide shares s5 and s6, and it will still give me the secret 'foo'.

I personally am in great need of such a feature, and even though I realize, of course, that this is probably not a mandatory feature in general, I would very much appreciate if it were possible to incorporate it into the library.

In general though, I think this is one of the best (and only) libraries that support this valuable cryptographic function for PHP.

Regards.

[marcinlawnik]

This would be problematic, as it is impossible to assure that the new share will be unique from previously generated ones.
See an answer over here (second answer):
http://crypto.stackexchange.com/questions/37550/secret-sharing-scheme-with-ability-to-add-or-update-share-number

This means that in some combinations it would be impossible to recover the secret, and the chance of that occuring would increase with each new share generated.

[ogmueller]

I do agree. Even though that it is not a theoretical problem, because generating n number of additional keys is not a problem for the algorithm itself. It is rather an implementation problem.

I guess there are at least 2 solutions to this problem:

1. currently we use positive integer x-values (1, 2, 3, 4, .., n) depending on how many keys were created. So if someone likes to calculate any additional keys, he could provide us with the number of keys, which have been generated already. So if n was 5, we start to create keys with 6, 7, ..., n. If this person doesn't know the number, it could be problematic though.

2. instead of using positive integer for x-values, we could choose random x-values. Depending on the "randomness" (range), there could be still collisions though, but it might be better than asking for number of previous generated keys. But this might change quite a bit of the code.

[samuel-allan]

Another thing, to avoid collisions you could specify a large enough field size (such as 2^128), which would work fine, however, since PHP has no in-built support for BIGINTS this too, could be problematic. Providing the number of shares seems like a nice option to be honest, since it is in most cases fairly easy to calculate (e.g. number of rows in a database, e.t.c.)

…

On Thu, Dec 15, 2016 at 3:38 PM, Oliver Mueller ***@***.***> wrote: I do agree. Even though that it is not a theoretical problem, because generating n number of additional keys is not a problem for the algorithm itself. It is rather an implementation problem. I guess there are at least 2 solutions to this problem: 1. currently we use positive integer x-values (1, 2, 3, 4, .., n) depending on how many keys were created. So if someone likes to calculate any additional keys, he could provide us with the number of keys, which have been generated already. So if n was 5, we start to create keys with 6, 7, ..., n. If this person doesn't know the number, it could be problematic though. 2. instead of using positive integer for x-values, we could choose random x-values. Depending on the "randomness" (range), there could be still collisions though, but it might be better than asking for number of previous generated keys. But this might change quite a bit of the code. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#3 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AF9Y9DAw0yg687fkht5E2QpDYUGkyWaMks5rITStgaJpZM4K3S-_> .

-- *Samuel Allan* [email protected] *Work Email* [email protected]

[samuel-allan]

Checking back to see if there are any final thoughts? :)
Thanks!