Quantum Cryptography Reading Group

Overview

We are organizing a reading group this semester to study (in a broad sense) the impact of quantum technology on the field of cryptography. Topics of interest include both quantum protocols and classical "postquantum" cryptographic protocols. Part of the goal is to continue to develop a bridge between the classical crypto and quantum information communities. Since this is an interdisciplinary group, we encourage speakers to provide ample preliminary information and overview material during each talk.

There is a list of resources provided below to give some ideas on topics of interest in quantum cryptography. An online course in quantum cryptography is also listed for those who wish to have some additional background.

You can access the spring 2019 website for the quantum cryptography reading group here.

Meetings Time: No more meetings this semester

Meetings Location: No more meetings this semester

Schedule

Date Speaker Topic Reading
February 12th Yusuf Alnawakhtha Offline Simon's Algorithm "Quantum Attacks without
Superposition Queries: The
Offline Simon's Algorithm"
February 26th Carl Miller
The Fiat-Shamir Transformation in
the Quantum Random Oracle Model
"Security of the Fiat-Shamir
Transformation in the Quantum
Random Oracle Model"
Shih-Han Hung Two Message Verification of
Quantum Computation
"Two Message Verification of
Quantum Computation"
April 1st Nishant Rodrigues Device Independent QKD "Fully Device Independent Quantum Key
Distribution"
April 9th Atul Mantri Abstract Cryptography and Delegated Quantum Computation "Abstract Cryptography"

"Composable Security of Delegated
Quantum Computation"

"Computationally-Secure and Composable
Remote State Preparation"
April 15th Hong Hao Fu Zero Knowledge Protocols "Zero-Knowledge Against Quantum
Attacks"


Previous Meetings

Title: The Offline Simon's Algorithm
Presenter: Yusuf Alnawakhtha
Date: Wednesday, February 12th (4p.m.)
Summary: Threat models that allow the attacker to perform offline quantum computation and make superposition queries to an oracle are often enticing to consider since they offer a considerable speedup over classical attacks. However, due to current communication infrastructure, these models are not as relevant as threat models that only allow the attacker to perform classical queries. We will be going over this paper by Bonnetain et al., which presents the first use of Simon's algorithm in the model without superposition queries. The paper also goes over attack examples on the Even-Mansour and FX constructions as examples of consequences of their result.

Title: The Fiat-Shamir Transformation in the Quantum Random Oracle Model
Presenter: Carl Miller
Date: Wednesday, February 26th (4p.m.)
Location: Iribe 5105
Summary: The Fiat-Shamir transformation is a method for turning an interactive protocol in a non-interactive protocol. It has been used as a building block in digital signature schemes. While the security of this transformation can be proved in the random oracle model (ROM) without much difficulty, the ROM is not an appropriate model if one of the parties in the protocol can perform quantum computation. I will discuss recent work of J. Don et al. which proves that the Fiat-Shamir transformation remains secure in the quantum random oracle model (QROM).

Title: Two Message Verification of Quantum Computation
Presenter: Shih-Han Hung
Date: Wednesday, February 26th (4:30p.m.)
Location: Iribe 5105
Summary: We describe a two-message protocol that enables a purely classical verifier to delegate any quantum computation to an untrusted quantum prover. The protocol begins with the verifier publishing a problem instance together with a public cryptographic key. The prover then transmits the computation result, appropriately encoded. Finally, the verifier uses their private key to detect any cheating and extract the result.

We achieve this by upgrading the verification protocol of Mahadev in two steps. First, the protocol is repeated many times in parallel, yielding a four-message protocol with negligible soundness error. This enables the second step: the "challenge round" is eliminated via the Fiat-Shamir transform, in which the prover computes their own challenges using a public hash function.

We show that this protocol is secure under the same assumptions underlying many candidate schemes for post-quantum public-key cryptography. Specifically, it is secure in the Quantum Random Oracle Model, and assuming the quantum hardness of the Learning with Errors problem. The main technical advance in our security proof is a parallel repetition theorem for the Mahadev protocol.

Title: Abstract Cryptography and Delegated Quantum Computation
Presenter: Nishant Rodrigues
Date: April 1st (4p.m.)
Location: Virtual - https://umd.zoom.us/j/621718109
Summary: I will primarily discuss the paper "Fully Device Independent Quantum Key Distribution" by Vazirani and Vidick. The idea is to prove the security of quantum key distribution based only on the validity of quantum mechanics. Previous work on DIQKD assumed no presence of noise, or independent uses of the devices involved. In this paper, Vazirani and Vidick prove security of DIQKD even in the presence of a constant amount of noise. The only assumptions made in the paper are spatial isolation of the devices the two parties (Alice and Bob) use, and that Alice, Bob and Eve (adversary) are all bound by the laws of quantum mechanics.

Title: Abstract Cryptography and Delegated Quantum Computation
Presenter: Atul Mantri (4p.m.)
Date: April 9th (Thursday)
Location: Virtual - https://umd.zoom.us/j/621718109
Summary: The session will be divided into two parts. In the first part, I will introduce a framework for the composable security - Abstract Cryptography - proposed by Maurer and Renner. The main idea behind the composable security is to extend the stand-alone security definitions as they fail to capture the scenario when a (cryptographic) protocol is used as a subroutine of a larger protocol. Abstract cryptography can be used to define the security of cryptographic schemes such as symmetric encryption, message authentication codes, public-key encryption, digital signature schemes, etc and for proving the security of protocols making use of such schemes.

In the second part, I will provide a proof sketch of the composable security of quantum cryptographic protocols such as delegated quantum computation and secure remote state preparation using the framework of abstract cryptography.

Title: Basics of Quantum Zero Knowledge Proofs
Presenter: Hong Hao Fu (4p.m.)
Date: April 15th
Location: Virtual - https://umd.zoom.us/j/621718109
Reading: "Zero-Knowledge Against Quantum Attacks"
Summary: An interactive proof system is zero-knowledge if verifiers that interact with the honest prover of the system learn nothing from the interaction beyond the validity of the statement being proved. Classically, every language in NP has a zero-knowledge proof system under certain conditions. In the quantum setting, even finding the general definition is non-trivial. In this talk, we will formally define quantum zero-knowledge proof systems. Then we will discuss some examples of classical zero-knowledge protocols that remain zero-knowledge against quantum attacks.

Resources


Organizers: Carl Miller and Yusuf Alnawakhtha.