Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/80963
Title: On Secret Sharing with Nonlinear Product Reconstruction
Authors: Cascudo, Ignacio
Cramer, Ronald
Mirandola, Diego
Padró, Carles
Xing, Chaoping
Keywords: (arithmetic) secret sharing
Issue Date: 2015
Source: Cascudo, I., Cramer, R., Mirandola, D., Padró, C., & Xing, C. (2015). On Secret Sharing with Nonlinear Product Reconstruction. SIAM Journal on Discrete Mathematics, 29(2), 1114-1131.
Series/Report no.: SIAM Journal on Discrete Mathematics
Abstract: Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty computation 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 coordinatewise 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 abandon the latter linearity condition and instead require that this product is obtained by some, not-necessarily-linear “product reconstruction function.” Is the resulting notion equivalent to multiplicative linear secret sharing? We show the (perhaps somewhat counterintuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field F_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 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.
URI: https://hdl.handle.net/10356/80963
http://hdl.handle.net/10220/39034
ISSN: 0895-4801
DOI: 10.1137/130931886
Schools: School of Physical and Mathematical Sciences 
Rights: © 2015 Society for Industrial and Applied Mathematics. This paper was published in SIAM Journal on Discrete Mathematics and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The published version is available at: [http://dx.doi.org/10.1137/130931886]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
On Secret Sharing with Nonlinear Product Reconstruction.pdf242.62 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

3
Updated on Mar 13, 2024

Web of ScienceTM
Citations 50

1
Updated on Oct 30, 2023

Page view(s) 20

682
Updated on Mar 18, 2024

Download(s) 20

178
Updated on Mar 18, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.