Threshold Secret Sharing Requires a Linear-Size Alphabet

Bogdanov, A; Guo, SY; Komargodski, I

Bogdanov, A (corresponding author), Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Peoples R China.

THEORY OF COMPUTING, 2020; 16 ():

Abstract

We prove that for every n and 1 < t < n any t-out-of-n threshold secret sharing scheme for one-bit secrets requires share size log(t + 1). Our b......

Full Text Link