Error correcting and complexity aspects of linear secret sharing schemes.
In: Boyd, C and Mao, W, (eds.)
INFORMATION SECURITY, PROCEEDINGS.
(pp. 396 - 407).
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.
|Title:||Error correcting and complexity aspects of linear secret sharing schemes|
|Event:||6th International Information Security Conference (ISC 2003)|
|Dates:||2003-10-01 - 2003-10-03|
|Keywords:||secret sharing, VSS, modules, error correcting codes, CODES|
|UCL classification:||UCL > School of BEAMS > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
Archive Staff Only