{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:26:39Z","timestamp":1787325999581,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 \u201cproduct reconstruction function.\u201d 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 ${\\mathbb 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.<\/jats:p>","DOI":"10.1137\/130931886","type":"journal-article","created":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T11:52:36Z","timestamp":1435146756000},"page":"1114-1131","source":"Crossref","is-referenced-by-count":2,"title":["On Secret Sharing with Nonlinear Product Reconstruction"],"prefix":"10.1137","volume":"29","author":[{"given":"Ignacio","family":"Cascudo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald","family":"Cramer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Diego","family":"Mirandola","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carles","family":"Padr\u00f3","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chaoping","family":"Xing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"atypb1","unstructured":"N. Bourbaki,\n                      Algebra\n                      I, Springer-Verlag, New York, 1989."},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson,\n                      Completeness theorems for non-cryptographic fault-tolerant distributed computation\n                      , in Proceedings of STOC 1988, ACM Press, New York, 1988, pp. 1-10.","DOI":"10.1145\/62212.62213"},{"key":"atypb3","first-page":"466","author":"Cascudo I.","year":"2009","journal-title":"New York"},{"key":"atypb4","first-page":"685","author":"Cascudo I.","year":"2011","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Cre\u0301peau, and I. Damgaard,\n                      Multi-party unconditionally secure protocols\n                      , in Proceedings of STOC 1988, ACM Press, New York, 1988, pp. 11-19.","DOI":"10.1145\/62212.62214"},{"key":"atypb6","first-page":"516","author":"Chen H.","year":"2006","journal-title":"New York"},{"key":"atypb7","first-page":"291","author":"Chen H.","year":"2007","journal-title":"New York"},{"key":"atypb8","first-page":"316","author":"Cramer R.","year":"2000","journal-title":"New York"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"J. Dieudonne\u0301,\n                      La Ge\u0301ome\u0301trie des Groupes Classiques\n                      , 2nd ed., Springer-Verlag, New York, 1963.","DOI":"10.1007\/978-3-662-59144-4"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(78)90202-8"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. K. Franklin and M. Yung,\n                      Communication complexity of secure computation (extended abstract)\n                      , in Proceedings of STOC 1992, ACM Press, New York, 1992, pp. 699-710.","DOI":"10.1145\/129712.129780"},{"key":"atypb12","first-page":"21","author":"Ishai Y.","year":"2007","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"T. Y. Lam,\n                      Introduction to Quadratic Forms over Fields\n                      . Grad. Stud. Math. 67, AMS, Providence, RI, 2005.","DOI":"10.1090\/gsm\/067"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"S. Roman,\n                      Advanced Linear Algebra\n                      , 3rd ed., Springer-Verlag, New York, 2008.","DOI":"10.1007\/978-0-387-72831-5"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"J.P. Serre,\n                      A course in arithmetic\n                      , Grad. Texts in Math. 7, Springer-Verlag, New York, 1973.","DOI":"10.1007\/978-1-4684-9884-4"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130931886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:25:23Z","timestamp":1787322323000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130931886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130931886"],"URL":"https:\/\/doi.org\/10.1137\/130931886","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}