Fang Song Explores Quantum Security in Post-Quantum Cryptography 🔐

IQC member Fang Song presented a talk titled: A Note on Quantum Security for Post-Quantum Cryptography at the 2014 PQCrypto conference in October, 2014.

Abstract: 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 computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as no-cloning.

This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are "quantum-friendly". We characterize sufficient conditions such that a classical reductions can be "lifted" to the quantum setting.

We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [10] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straight-forward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [47] and the simple hybrid arguments framework in [23]) can be reformulated under our unified framework.

PQCrypto
2014 Book: http://www.springer.com/computer/security+and+cryptology/book/978-3-319-11658-7
Workshop: https://pqcrypto2014.uwaterloo.ca/

Find out more about IQC!
Website - https://uwaterloo.ca/institute-for-qu...
Facebook - https://www.facebook.com/QuantumIQC
Twitter - https://twitter.com/QuantumIQC