QCCC Seminar

In this talk I will give a brief introduction about the security of various symmetric-key constructions against quantum attackers in two models: Q1 model and Q2 model. I’ll talk about the difference between those two models, why Q1 model is more realistic and some recent results about the post-quantum security of block ciphers in the Q1 model.

Reference: G. Alagic, C. Bai, J. Katz, C. Majenz, Post-Quantum Security of the Even-Mansour Cipher https://eprint.iacr.org/2021/1601.
 

In this talk, I will give a brief introduction to nonlocal games, followed by a discussion on the results from [1]. In this paper Kalai et al. show a connection between nonlocal games and classical verification of quantum advantage. Specifically, they construct a framework for compiling a k-prover nonlocal game into a single-prover interactive game.

Position verification is the task of verifying the geographical position of a party using computational tasks and physical bounds on the speed of communication. It has been shown that position verification is impossible in the classical setting, but using non-clonability it is shown that one can construct quantum position verification (QPV) schemes. These schemes are secure against any individual attacker, but can be broken by colluding attackers that share a large amount of entanglement.

Trapdoor claw-free functions are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-X or Z measurements.

Quantum money leverages the fundamental uncloneability of quantum information to create a money system in which copying money is computationally infeasible, yet verifying it is efficient. However, in addition to fault tolerant quantum computers, many quantum money schemes also require quantum communication. I will discuss the possibility of schemes with classical communication in place of quantum. In particular, I will focus on the private key semi-quantum money of Radian et al, placing it in context with other types of dequantization we could hope for.

In a previous talk we saw that Brakerski et al. [1] used the hardness of the Learning with Errors (LWE) problem to not only construct an interactive Proof of Quantumness but also certifiably generate a random bit.

Recently, Yamakawa and Zhandry constructed a problem and proved that it admits a super-polynomial quantum speedup in the average case. Before their work, we only knew of problems that admit a super-polynomial quantum speedup in the worst case. In this talk, I will describe their problem and go over some key steps in their proof. I will also briefly discuss how their result can be construed as a non-interactive proof of quantumness relative to a random oracle.

Remote state preparation (RSP) has become an essential subroutine to ''dequantize'' the quantum channel in various quantum cryptographic schemes. Some of the applications of RSP include proofs of quantumness, delegated quantum computations, quantum money, unclonable quantum encryption, quantum copy protection and more. In this talk, we will talk about security aspects and some of these applications. 

In this talk I will introduce the remote state preparation primitive, which can enable a fully classical party to participate in different quantum protocols.  Next, I will present two simple protocols based on trapdoor one-way functions with extra properties and show how to construct them based on the Learning-With-Errors problem.

In this talk I will give an introduction to proofs of quantumness. Such protocols can be executed using local quantum computations and only classical communication. I will begin by defining and motivating proofs of quantumness. I will then describe the specific construction by Brakerski et al. [1] and how it uses the Learning with Errors problem. Finally, I will briefly describe proofs of quantumness protocols based on other cryptographically hard problems.