• Calendar

March 8, Tuesday
12:00 – 14:00

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone.

However, the naive way of computing it is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we by-pass this addition step and construct a polynomial size logarithmic depth monotone circuit for every weighted threshold function, Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes.

Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure.