Skip to main content
placeholder image

Iterated random oracle: A universal approach for finding loss in security reduction

Chapter


Abstract


  • 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 260 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/260 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.

Publication Date


  • 2016

Citation


  • Guo, F., Susilo, W., Mu, Y., Chen, R., Lai, J., & Yang, G. (2016). Iterated random oracle: A universal approach for finding loss in security reduction. In Unknown Book (Vol. 10032 LNCS, pp. 745-776). doi:10.1007/978-3-662-53890-6_25

International Standard Book Number (isbn) 13


  • 9783662538890

Scopus Eid


  • 2-s2.0-85008178639

Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 745

End Page


  • 776

Abstract


  • 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 260 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/260 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.

Publication Date


  • 2016

Citation


  • Guo, F., Susilo, W., Mu, Y., Chen, R., Lai, J., & Yang, G. (2016). Iterated random oracle: A universal approach for finding loss in security reduction. In Unknown Book (Vol. 10032 LNCS, pp. 745-776). doi:10.1007/978-3-662-53890-6_25

International Standard Book Number (isbn) 13


  • 9783662538890

Scopus Eid


  • 2-s2.0-85008178639

Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 745

End Page


  • 776