6 Search Results for "Çakan, Alper"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.41
The Curious Case of "XOR Repetition" of Monogamy-Of-Entanglement Games

Authors: Andrea Coladangelo, Qipeng Liu, and Ziyi Xie

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In this work, we consider "decision" variants of a well-known monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner [New Journal of Physics '13]. In its original "search" variant, Alice prepares a (possibly entangled) state on registers ABC; register 𝖠, consisting of n qubits, is sent to a Referee, while 𝖡 and 𝖢 are sent to Bob and Charlie; the Referee then measures each qubit in the standard or Hadamard basis (chosen uniformly at random). The basis choices are sent to Bob and Charlie, whose goal is to simultaneously guess the Referee’s n-bit measurement outcome string x. Tomamichel et al. show that the optimal winning probability is cos^{2n}(π/8), following a perfect parallel repetition theorem. We consider the following "decision" variants of this game: - Variant 1, "XOR repetition": Bob and Charlie’s goal is to guess the XOR of all the bits of x. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in n. Surprisingly, we show that this conjecture is false, and, in fact, there is no decay at all: there exists a strategy that wins with probability cos²(π/8) ≈ 0.85 for any n. Moreover, this strategy does not involve any entanglement between Alice, Bob, and Charlie! - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random n-bit string r that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of r⋅ x. We show that the optimal advantage over random guessing decays exponentially in n for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and Çakan et al.; we give a more direct proof. Showing that Variant 2 is "secure" (i.e., that the optimal winning probability is exponentially close to 1/2) against general adversaries would imply the existence of an information-theoretically "unclonable bit". We put forward a reasonably concrete conjecture that is equivalent to the general security of Variant 2.
Cite as

Andrea Coladangelo, Qipeng Liu, and Ziyi Xie. The Curious Case of "XOR Repetition" of Monogamy-Of-Entanglement Games. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{coladangelo_et_al:LIPIcs.ITCS.2026.41,
  author =	{Coladangelo, Andrea and Liu, Qipeng and Xie, Ziyi},
  title =	{{The Curious Case of "XOR Repetition" of Monogamy-Of-Entanglement Games}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.41},
  URN =		{urn:nbn:de:0030-drops-253281},
  doi =		{10.4230/LIPIcs.ITCS.2026.41},
  annote =	{Keywords: quantum information, monogamy of entanglement, unclonable encryption}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.109
Cloning Games, Black Holes and Cryptography

Authors: Alexander Poremba, Seyoon Ragavan, and Vinod Vaikuntanathan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In this work, we introduce a new toolkit for analyzing cloning games, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. This framework allows us to analyze a new cloning game based on binary phase states. Our results provide evidence that these games may be able to overcome important limitations of previous candidates based on BB84 states and subspace coset states: in a model where the adversaries are restricted to making a single oracle query, we show that the binary phase variant is t-copy secure when t = o(n/log n). Moreover, for constant t, we obtain the first optimal bounds of O(2^{-n}), asymptotically matching the value attained by a trivial adversarial strategy. We also show a worst-case to average-case reduction which allows us to show the same quantitative results for the new and natural notion of Haar cloning games. Our analytic toolkit, which we believe will find further applications, is based on binary subtypes and uses novel bounds on the operator norms of block-wise tensor products of matrices. To illustrate the effectiveness of these new techniques, we present two applications: first, in black-hole physics, where our asymptotically optimal bound offers quantitative insights into information scrambling in idealized models of black holes; and second, in unclonable cryptography, where we (a) construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries, and (b) propose and provide evidence for the security of multi-copy unclonable encryption schemes.
Cite as

Alexander Poremba, Seyoon Ragavan, and Vinod Vaikuntanathan. Cloning Games, Black Holes and Cryptography. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 109:1-109:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{poremba_et_al:LIPIcs.ITCS.2026.109,
  author =	{Poremba, Alexander and Ragavan, Seyoon and Vaikuntanathan, Vinod},
  title =	{{Cloning Games, Black Holes and Cryptography}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{109:1--109:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.109},
  URN =		{urn:nbn:de:0030-drops-253961},
  doi =		{10.4230/LIPIcs.ITCS.2026.109},
  annote =	{Keywords: Unclonable cryptography, quantum pseudorandomness, black hole physics}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.9
Revocable Encryption, Programs, and More: The Case of Multi-Copy Security

Authors: Prabhanjan Ananth, Saachi Mutreja, and Alexander Poremba

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

Abstract
Fundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led to the emerging field of revocable cryptography. Roughly speaking, in a revocable cryptographic primitive, a cryptographic object (such as a ciphertext or program) is represented as a quantum state in such a way that surrendering it effectively translates into losing the capability to use this cryptographic object. All of the revocable cryptographic systems studied so far have a major drawback: the recipient only receives one copy of the quantum state. Worse yet, the schemes become completely insecure if the recipient receives many identical copies of the same quantum state - a property that is clearly much more desirable in practice. While multi-copy security has been extensively studied for a number of other quantum cryptographic primitives, it has so far received only little treatment in context of unclonable primitives. Our work, for the first time, shows the feasibility of revocable primitives, such as revocable encryption and revocable programs, which satisfy multi-copy security in oracle models. This suggest that the stronger notion of multi-copy security is within reach in unclonable cryptography more generally, and therefore could lead to a new research direction in the field.
Cite as

Prabhanjan Ananth, Saachi Mutreja, and Alexander Poremba. Revocable Encryption, Programs, and More: The Case of Multi-Copy Security. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITC.2025.9,
  author =	{Ananth, Prabhanjan and Mutreja, Saachi and Poremba, Alexander},
  title =	{{Revocable Encryption, Programs, and More: The Case of Multi-Copy Security}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-243592},
  doi =		{10.4230/LIPIcs.ITC.2025.9},
  annote =	{Keywords: quantum cryptography, unclonable primitives}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.7
Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography

Authors: Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study a novel question about nonlocal quantum state discrimination: how well can non-communicating - but entangled - players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is to show that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We show that this question has implications to unclonable cryptography, which leverages the no-cloning principle to build cryptographic primitives that are classically impossible to achieve. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We leverage our main result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing. These applications present evidence that simultaneous Haar indistinguishability could be useful in quantum cryptography.
Cite as

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITCS.2025.7,
  author =	{Ananth, Prabhanjan and Kaleoglu, Fatih and Yuen, Henry},
  title =	{{Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.7},
  URN =		{urn:nbn:de:0030-drops-226352},
  doi =		{10.4230/LIPIcs.ITCS.2025.7},
  annote =	{Keywords: Quantum, Haar, unclonable encryption}
}
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}
}
  • Refine by Type
  • 6 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 2 2025
  • 1 2023
  • 1 2021

  • Refine by Author
  • 2 Ananth, Prabhanjan
  • 2 Poremba, Alexander
  • 2 Çakan, Alper
  • 1 Ball, Marshall
  • 1 Coladangelo, Andrea
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Cryptographic primitives
  • 2 Theory of computation → Cryptographic protocols
  • 2 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 2 quantum cryptography
  • 2 unclonable encryption
  • 1 Haar
  • 1 Lattice-based cryptography
  • 1 Quantum
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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