Paper 2016/872

Iterated Random Oracle: A Universal Approach for Finding Loss in Security Reduction

Fuchun Guo, Willy Susilo, Yi Mu, Rongmao Chen, Jianchang Lai, and Guomin Yang


The indistinguishability security of a public-key cryptosystem can be reduced to a computational hard assumption in the random oracle model, where the solution to a computational hard problem is hidden in one of the adversary's queries to the random oracle. Usually, there is a finding loss in finding the correct solution from the query set, especially when the decisional variant of the computational problem is also hard. The problem of finding loss must be addressed towards tight(er) reductions under this type. In EUROCRYPT 2008, Cash, Kiltz and Shoup proposed a novel approach using a trapdoor test that can solve the finding loss problem. The simulator can find the correct solution with overwhelming probability 1, if there exists a trapdoor test for the adopted hard problem. The proposed approach is efficient and can be used for many Diffie-Hellman computational assumptions. The only limitation is the requirement of a trapdoor test that must be found for the adopted computational assumptions. In this paper, we introduce a universal approach for finding loss, namely Iterated Random Oracle, which can be applied to all computational assumptions. The finding loss in our proposed approach is very small. For $2^{60}$ queries to the random oracle, the success probability of finding the correct solution from the query set will be as large as $1/{64}$ compared to $1/{2^{60}}$ by a random pick. We show how to apply the iterated random oracle for security transformation from key encapsulation mechanism with one-way security to normal encryption with indistinguishability security. The security reduction is very tight due to a small finding loss. The transformation does not expand the ciphertext size. We also give the application of the iterated random oracle in the key exchange.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2016
Random OracleFinding Loss
Contact author(s)
fuchun @ uow edu au
2016-09-10: received
Short URL
Creative Commons Attribution


      author = {Fuchun Guo and Willy Susilo and Yi Mu and Rongmao Chen and Jianchang Lai and Guomin Yang},
      title = {Iterated Random Oracle: A Universal Approach for Finding Loss in Security Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2016/872},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.