Paper 2013/503

On secret sharing with nonlinear product reconstruction

Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Carles Padro and Chaoping Xing

Abstract

Multiplicative linear secret sharing is a fundamental notion in the area of secure multi-party computation (MPC) and, since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that ``the product of two secrets is obtained as a linear function of the vector consisting of the coordinate-wise product of two respective share-vectors''. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we {\em abandon the latter linearity condition} and instead require that this product is obtained by {\em some}, not-necessarily-linear ``product reconstruction function''. {\em Is the resulting notion equivalent to multiplicative linear secret sharing?} We show the (perhaps somewhat counter-intuitive) result that this relaxed notion is strictly {\em more general}. Concretely, fix a finite field $\FF_q$ as the base field $\FF_q$ over which linear secret sharing is considered. Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players $n$ such that it has $t$-privacy with $t\approx \sqrt{n}$ and such that it does admit a product reconstruction function, yet this function is {\em necessarily} nonlinear. Our proof is based on combinatorial arguments involving bilinear forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.