Abstract

Using information inequalities, we prove any unrestricted arithmetic circuits computing the shares of any (t,n)-threshold secret sharing scheme must satisfy some superconcentrator-like connection properties. 

In the reverse direction, we prove, when the underlying field is large enough, any graph satisfying these connection properties can be turned into a linear arithmetic circuit computing the shares of a (t,n)-threshold secret sharing scheme. Specifically, n shares can be computed by a linear arithmetic circuits with O(n) wires in depth O(α(t,n)), where α(t,n) is the two-parameter version of the inverse Ackermann function. For example, when n≥t^2.5, depth 2 would be enough; when n≥tlog^2.5 t, depth 3 would be enough.

Time

2023-06-18  11:30 - 12:00   

Speaker

Yuan Li, Fudan University 

Room

Guangdong Hotel