Fang Song is an Associate Professor in the Computer Science Department at Portland State University. His research lies at the intersection of cryptography, quantum computing, and computational complexity, including provable security against quantum attacks, quantum algorithms, and quantum pseudorandomness. His work has been supported by the National Science Foundation (including a CAREER Award) and the Sony Group. He received the Early Career Research Award at Portland State University.
Before joining Portland State, Fang Song was a postdoctoral fellow at the Institute for Quantum Computing at the University of Waterloo (2013–2016). He received his PhD in Computer Science and Engineering from Penn State in 2013, advised by Sean Hallgren, and his bachelor's degree from USTC in 2008.
-
Parallel Kac's Walk Generates PRU PreprintProved that the parallel Kac's walk construction generates pseudorandom unitaries, giving a conceptually distinct route to PRUs.
-
Introduced pseudorandom quantum states and gave the first construction. Inspired the pursuit of a new landscape of quantum cryptography and new approahes to quantum gravity.
-
Introduced blind-unforgeability and developed new tools to reason about unpredictability against quantum-superposition attacks.
-
Established feasibility of quantum-secure two-party computation for the first time.
-
Efficient Quantum Algorithms for Computing Class Groups and Solving the Principal Ideal Problem in Arbitrary Degree Number Fields SODA 2016Gave efficient quantum algorithms for computing class groups and solving the principal ideal problem, with implications for cryptanalysis of ideal-lattice cryptosystems.
-
Gave the first efficient quantum algorithm for unit groups of arbitrary degree number fields, achieving exponential speedup over best known classical algorithms.
-
Constructed oblivious transfer from one-way functions in a quantum world, bypassing a classical impossibility barrier.
-
Constructed the first zero-knowledge proof system for QMA, the quantum analogue of NP.
- 04/2024 PSU Early Career Research Award
- 03/2022 Sony Faculty Innovation Award
- 01/2021 Long Plenary talk (equivalent to Best Paper) at QIP 2021
- 04/2020 NSF CAREER Award
- 01–05/2020 Research Fellowship, Simons Institute for the Theory of Computing
- 08/2018 Appreciation to Mentor, Portland Saturday Academy K-12 Apprenticeship
- 01/2015 Plenary talk (equivalent to Best Paper) at QIP 2015
Happy to serve on the program committee of SCN 2026 to be hosted in the historic town of Amalfi, Italy.
Chuhan Lu successfully defended her Ph.D. dissertation. Congrats Dr. Lu! Big thanks to the great committee: Drs. Ameeta Agrawal, Shravas Rao, Penghui Yao and Henry Yuen.