Welcome to the resource topic for 2024/1781
Title:
New results in Share Conversion, with applications to evolving access structures
Authors: Tamar Ben David, Varun Narayanan, Olga Nissenbaum, Anat Paskin-Cherniavsky
Abstract:We say there is a share conversion from a secret sharing scheme \Pi to another scheme \Pi' implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret sharing under \Pi to a valid (but not necessarily random) secret sharing under \Pi' of the same secret. If such a conversion exists, we say that \Pi\ge\Pi'. This notion was introduced by Cramer et al. (TCC’05), where they particularly proved that for any access structure (AS), any linear secret sharing scheme over a given field \mathbb{F}, has a conversion from a CNF scheme, and is convertible to a DNF scheme.
In this work, we initiate a systematic study of convertability between secret sharing schemes, and present a number of results with implications to the understanding of the convertibility landscape.
- In the context of linear schemes, we present two key theorems providing necessary conditions for convertibility, proved using linear-algebraic tools. It has several implications, such as the fact that Shamir secret sharing scheme can be neither maximal or minimal. Another implication of it is that for a broad class of access structures, a linear scheme where some party has sufficiently small share complexity, may not be minimal.
- Our second key result is a necessary condition for convertibility to CNF from a broad class of (not necessarily linear) schemes. This result is proved via information-theoretic techniques and implies non-maximality for schemes with share complexity smaller than that of CNF.
We also provide a condition which is both necessary and sufficient for the existence of a share conversion to some linear scheme. The condition is stated as a system of linear equations, such that a conversion exists iff. a solution to the linear system exists. We note that the impossibility results for linear schemes may be viewed as identifying a subset of contradicting equations in the system.
Another contribution of our paper, is in defining and studying share conversion for evolving secret sharing schemes. In such a schemes, recently introduced by Komargodski et al. (IEEE ToIT’18), the number of parties is not bounded apriori, and every party receives a share as it arrives, which never changes in the sequel. Our impossibility results have implications to the evolving setting as well. Interestingly, that unlike the standard setting, there is no maximum or minimum in a broad class of evolving schemes, even without any restriction on the share size.
Finally, we show that, generally, there is no conversion between additive schemes over different fields, however by degrading to statistical security, it may be possible to create convertible schemes.
ePrint: https://eprint.iacr.org/2024/1781
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .