1 of 57

Lifting theorem(s): �From classical to quantum security

GAPS seminar

2026 04 10

Minki Hhan (KAIST)

2 of 57

This talk: Lifting theorems

Reducing quantum security using classical security

When using it, you don’t need to know quantum!

I’ll mainly talk about the proof.

The proof is quantum. I’ll try to avoid “quantum”, but…

Half of the talk is about “classical” lifting theorem!

* Many thanks to my coauthors, especially Qipeng Liu who taught me about the overview of the proof in this talk

3 of 57

Contents

Quantum gossips

Classical Lifting Theorem for functions

(Simplest) Quantum Lifting for functions

Lifting for permutations

Open problems

4 of 57

Post-quantum security

We all know Shor’s algorithm is likely to break RSA/ECDLP

7 of 57

Post-quantum security of �SYMMETRIC CRYPTOGRAPHY

We’ll talk about the post-quantum security of symmetric crypto

Attack side: Grover gives quadratic speedup

.. sometimes better attacks

or sometimes worse (main reason: online queries are classical)

8 of 57

What about the proof side?

For classical oracles, we can do many things:

lazily sample the outputs
or even program the outputs as long as they look random
know the specific inputs that adversary cares about
easily analyze the bad events (e.g. collisions)

… but everything becomes nontrivial to analyze quantum-accessible ideal oracles

9 of 57

Some quantum tools

To some extent, related techniques are developed

Adversarial/polynomial method
Compressed oracles (aka quantum lazy sampling)
Several reprogramming & resampling lemmas
One-way-to-hiding lemmas

But they are occasionally hard-to-analyze..

10 of 57

… easier quantum security proofs?

Are there “quantum-friendly” one-shot proofs, �or at least can all quantum details be hidden inside of toolkits?

..at least for some problems?

Ideally, can we “upgrade” classical security to quantum security?

11 of 57

Lifting theorem!

Classical vs Quantum Random Oracles

Takashi Yamakawa & Mark Zhandry

Eurocrypt 2021

12 of 57

Lifting theorem roughly says that:

13 of 57

Classical lifting theorem

14 of 57