Search Results

Documents authored by Paskin-Cherniavsky, Anat

Document
DOI: 10.4230/LIPIcs.ITC.2025.11
New Results in Share Conversion, with Applications to Evolving Access Structures

Authors: Tamar Ben David, Varun Narayanan, Olga Nissenbaum, and Anat Paskin-Cherniavsky

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
We say there is a share conversion from a secret-sharing scheme Π to another scheme Π' implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret-sharing under Π to a valid (but not necessarily random) secret-sharing under Π' of the same secret. If such a conversion exists, we say that Π ≥ Π'. This notion was introduced by Cramer et al. (TCC'05), where they particularly proved that for any access structure, any linear secret-sharing scheme over a given field 𝔽, 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 a scheme may be minimal if its share complexity is at least as high as that of DNF. - 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 if and only if 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, unlike in 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, even from CNF to DNF! However by relaxing from perfect to statistical security, it may be possible to convert, and exemplify this for (n,n)-threshold access structures.
Cite as

Tamar Ben David, Varun Narayanan, Olga Nissenbaum, and Anat Paskin-Cherniavsky. New Results in Share Conversion, with Applications to Evolving Access Structures. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.ITC.2025.11,
  author =	{Ben David, Tamar and Narayanan, Varun and Nissenbaum, Olga and Paskin-Cherniavsky, Anat},
  title =	{{New Results in Share Conversion, with Applications to Evolving Access Structures}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.11},
  URN =		{urn:nbn:de:0030-drops-243610},
  doi =		{10.4230/LIPIcs.ITC.2025.11},
  annote =	{Keywords: secret sharing, linear secret sharing, evolving access structures, share conversion, feasibility}
}
Document
DOI: 10.4230/LIPIcs.ITC.2023.11
MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Authors: Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized" by the protocol participants. Orlandi et al. [Orlandi et al., 2022] initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of [Orlandi et al., 2022] in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, "read-k" non-abelian programs, and "read-k" generalized formulas. Our constructions use a novel abstraction, called incremental function secret-sharing (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).
Cite as

Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi. MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.ITC.2023.11,
  author =	{Keller, Hannah and Orlandi, Claudio and Paskin-Cherniavsky, Anat and Ravi, Divya},
  title =	{{MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.11},
  URN =		{urn:nbn:de:0030-drops-183391},
  doi =		{10.4230/LIPIcs.ITC.2023.11},
  annote =	{Keywords: Secure Multiparty Computation, Bottleneck Complexity, Information-theoretic}
}
Document
DOI: 10.4230/LIPIcs.ITC.2022.16
Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme & Its Consequences

Authors: Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang, Xiuyu Ye, and Albert Yu

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

Abstract
Innovative side-channel attacks have repeatedly exposed the secrets of cryptosystems. Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO-2018) introduced local leakage resilience of secret-sharing schemes to study some of these vulnerabilities. In this framework, the objective is to characterize the unintended information revelation about the secret by obtaining independent leakage from each secret share. This work accurately quantifies the vulnerability of the additive secret-sharing scheme to local leakage attacks and its consequences for other secret-sharing schemes. Consider the additive secret-sharing scheme over a prime field among k parties, where the secret shares are stored in their natural binary representation, requiring λ bits - the security parameter. We prove that the reconstruction threshold k = ω(log λ) is necessary to protect against local physical-bit probing attacks, improving the previous ω(log λ/log log λ) lower bound. This result is a consequence of accurately determining the distinguishing advantage of the "parity-of-parity" physical-bit local leakage attack proposed by Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT-2021). Our lower bound is optimal because the additive secret-sharing scheme is perfectly secure against any (k-1)-bit (global) leakage and (statistically) secure against (arbitrary) one-bit local leakage attacks when k = ω(log λ). Any physical-bit local leakage attack extends to (1) physical-bit local leakage attacks on the Shamir secret-sharing scheme with adversarially-chosen evaluation places, and (2) local leakage attacks on the Massey secret-sharing scheme corresponding to any linear code. In particular, for Shamir’s secret-sharing scheme, the reconstruction threshold k = ω(log λ) is necessary when the number of parties is n = O(λ log λ). Our analysis of the "parity-of-parity" attack’s distinguishing advantage establishes it as the best-known local leakage attack in these scenarios. Our work employs Fourier-analytic techniques to analyze the "parity-of-parity" attack on the additive secret-sharing scheme. We accurately estimate an exponential sum that captures the vulnerability of this secret-sharing scheme to the parity-of-parity attack, a quantity that is also closely related to the "discrepancy" of the Irwin-Hall probability distribution.
Cite as

Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang, Xiuyu Ye, and Albert Yu. Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme & Its Consequences. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maji_et_al:LIPIcs.ITC.2022.16,
  author =	{Maji, Hemanta K. and Nguyen, Hai H. and Paskin-Cherniavsky, Anat and Suad, Tom and Wang, Mingyuan and Ye, Xiuyu and Yu, Albert},
  title =	{{Tight Estimate of the Local Leakage Resilience of the Additive Secret-Sharing Scheme \& Its Consequences}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.16},
  URN =		{urn:nbn:de:0030-drops-164943},
  doi =		{10.4230/LIPIcs.ITC.2022.16},
  annote =	{Keywords: leakage resilience, additive secret-sharing, Shamir’s secret-sharing, physical-bit probing leakage attacks, Fourier analysis}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.12
On Polynomial Secret Sharing Schemes

Authors: Anat Paskin-Cherniavsky and Radune Artiom

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Nearly all secret sharing schemes studied so far are linear or multi-linear schemes. Although these schemes allow to implement any monotone access structure, the share complexity, SC, may be suboptimal - there are access structures for which the gap between the best known lower bounds and best known multi-linear schemes is exponential. There is growing evidence in the literature, that non-linear schemes can improve share complexity for some access structures, with the work of Beimel and Ishai (CCC '01) being among the first to demonstrate it. This motivates further study of non linear schemes. We initiate a systematic study of polynomial secret sharing schemes (PSSS), where shares are (multi-variate) polynomials of secret and randomness vectors ~s,~r respectively over some finite field 𝔽_q. Our main hope is that the algebraic structure of polynomials would help obtain better lower bounds than those known for the general secret sharing. Some of the initial results we prove in this work are as follows. On share complexity of polynomial schemes. First we study degree (at most) 1 in randomness variables ~r (where the degree of secret variables is unlimited). We have shown that for a large subclass of these schemes, there exist equivalent multi-linear schemes with O(n) share complexity overhead. Namely, PSSS where every polynomial misses monomials of exact degree c≥ 2 in ~s and 0 in ~r, and PSSS where all polynomials miss monomials of exact degree ≥ 1 in ~s and 1 in ~r. This translates the known lower bound of Ω(n^{log(n)}) for multi linear schemes onto a class of schemes strictly larger than multi linear schemes, to contrast with the best Ω(n²/log(n)) bound known for general schemes, with no progress since 94'. An observation in the positive direction we make refers to the share complexity (per bit) of multi linear schemes (polynomial schemes of total degree 1). We observe that the scheme by Liu et. al obtaining share complexity O(2^{0.994n}) can be transformed into a multi-linear scheme with similar share complexity per bit, for sufficiently long secrets. For the next natural degree to consider, 2 in ~r, we have shown that PSSS where all share polynomials are of exact degree 2 in ~r (without exact degree 1 in ~r monomials) where 𝔽_q has odd characteristic, can implement only trivial access structures where the minterms consist of single parties. Obtaining improved lower bounds for degree-2 in ~r PSSS, and even arbitrary degree-1 in ~r PSSS is left as an interesting open question. On the randomness complexity of polynomial schemes. We prove that for every degree-2 polynomial secret sharing scheme, there exists an equivalent degree-2 scheme with identical share complexity with randomness complexity, RC, bounded by 2^{poly(SC)}. For general PSSS, we obtain a similar bound on RC (preserving SC and 𝔽_q but not degree). So far, bounds on randomness complexity were known only for multi linear schemes, demonstrating that RC ≤ SC is always achievable. Our bounds are not nearly as practical as those for multi-linear schemes, and should be viewed as a proof of concept. If a much better bound for some degree bound d=O(1) is obtained, it would lead directly to super-polynomial counting-based lower bounds for degree-d PSSS over constant-sized fields. Another application of low (say, polynomial) randomness complexity is transforming polynomial schemes with polynomial-sized (in n) algebraic formulas C(~s,~r) for each share, into a degree-3 scheme with only polynomial blowup in share complexity, using standard randomizing polynomials constructions.
Cite as

Anat Paskin-Cherniavsky and Radune Artiom. On Polynomial Secret Sharing Schemes. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{paskincherniavsky_et_al:LIPIcs.ITC.2020.12,
  author =	{Paskin-Cherniavsky, Anat and Artiom, Radune},
  title =	{{On Polynomial Secret Sharing Schemes}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.12},
  URN =		{urn:nbn:de:0030-drops-121174},
  doi =		{10.4230/LIPIcs.ITC.2020.12},
  annote =	{Keywords: Secret sharing, polynomial, lower bounds, linear program}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact