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 31^{st}, 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 14^{th}, 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 28^{th}, 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 5^{th}, 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 12^{th},
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 19^{th}, 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 2^{nd}, 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 9^{th}, 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 30^{th}, 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 7^{th}, 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