Contributed Talks 2b

Abstract: Weak coin flipping is a cryptographic primitive in which two mutually distrustful parties generate a shared random bit to agree on a winner via remote communication. While a stand-alone secure weak coin flipping protocol can be constructed from noiseless communication channels, its composability has not been explored. In this work, we demonstrate that no weak coin flipping protocol can be abstracted into a black box resource with composable security. Despite this, we also establish the overall stand-alone security of weak coin flipping protocols under sequential composition.

Abstract: We show the following unconditional results on quantum commitments in two related yet different models: 1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter, as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist unconditionally, i.e., without relying on any unproven assumption, while Chailloux et al. assumed a complexity-theoretic assumption, $QIP not subseteq QMA$. On the other hand, we observe that achieving both statistical hiding and statistical binding at the same time is impossible even in the quantum auxiliary-input setting. To the best of our knowledge, this is the first example of unconditionally proving computational security of any form of (classical or quantum) commitments for which statistical security is impossible. As intermediate steps toward our construction, we introduce and unconditionally construct post-quantum sparse pseudorandom distributions and quantum auxiliary-input EFI pairs which may be of independent interest. 2. We introduce a new model which we call the common reference quantum state (CRQS) model where both the committer and receiver take the same quantum state that is randomly sampled by an efficient setup algorithm. We unconditionally prove that there exist statistically hiding and statistically binding commitments in the CRQS model, circumventing the impossibility in the plain model. We also discuss their applications to zero-knowledge proofs, oblivious transfers, and multi-party computations.

Abstract: One-way state generators (OWSG) [MY22a] are natural quantum analogs to classical one-way functions. We show that O(n/log(n))-copy OWSGs (n represents the input length) are equivalent to poly(n)-copy OWSGs and to quantum commitments. Since known results show that o(n/log(n))-copy OWSGs cannot imply commitments [CGG`23], this shows that O(n/log(n))-copy OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of Håstad, Impagliazzo, Levin and Luby [HILL99], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL99]. Since we do not argue conditioned on the output of the one-way function, our construction and analysis are arguably simpler and may be of independent interest.

Abstract: Quantum cryptography allows to achieve security goals that are unobtainable using classical cryptography alone, it offers the promise of everlasting privacy. That is, an adversary trying to attack a protocol must succeed during the run of the protocol, after the protocol has terminated security holds unconditionally. In this work we initiate the study of a new model which we call the quantum decoherence model (QDM). In a nutshell, this model requires that the adversary is computationally bounded during the run of a protocol (and some time after), but becomes computationally unbounded long after the protocol terminates. Importantly, once the adversary becomes computationally unbounded, he can only remember a bounded number of qubits from before the bound was lifted. As our main contribution, we construct a non-interactive commitment scheme achieving unconditional security against malicious senders and everlasting security against malicious receivers in the UC model. Additionally, we show that it gives rise to everlasting public key encryption and OT in the QDM. Finally, we also consider the weaker notion of incompressible encryption in the setting of quantum decoherence, and show that post-quantum IND-CPA secure public key encryption is sufficient to realize this notion without resorting to random oracles.