123 citations · 237 across the 13 of their papers we have counts for
14 papers · 1 filter
Blind Unforgeability implies Plus-One Unforgeability
Mehil Agarwal, Calliope S. Reimann, Fang Song
We prove that quantum blind-unforgeability implies quantum plus-one unforgeability, settling an open question in the literature. Since plus-one unforgeability is known not to imply…
Generalized Hybrid Search and Applications to Blockchain and Hash Function Security
Alexandru Cojocaru, Juan Garay, Fang Song
In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical cap…
Quantum Key-length Extension
Joseph Jaeger, Fang Song, Stefano Tessaro
Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to us…
Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security
Alexandru Cojocaru, Juan Garay, Aggelos Kiayias +2
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main…
Oblivious Transfer is in MiniQCrypt
Alex B. Grilo, Huijia Lin, Fang Song +1
MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achie…
Quantum security of hash functions and property-preservation of iterated hashing
Ben Hamlin, Fang Song
This work contains two major parts: comprehensively studying the security notions of cryptographic hash functions against quantum attacks and the relationships between them; and re…
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
Nai-Hui Chia, Sean Hallgren, Fang Song
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to av…
Quantum-secure message authentication via blind-unforgeability
Gorjan Alagic, Christian Majenz, Alexander Russell +1
Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical…
Pseudorandom States, Non-Cloning Theorems and Quantum Money
Zhengfeng Ji, Yi-Kai Liu, Fang Song
We propose the concept of pseudorandom states and study their constructions, properties, and applications. Under the assumption that quantum-secure one-way functions exist, we pres…
Early days following Grover's quantum search algorithm
Fang Song
This is a note accompanying "CS 410/510: INTRO TO QUANTUM COMPUTING" I taught at Portland State University in Spring 2017. It is a review and summary of some early results related…
Zero-knowledge proof systems for QMA
Anne Broadbent, Zhengfeng Ji, Fang Song +1
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof sys…
Making Existential-Unforgeable Signatures Strongly Unforgeable in the Quantum Random-Oracle Model
Edward Eaton, Fang Song
Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a…
Classical Cryptographic Protocols in a Quantum World
Sean Hallgren, Adam Smith, Fang Song
Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these…
A Note on Quantum Security for Post-Quantum Cryptography
Fang Song
Shor's quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on…