International Association
for Cryptologic Research

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.