UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Error correcting and complexity aspects of linear secret sharing schemes

Desmedt, Y; Kurosawa, K; Le, TV; (2003) Error correcting and complexity aspects of linear secret sharing schemes. In: Boyd, C and Mao, W, (eds.) INFORMATION SECURITY, PROCEEDINGS. (pp. 396 - 407). SPRINGER-VERLAG BERLIN

Full text not available from this repository.

Abstract

Linear secret sharing schemes and general access structures have played a key role in modern cryptography. Cramer-Damgard-Maurer recently proved that any linear secret sharing scheme over a finite field can be a verifiable one. We give a simple proof based on error-correcting codes. Our proof allows us to generalize the Cramer-Damg (a) over circle rd-Maurer's result to linear schemes over modules, which played an important role in threshold cryptography, i.e. any existing linear secret sharing scheme over a module can be changed into a verifiable one. We then reflect on another aspect of linear secret sharing. While there has been lots of research on bounds in general access secret sharing schemes, little has been done on the computational complexity aspects. In this paper we also demonstrate that verifying whether a linear scheme is a secret sharing scheme for a given access structure is coNP-complete. The later result relates to the problem cheating sharedealer, the dual problem of secret sharing.

Type:Proceedings paper
Title:Error correcting and complexity aspects of linear secret sharing schemes
Event:6th International Information Security Conference (ISC 2003)
Location:BRISTOL, ENGLAND
Dates:2003-10-01 - 2003-10-03
ISBN:3-540-20176-9
Keywords:secret sharing, VSS, modules, error correcting codes, CODES
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record