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) https://umd.zoom.us/j/96508005344
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” (arxiv.org) 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.
References:
[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-
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,” https://arxiv.org/abs/1908.
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.
References:
[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 https://eprint.iacr.org/2021/1601.
- 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