Seminar on Quantum Cryptography with Classical Communication


While much of quantum cryptography requires communication of quantum states, recent research has proved major theoretical advantages in cryptography using quantum algorithms and classical communication only.  This is an active and mathematically rich field which incorporates tools from lattice-based cryptography.  The goal of this seminar series is to get a broad view of this area (including ongoing research at QuICS) with the hope of inspiring new ideas and collaboration.  We welcome talks on related research directions, including proofs of quantumness and post-quantum cryptography.


Organizers: Yusuf Alnawakhtha and Carl Miller


Location: ATL 3100A

Zoom link: (requires a UMD account)


Past Meetings

Date: Wednesday, August 31st, 2022, 1:00-2:00pm EDT

Title: Organizational Meeting

Speakers: Yusuf Alnawakhtha and Carl Miller

Abstract: We will discuss format and refine the goals for the seminar.  Attendees are invited to sign up to speak during the Fall 2022 semester.


Date: Wednesday, September 7th, 2022, 1:00-2:00pm EDT

Title: A Brief Introduction to Post-Quantum Cryptography

Speaker: Yusuf Alnawakhtha

Abstract: In this talk I will be giving a brief introduction to some post-quantum cryptography concepts that appear frequently when discussing quantum cryptographic protocols with classical communication. The objective of this talk is to give intuition on how some of the protocols that will be described in this seminar series derive their security. To that end, I will be explaining the Learning with Errors problem (LWE) and how it relates to the conjectured hardness of lattice problems. I will then define Trapdoor Claw-Free functions and discuss their relevance to this research area and how we can construct them from LWE.


Date: Wednesday, September 14th, 2022, 1:00-2:00pm EDT

Title: Introduction to Proofs of Quantumness

Speaker: Manasi Shingane

Abstract: 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. and how it uses the Learning with Errors problem. Finally, I will briefly describe proofs of quantumness protocols based on other cryptographically hard problems.  Reference: Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, T. Vidick, A cryptographic test of quantumness and certifiable randomness from a single quantum device, doi:10.1145/3441309 (2021).


Date: Wednesday, September 28th, 2022, 1:00-2:00pm EDT

Title: Remote State Preparation (Part I)

Speaker: Alexandru Cojocaru 

Abstract: 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.


Date: Wednesday, October 5th, 2022, 1:00-2:00pm EDT

Title: Remote State Preparation (Part II)

Speaker: Atul Mantri

Abstract: 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. 


Date: Wednesday, October 12th, 2022, 1:00-2:00pm EDT

Title: The Yamakawa-Zhandry breakthrough

Speaker: Daochen Wang

Abstract: 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. 

References: “Verifiable Quantum Advantage without Structure” ( and “Quantum Algorithms Conquer a New Kind of Problem” (Quanta magazine).


Date: Wednesday, October 19th, 2022, 1:00-2:00pm EDT

Title: From 1 to K: Improved Certifiable Randomness

Speaker: Rushil Dandamudi

Abstract: 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. For this talk, I will review Mahdadev et al. [2] — an improvement on the former that generates Ω(n) random bits using only O(n) bits of communication. My main goal is to walk through why they first design for a quantum verifier and how they eliminate that dependency. After explaining their intuition, I will dive deeper and prove leakage resilience using a smaller instance of the LWE problem.  


[1] Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, T. Vidick, A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device (2018).

[2] U. Mahadev, U. Vazirani, T. Vidick, Efficient Certifiable Randomness from a Single Quantum Device (2022).


Date: Wednesday, November 2nd, 2022, 1:00-2:00pm EDT

Title: Lattice-Based Quantum Advantage from Rotated Measurements

Speaker: Carl Miller

Abstract: 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. This talk will explain a new technique that uses the entire range of qubit measurements from the XY-plane.  This technique substantially enhances what we are able to do cryptographically with a single claw-state.  I will discuss two applications: proofs of quantumness and remote state preparation. 

Reference: Y. Alnawakhtha, A. Mantri, C. Miller, D. Wang, “Lattice-Based Quantum Advantage from Rotated Measurements,” arXiv:2210.10143 (2022).


Date: Wednesday, November 9th, 2022, 1:00-2:00pm EST

Title: Quantum Money with Minimal Quantum

Speaker: Joseph Carolan

Abstract: 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.

Reference: R. Radian, O. Sattath, “Semi-quantum money,” (2019)


Date: Wednesday, November 16 th, 2022, 1:00-2:00pm EST

Title: Position Verification with Classical Communication

Speaker: Yusuf Alnawakhtha

Abstract: 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.

In this talk, we will go over a recent quantum position verification protocol developed by Jiahui Liu, Qipeng Liu, and Luowen Qian. We will discuss how they use trapdoor claw-fre funcations to replace quantum communication channels in QPV protocols with classical channels. We will also discuss entanglement lower-bounds required to break the protocol and give some insight into possible future directions in QPV.

Reference: Liu, Jiahui, Qipeng Liu, and Luowen Qian. "Beating Classical Impossibility of Position Verification." arXiv:2109.07517 (2021).


Date: Wednesday, November 30th, 2022, 1:00-2:00pm EST

Title: Using nonlocal games to verify quantum advantage

Speaker: Nishant Rodrigues

Abstract: 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. They use quantum homomorphic encryption to simulate the spatial separation that is required in nonlocal games, and then use the gap between the classical and quantum winning probabilities of the nonlocal game to verify quantum advantage.


[1] Kalai, Yael, et al. "Quantum Advantage from Any Non-Local Game." arXiv preprint arXiv:2203.15877 (2022).


Date: Wednesday, December 7th, 2022, 1:00-2:00pm EST

Title: Post-quantum security of symmetric-key constructions

Speaker: Chen Bai

Abstract: 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: Reference: G. Alagic, C. Bai, J. Katz, C. Majenz, Post-Quantum Security of the Even-Mansour Cipher


Additional Resources

-       Urmila Mahadev.  Classical Homomorphic Encryption for Quantum Circuits. SIAM Journal on Computing, Special Section FOCS 2018.  doi:10.1137/18M1231055


-       Chris Peikert (2016), "A Decade of Lattice Cryptography", Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 4, pp 283-424. doi:10.1561/0400000074