**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.

**Category / Keywords: **foundations / (arithmetic) secret sharing

**Date: **received 15 Aug 2013, last revised 10 Sep 2013

**Contact author: **i cascudo at cwi nl

**Available format(s): **PDF | BibTeX Citation

**Version: **20130910:090609 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]