International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Qipeng Liu

Publications

Year
Venue
Title
2019
EUROCRYPT
On Finding Quantum Multi-collisions 📺
Qipeng Liu Mark Zhandry
A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, $$\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) $$ quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
2019
CRYPTO
Revisiting Post-quantum Fiat-Shamir 📺
Qipeng Liu Mark Zhandry
The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting. In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.
2017
TCC

Coauthors

Mark Zhandry (3)