DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2023.4

Computational Quantum Secret Sharing

Authors: Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract

Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.

Cite as

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro. Computational Quantum Secret Sharing. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 4:1-4:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cakan_et_al:LIPIcs.TQC.2023.4,
  author =	{\c{C}akan, Alper and Goyal, Vipul and Liu-Zhang, Chen-Da and Ribeiro, Jo\~{a}o},
  title =	{{Computational Quantum Secret Sharing}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{4:1--4:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.4},
  URN =		{urn:nbn:de:0030-drops-183144},
  doi =		{10.4230/LIPIcs.TQC.2023.4},
  annote =	{Keywords: Quantum secret sharing, quantum cryptography}
}

Document

DOI: 10.4230/LIPIcs.ITC.2021.12

Linear Threshold Secret-Sharing with Binary Reconstruction

Authors: Marshall Ball, Alper Çakan, and Tal Malkin

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract

Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold (`t-out-of-n') secret-sharing where the linear reconstruction function is restricted to coefficients in {0,1}. We also study the complexity of such schemes with the additional requirement that the joint distribution of the shares of any unauthorized set of parties is not only independent of the secret, but also uniformly distributed. We prove upper and lower bounds on the share size of such schemes, where the size is measured by the total number of field elements distributed to the parties. We prove our results by defining and investigating an equivalent variant of Karchmer and Wigderson’s Monotone Span Programs [CCC, 1993]. One ramification of our results is that a natural variant of Shamir’s classic scheme [Comm. of ACM, 1979], where bit-decomposition is applied to each share, is optimal for when the underlying field has characteristic 2. Another ramification is that schemes obtained from monotone formulae are optimal for certain threshold values when the field’s characteristic is any constant. For schemes with the uniform distribution requirement, we show that they must use Ω(nlog n) field elements, for all thresholds 2 < t < n and regardless of the field. Moreover, this is tight up to constant factors for the special cases where any t = n-1 parties can reconstruct, as well as for any threshold when the field characteristic is 2.

Cite as

Marshall Ball, Alper Çakan, and Tal Malkin. Linear Threshold Secret-Sharing with Binary Reconstruction. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITC.2021.12,
  author =	{Ball, Marshall and \c{C}akan, Alper and Malkin, Tal},
  title =	{{Linear Threshold Secret-Sharing with Binary Reconstruction}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.12},
  URN =		{urn:nbn:de:0030-drops-143313},
  doi =		{10.4230/LIPIcs.ITC.2021.12},
  annote =	{Keywords: Secret sharing, Span programs, Lattice-based cryptography}
}

Search Results

Documents authored by Çakan, Alper

Computational Quantum Secret Sharing

Abstract

Cite as

Linear Threshold Secret-Sharing with Binary Reconstruction

Abstract

Cite as

Thanks for your feedback!

Could not send message