Publications
- Quantum State Learning Implies Circuit Lower Bounds
- Authors: Nai-Hui Chia, Daniel Liang, and Fang Song
- Contributed talk at the 19th Theory of Quantum Computation, Communication and Cryptography (TQC 2024).
- [arXiv] [Talk at TQC’24 by Daniel Liang YouTube]
- Improved Quantum Lifting by Coherent Measure-and-Reprogram
- Authors: Alexandru Cojocaru, Juan Garay, Qipeng Liu, and Fang Song
- In the 30th International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2024).
- [IACR ePrint]
- Generalized Hybrid Search and Applications
- Authors: Alexandru Cojocaru, Juan Garay, and Fang Song
- In the 30th International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2024).
- [IACR ePrint]
- Quantum Pseudorandom Scramblers
- Authors: Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao
- In the 22nd Theory of Cryptography Conference (TCC 2024).
- Contributed talk at the 27th Conference on Quantum Information Processing (QIP 2024).
- [arXiv:2309.08941] [IACR ePrint]
- A Cryptographic Perspective on the Verifiability of Quantum Advantage
- Authors: Nai-Hui Chia, Honghao Fu, Fang Song, and Penghui Yao
- Contributed talk at the 24th Asian Quantum Information Science Conference (AQIS 2024).
- [arXiv:2310:14464]
- Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin’s Post-Quantum Security
- Authors: Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, and Petros Wallden
- In Quantum, volume 7, 944, 2023.
- Quantum algorithms for attacking hardness assumptions in classical and post-quantum cryptography
- Authors: J-F Biasse, X. Bonnetain, E. Kirshanova, A. Schrottenloher, and F. Song
- In IET Information Security, 1-39, 2022, 2022.
- Quantum Key-length Extension
- Authors: Joseph Jaeger, Fang Song, and Stefano Tessaro
- In the 19th Theory of Cryptography Conference (TCC 2021).
- [Springer] [arXiv] [IACR ePrint]
- Oblivious Transfer is in MiniQCrypt
- Authors: Alex B. Grilo, Huijia Lin, Fang Song, Vinod Vaikuntanathan
- In the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021).
- Long plenary talk at the 24th Annual Conference on Quantum Information Processing (QIP 2021).
- [arXiv] [IACR ePrint]
- Basing cryptography on NP-hardness using quantum reductions
- Authors: Nai-Hui Chia, Sean Hallgren, and Fang Song
- In Quantum, the open journal for quantum science, 4, 312 (2020).
- Contributed talk at the 8th International Conference on Quantum Cryptography (QCrypt 2018).
- [Quantum] [arXiv]
- Quantum-secure message authentication via blind-unforgeability
- Authors: Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song
- In the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2020).
- [arXiv]
- A note on the instantiability of the quantum random oracle
- Authors: Edward Eaton and Fang Song
- In the Eleventh International Conference on Post-Quantum Cryptography (PQCrypto 2020).
- [ePrint]
- General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
- Authors: Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun
- In the 17th Theory of Cryptography Conference (TCC 2019).
- Contributed talk at the 23rd Annual Conference on Quantum Information Processing (QIP 2020).
- [arXiv] [ePrint]
- Quantum security of hash functions and property-preservation of iterated hashing
- Authors: Ben Hamlin and Fang Song
- In the 10th International Conference on Post-Quantum Cryptography (PQCrypto 2019).
- [arXiv]
- Pseudorandom Quantum States
- Authors: Zhengfeng Ji, Yi-Kai Liu, Fang Song
- In the 38th International Cryptology Conference (Crypto 2018).
- [ePrint arXiv] [Slides: PDF Video]
- Quantum Collision-Finding in Non-Uniform Random Functions
- Authors: Marko Balogh, Edward Eaton, and Fang Song
- In the 9th International Conference on Post-Quantum Cryptography (PQCrypto 2018).
- [Springer] [IACR ePrint]
- Quantum Security of NMAC and Related Constructions
- Authors: Fang Song and Aaram Yun
- In the 37th International Cryptology Conference (Crypto 2017).
- [Springer] [ePrint]
- Zero-knowledge proof systems for QMA
- Authors: Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous
- In 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
- Contributed talk at 20th Annual Conference on Quantum Information Processing (QIP 2017).
- [arXiv] [Slides: @FOCS PDF, @QIP’17 PDF Video (slightly tuned to quantum audience) ]
- [Journal version: SICOMP] SIAM J. Comput., 49(2), 245–283, 2020.
- Mitigating multi-target attacks in hash-based signatures
- Authors: Andreas Hülsing, Joost Rijneveld, and Fang Song
- In 19th International Conference on the Theory and Practice of Public-Key Cryptography (PKC 2016).
- [Proceedings version: Official] [Preliminary full version: ePrint]
- Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
- Making Existential-Unforgeable Signatures Strongly Unforgeable in the Quantum Random-Oracle Model
- A Note on Quantum Security for Post-Quantum Cryptography
- Author: Fang Song
- In 6th International Conference on Post-Quantum Cryptography (PQCrypto 2014). [Proceedings Version: Official] [Slides: Powerpoint, PDF] [Video]
- [arXiv] [ePrint]
- A Quantum Algorithm for Computing the Unit Group of an Arbitrary Degree Number Field
- Authors: Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev and Fang Song
- In STOC 2014. [Proceedings Version: Official, PDF]
- Plenary talk at QIP 2015. [Video] [Slides: PDF]
- Full version: [PDF] [arXiv]
- Feasibility and Completeness of Cryptographic Tasks in the Quantum World
- Authors: Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou and Vassilis Zikas
- In 10th Theory of Cryptography Conference (TCC 2013).
- Workshop Track at ICITS 2012, Poster (PDF) at STOC 2012
- [Proceedings version: Official, ePrint] [Preliminary full version: PDF]
- Classical Cryptographic Protocols in a Quantum World
- Authors: Sean Hallgren, Adam Smith and Fang Song
- Featured talk at QIP 2011
- In 31st International Cryptology Conference (CRYPTO 2011).
- Invited to International Journal of Quantum Information, Vol. 13, No. 4 (2015). [doi]
- [Springer] [Slides: Powerpoint, PDF] [Video] [Full version: arXiv ePrint]
Manuscripts
- Early days following Grover’s quantum search algorithm
- Authors: Fang Song
- A lecture note in Spring’17 summarizing basic results related to Grover’s algorithm.
- [arXiv]
- On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \(\mathbb{Q}(\zeta_{p^n})\)
- Authors: Jean-François Biasse and Fang Song
- CACR Tech Report, CACR2015-12, September 2015.
- Poster at QIP’16.
- Mentioned in “A Tricky Path to Quantum-Safe Encryption’’, Quanta Magazine, September 9, 2015.
Grant awards
- 10/2022 - 09/2024 NSF Award #2224131. Collaborative Research: FET: Small.
- 03/2022 - 02/2023 Sony Faculty Innovation Award.
- 04/2020 - 03/2025 NSF CAREER Award #2054758. FET: CAREER.
- 10/2018 - 09/2022 NSF Award #2041841 (#1816869). AF: Small.
- 08/2018 - 07/2022 NSF Award #2042414 (#1764042). AF: Medium: Collaborative Research.
- 10/2021 - 07/2022 REU supplement.
Selected Talks
Information about conference talks are typically under the publication list. Some recorded talks are collected in this YouTube playlist.
-
Tutorial on Quantum Computing at IPAM Graduate Summer School on Post-quantum and Quantum Cryptography, July 25 - 29, 2022. [Hand-written notes PDF] [Videos: Part 1 Part 2 Part 3]
- Quantum-secure key-length extension, invited Zoom talk at the EWHA-KMS International Workshop on Cryptography, June 2021.
- Unpredictable Functions and Quantum-secure Authentication, invited Zoom talk at the International Joint Conference on Theoretical Computer Science (IJTCS), August 2020.
- Cybersecurity in a quantum world, invited Zoom talk at the Portland quantum computing meetup group, August 2020.
- Invited tutorial at the 9th International Conference on Quantum Cryptography, Montreal, Canada, August 28, 2019. Zero-knowledge proofs meet quantum computing. [Slides PDF]
- Invited talk at the 2nd IAMCS Quantum Computation and Information Workshop, TAMU, May 13-15, 2019. Cryptography from NP Hardness: can quantum help?. [Slides PDF]
- Invited talk at the AMS Spring Central and Western Joint Sectional Meeting, University of Hawaii at Manoa, Honolulu, HI, March 22-24, 2019. Pseudorandom quantum states.
- Invited talk at IAMCS Quantum Computation and Information Workshop. TAMU, TX, September 22 2018. Pseudorandom quantum states.
- Invited speaker at Asia Forum
on Post-quantum cryptography. Seoul, Korea, Nov 28 - 29, 2016.
What are we talking about when we talk about post-quantum cryptography?
Available: [Slides PDF] [Video]. - QuICS Seminar, University of Maryland, October 12 2016.
Zero-knowledge proof systems for QMA.