Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

Paper 2013/503

On secret sharing with nonlinear product reconstruction

Ignacio Cascudo, Ronald Cramer, Diego Mirandola, 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 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 = \Omega(n)$ and such that it does admit a product reconstruction function, yet this function is {\em necessarily} nonlinear. In addition, we determine the minimum number of players for which those exotic schemes exist. Our proof is based on combinatorial arguments involving quadratic forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.

Note: Updated publication info.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. SIAM Journal on Discrete Mathematics 29 (2), 1114-1131
DOI
10.1137/130931886
Keywords
(arithmetic) secret sharing
Contact author(s)
ignacio @ cs au dk
History
2016-07-18: last of 5 revisions
2013-08-17: received
See all versions
Short URL
https://ia.cr/2013/503
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/503,
      author = {Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Carles Padro and Chaoping Xing},
      title = {On secret sharing with nonlinear product reconstruction},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/503},
      year = {2013},
      doi = {10.1137/130931886},
      url = {https://eprint.iacr.org/2013/503}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.