Is this the first ever practically-deployed use of a threshold scheme?
thierry.moreau at connotech.com
Wed Aug 4 11:23:06 EDT 2010
Tanja Lange wrote:
>> There is more than the UI at stake here, i.e. the basic functionality of
>> the scheme. Say you distribute shares in a 4 out of 7 scheme (ABCDEF)
>> and share A is published on the web. How do you recover from the
>> remaining 3 out of 6 scheme into a 4 out of 6 scheme without having a
>> key ceremony? In an ad-hoc multi-party scheme, you request 4 of the
>> remaining compliant parties to destroy key material allowing them to
>> participate in a group with the traitor A, but no other key material. No
>> system UI, but admittedly a coordination nightmare!
> If the system is built to allow resharing then this is no problem.
> Resharing from a t-out-of-n scheme to an r-out-of-m scheme works as
> follows: If the secret s is shared using the (otherwise random)
> polynomial f of degree t then a share consists of (i,f(i)). To
> reshare, at least t or the original shareholders issue shares of
> f(i) in an r-out-of-m manner, i.e. take a polynomial gi of degree r and
> compute m shares (i,j,gi(j)). When these are distributed to the new
> users, the new users should end up with matching j's. The old shares
> (i,f(i)) are deleted. Each of the m new users now has t shares
> (i1,j,gi1(j)), (i2,j,gi2(j)), ... ,(it,j,git(j)). This information
> can be combined into a single share (j,G(j)) of s by using the Lagrange
> coefficients of the first scheme.
> All of this can be decorated with zero knowledge proofs to prove
> correctness of the shares etc. Note that there is no interaction of the
> t shareholders and everthing can be done remotely.
> In the scenario that one share A is published it's enough to have t-1
> users help in the resharing since every new user can use the public
> information. On the other hand that's a mess to program, so it's more
> resonable to ask t of the remaining shareholders to help. Doesn't sound
> like a coordination nightmare to me.
> For all this in a more general setting see e.g. "Redistributing Secret
> Shares to New Access Structures and Its Applications" by Yvo Desmedt
> and Sushil Jajodia (1997)
> Does this answer the question?
Yes, or at least it gives a good sense that these issues has been dealt
with in the cryptographic literature. It seems to fulfill the
operational requirements (obviously when a good faith participant
receives new shares from a remote party, a trust relationship is needed,
but that is a given irrespective of the underlying crypto).
Thanks a lot for your answer!
- Thierry Moreau
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography