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

[Thierry Moreau]

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) 
> 	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.3353
> 
> 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!

Regards,

-- 
- Thierry Moreau



> 	Tanja
> 


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com