Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

On the Impossibility of d-Multiplicative Non-perfect Secret Sharing

Maki Yoshida, Toru Fujiwara

Published Jan 1, 2015• 3 citations
Publisher

Abstract

A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. In the previous work, the following negative result for perfect secret sharing has been shown: The d-multiplicative secret sharing for d players is impossible. This paper extends the impossibility result to non-perfect secret sharing. Our main result is a proof that d-multiplicative secret sharing for d players is impossible even if every player has partial information on the secret (e.g., all but one bit). This result means that there is no need to relax the privacy requirement with leakage of partial information only for the purpose of d-multiplication.

DOI
10.1587/transfun.e98.a.767

Related papers

Hybrid Multiplicative Non-perfect Secret Sharing

Maki Yoshida

A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. This paper considers the most general setting where d secrets are independently shared by different adversary structures (hybrid) and a partial information can be leaked (non-perfect) and presents a necessary and sufficient condition for d-multiplication to be possible. In particular, even for the extreme case that the i-th secret is known by all but the i-th player who has partial information on the secret (e.g., all but one bit), d-multiplication is impossible.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•0 citations

Hybrid Multiplicative Secret Sharing

Maki Yoshida

A secret-sharing scheme is d-multiplicative if it allows the players to multiply d (rather than two) shared secrets (without recovering them) by locally converting their shares into an additive sharing of the product. In this work, the d-multiplicative secret-sharing (MSS) is extended to a hybrid MSS (HMSS), which is mainly designed for sharing d secrets against different access structures. A necessary and sufficient condition for n-player d-HMSS schemes to exist is presented. The condition is necessary for arbitrary (possibly inefficient or even nonlinear) secret-sharing schemes.

IEEE Information Theory Workshop (ITW)•Oct 17, 2021•1 citation

d-Multiplicative Secret Sharing for Multipartite Adversary Structures

Reo Eriguchi, Noboru Kunihiro

Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), j∈[d] can be converted into an additive share of the product ∏_{j∈[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n. In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any 𝓁-partite adversary structure of type Q_d whose information ratio is O(n^{𝓁+1}). Our schemes are applicable to the class of all the 𝓁-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if 𝓁 is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of 𝓁-partite adversary structures into ℝ^𝓁, we introduce a class of 𝓁-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.

Leibniz international proceedings in informatics•Jan 1, 2020•0 citations

On Secret Sharing with Nonlinear Product Reconstruction

Ignacio Cascudo, Ronald Cramer, Diego Mirandola +2 more

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 ${\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.

SIAM Journal on Discrete Mathematics•Jan 1, 2015•3 citations

On secret sharing with nonlinear product reconstruction

Ignacio Cascudo, Ronald Cramer, Diego Mirandola +2 more

Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty 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 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 counter-intuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field Fq as the base field Fq 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 ≈ √ n and such that it does admit a product reconstruction function, yet this function is 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.

•Aug 1, 2013•0 citations

On the Size of a Share for Non-perfect Secret Sharing Schemes

Maki Yoshida

In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by $\frac{{{2^k} - 1}}{k} \cdot H(s)$, where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a $\frac{1}{L}$ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of $\frac{{{2^k} - 1}}{{kL}} \cdot H(s)$, under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely $\frac{{{2^k} - 2 + 1/L}}{k} \cdot H(s)$, which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations
A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. In the previous work, the following negative result for perfect secret sharing has been shown: The d-multiplicative secret sharing for d players is impossible. This paper extends the impossibility result to non-perfect secret sharing. Our main result is a proof that d-multiplicative secret sharing for d players is impossible even if every player has partial information on the secret (e.g., all but one bit). This result means that there is no need to relax the privacy requirement with leakage of partial information only for the purpose of d-multiplication.
A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. This paper considers the most general setting where d secrets are independently shared by different adversary structures (hybrid) and a partial information can be leaked (non-perfect) and presents a necessary and sufficient condition for d-multiplication to be possible. In particular, even for the extreme case that the i-th secret is known by all but the i-th player who has partial information on the secret (e.g., all but one bit), d-multiplication is impossible.
A secret-sharing scheme is d-multiplicative if it allows the players to multiply d (rather than two) shared secrets (without recovering them) by locally converting their shares into an additive sharing of the product. In this work, the d-multiplicative secret-sharing (MSS) is extended to a hybrid MSS (HMSS), which is mainly designed for sharing d secrets against different access structures. A necessary and sufficient condition for n-player d-HMSS schemes to exist is presented. The condition is necessary for arbitrary (possibly inefficient or even nonlinear) secret-sharing schemes.
Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), j∈[d] can be converted into an additive share of the product ∏_{j∈[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n. In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any 𝓁-partite adversary structure of type Q_d whose information ratio is O(n^{𝓁+1}). Our schemes are applicable to the class of all the 𝓁-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if 𝓁 is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of 𝓁-partite adversary structures into ℝ^𝓁, we introduce a class of 𝓁-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.
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 Fq{\mathbb F}_qFq​ 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 nnn such that it has ttt-privacy with t=Ω(n)t = \Omega(n)t=Ω(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.
Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty 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 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 counter-intuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field Fq as the base field Fq 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 ≈ √ n and such that it does admit a product reconstruction function, yet this function is 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.
In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by 2k−1k⋅H(s)\frac{{{2^k} - 1}}{k} \cdot H(s)k2k−1​⋅H(s), where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a 1L\frac{1}{L}L1​ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of 2k−1kL⋅H(s)\frac{{{2^k} - 1}}{{kL}} \cdot H(s)kL2k−1​⋅H(s), under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely 2k−2+1/Lk⋅H(s)\frac{{{2^k} - 2 + 1/L}}{k} \cdot H(s)k2k−2+1/L​⋅H(s), which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.