CWI Cryptology Group

Abstract: In this talk, I give an overview over the results presented in my PhD thesis. We examine two-prover bit-commitments, as introduced by Ben-Or, Goldwasser, Kilian and Wigderson in 1988, where security relies on assumed communication restrictions between the provers. We introduce new definitions of the binding property of such commitment schemes and prove a composition theorem which shows that two commitment schemes can be composed into a "larger" scheme with the binding parameters adding up. This composition theorem can be applied to relativistic commitment schemes. In particular, we show that the relativistic commitment scheme introduced by Lunghi et al. in 2015 has a much better binding parameter than the original analysis indicated. The composition theorem only applies for classical provers. Time permitting, I will discuss some partial progress towards extending the result to provers with quantum capabilities. If one wants to prove a commitment scheme secure on the sole assumption that provers cannot communicate, one must consider so-called non-signalling provers: provers whose behavior is correlated in arbitrary ways, as long as no communication is implied. We show an impossibility result here: no commitment scheme is both hiding and binding for such provers. On the other hand, there is a three-prover scheme that is hiding and binding.

Abstract: Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives.
We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. This is joint work with Gorjan Alagic, Maris Ozols and Alexander Poremba.

Abstract: Quantum theory predicts correlations that question fundamental space-time causality. Dropping the latter, while still maintaining logical consistency, has dramatic consequences for the power of communication and computation. Such reasoning is in the spirit of Landauer's famous slogan "Information is Physical." A variant of its paradigmatic rival, Wheeler's "It from Bit," is the Church-Turing hypothesis: All physical processes can be simulated on a universal Turing machine. We use the tension between the two viewpoints to look for a purely intrinsic randomness notion and find one around the second law of thermodynamics. Quantum correlations, combined with Kolmogorov complexity as randomness, reveal an all-or-nothing nature of the Church-Turing hypothesis: Either non-Turing computations are physically impossible, or they can be carried out by "devices" as simple as individual photons.