Quantum computing and symmetric-key cryptography

About

• Instructor: Siwei Sun

• Lectures: 13:30 ~ 15:10, Saturday; 16:25 ~ 18:05, Sunday. (5-8周，中国科学院大学雁栖湖校区，教1-127)

• Wechat Group: (加入请修改群名片为 真实姓名-单位，谢谢！)

  

Course Description

I will introduce the basics of quantum computing via linear algebra from scratch and therefore no knowledge of quantum physics is required. I will describe how quantum transformations can be implemented with single-qubit and two-qubit quantum gates. Then, I will clarify important metrics in synthesis and optimization of quantum circuits and show interesting research topics of quantum circuits in the context of symmetric-key cryptography. Along the way, an overview of some recent results concerning quantum circuits and symmetric-key cryptography will be provided. Then I will introduce some simple quantum algorithms and show how they are applied in symmetric-key cryptanalysis.

Main Topics

• One-qubit and two-qubit systems

• N-qubit system and its measurement

• Quantum transformations

• Synthesis and optimization of quantum circuits

• Simple quantum algorithms

• Simon's algorithm and symmetric-key cryptanalysis

• Grover's algorithm and symmetric-key cryptanalysis

• The BHT algorithm for finding collisions of a hash function

• Quantum

Readings

1. Textbook: Michael A.Nielsen, Isaac L. Chuang. Quantum computation and quantum information.
2. Phd Thesis: Xavier Bonnetain. Hidden Structures and Quantum Cryptanalysis.
3. https://project.inria.fr/quasymodo/results/
4. Xavier Bonnetain: Tight Bounds for Simon's Algorithm. IACR Cryptol. ePrint Arch. 2020: 919 (2020)
5. Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia: Implementing Grover Oracles for Quantum Key Search on AES and LowMC. EUROCRYPT (2) 2020: 280-310
6. Jian Zou, Zihao Wei, Siwei Sun, Ximeng Liu, Wenling Wu: Quantum Circuit Implementations of AES with Fewer Qubits. ASIACRYPT 2020.
7. Akinori Hosoyamada, Yu Sasaki: Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound. EUROCRYPT (2) 2020: 249-279
8. Xiaoyang Dong, Siwei Sun, Danping Shi, Fei Gao, Xiaoyun Wang, Lei Hu: Quantum Collision Attacks on AES-like Hashing with Low Quantum Random Access Memories. ASIACRYPT 2020.
9. Gregor Leander, Alexander May: Grover Meets Simon - Quantumly Attacking the FX-construction. ASIACRYPT (2) 2017: 161-178

Invited Talks ( To be announced ... )

This will be online due to the current regulations of Chinese Academy of Sciences.