Is this the first ever practically-deployed use of a threshold scheme?

Tanja Lange tanja at
Tue Aug 3 23:25:50 EDT 2010

> 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?

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list