Random Oracles in a Quantum World

Details Random Oracles in a Quantum World Random Oracles in a Quantum World

2010-08-05

arxiv.org/abs/1008.0931v2

full version of Advances in Cryptology - ASIACRYPT 2011, pages 41-69, 2011

Physics

Quantum Physics

38 pages, v2: many substantial changes and extensions, merged with a related paper by Boneh and Zhandry

Scientific paper

The interest in post-quantum cryptography - classical systems that remain secure in the presence of a quantum adversary - has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum states. We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore post-quantum secure. We conclude with a rich set of open problems in this area.

Affiliated with

Also associated with

No associations

Rating

Random Oracles in a Quantum World does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random Oracles in a Quantum World, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Oracles in a Quantum World will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-438281