Institute of Information Theory and Automation

You are here

Secret sharing and duality

2019-06-17 14:00
Name of External Lecturer: 
Laszlo Csirmaz
Affiliation of External Lecturer: 
CEU, Department of Mathematics and Its Applications, Hungary

Secret sharing is an important building block in cryptography. Up to now all explicitly defined secret sharing schemes are multi-linear, thus are closely related to linear codes. The dual of such linear scheme, in the sense of duality of linear codes, gives another scheme for the dual access structure. These schemes have the same complexity, namely the largest share size relative to the secret size is the same. It is a long-standing open problem whether this fact is true in general: the complexity of any access structure is the same as the complexity of its dual. We give an almost answer to this question. An almost perfect scheme allows negligible errors, both in the recovery and in the independence. There exists an almost perfect scheme whose complexity is strictly smaller than that of its dual. Interestingly, we can prove the existence only without specifying what the access structure is.

2019-05-20 16:03