Paper 2026/1769

Rank Measures and Exponential Lower Bounds for Multilinear Secret Sharing

Abstract

Multilinear secret sharing can amortize share size over a vector secret, so scalar linear lower bounds need not survive normalization by the secret dimension. We prove that the Razborov–G´al rank measure does survive this amortization: every multi-target monotone span program satisfies a rank inequality in which the target dimension appears multiplicatively. Combined with the characteristic-separated witnesses of Pitassi and Robere, this gives an explicit family of access structures whose average and maximum multilinear information ratios are exponential over every finite field, settling the worst-case order at $2^{\Theta(n)}$. We also study arbitrary sharing algorithms with affine-linear reconstruction under non-perfect security notions, including the pairwise statistical security of Beimel–Othman–Peter and the partial privacy of Jafari–Khazaei. Combining these affine-reconstruction results with the degree-reduction theorem of Beimel–Othman–Peter gives corresponding fixed-degree lower bounds under both security notions, in particular for subexponential secret dimension.