Iterated Random Oracle: A Universal Approach for Finding Loss in Security Reduction
Authors: 
Fuchun Guo, Willy Susilo, Yi Mu, Rongmao Chen, Jianchang Lai, Guomin YangAuthors Info & Claims
Pages 745 - 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 tighter 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.
References
[1]
Abdalla, M., Ben Hamouda, F., Pointcheval, D.: Tighter reductions for forward-secure signature schemes. In: Kurosawa, K., Hanaoka, G. eds. PKC 2013. LNCS, vol. 7778, pp. 292---311. Springer, Heidelberg 2013.
[2]
Abdalla, M., Fouque, P.-A., Lyubashevsky, V., Tibouchi, M.: Tightly-secure signatures from lossy identification schemes. In: Pointcheval, D., Johansson, T. eds. EUROCRYPT 2012. LNCS, vol. 7237, pp. 572---590. Springer, Heidelberg 2012.
[3]
Abdalla, M., Pointcheval, D.: Simple password-based encrypted key exchange protocols. In: Menezes, A. ed. CT-RSA 2005. LNCS, vol. 3376, pp. 191---208. Springer, Heidelberg 2005.
[4]
Attrapadung, N., Furukawa, J., Gomi, T., Hanaoka, G., Imai, H., Zhang, R.: Efficient identity-based encryption with tight security reduction. In: Pointcheval, D., Mu, Y., Chen, K. eds. CANS 2006. LNCS, vol. 4301, pp. 19---36. Springer, Heidelberg 2006.
[5]
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. eds. CCS 1993, pp. 62---73. ACM 1993
[6]
Blazy, O., Kakvi, S.A., Kiltz, E., Pan, J.: Tightly-secure signatures from chameleon hash functions. In: Katz, J. ed. PKC 2015. LNCS, vol. 9020, pp. 256---279. Springer, Heidelberg 2015.
[7]
Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. eds. EUROCRYPT 2004. LNCS, vol. 3027, pp. 223---238. Springer, Heidelberg 2004.
[8]
Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. ed. CRYPTO 2001. LNCS, vol. 2139, pp. 213---229. Springer, Heidelberg 2001.
[9]
Boyen, X.: Miniature CCA2 PK encryption: tight security without redundancy. In: Kurosawa, K. ed. ASIACRYPT 2007. LNCS, vol. 4833, pp. 485---501. Springer, Heidelberg 2007.
[10]
Cash, D., Kiltz, E., Shoup, V.: The twin Diffie-Hellman problem and applications. In: Smart, N. ed. EUROCRYPT 2008. LNCS, vol. 4965, pp. 127---145. Springer, Heidelberg 2008.
[11]
Cash, D., Kiltz, E., Shoup, V.: The twin Diffie-Hellman problem and applications. J. Cryptology 224, 470---504 2009
[12]
Chen, L., Chen, Y.: The n-Diffie-Hellman problem and its applications. In: Lai, X., Zhou, J., Li, H. eds. ISC 2011. LNCS, vol. 7001, pp. 119---134. Springer, Heidelberg 2011.
[13]
Chevallier-Mames, B.: An efficient CDH-based signature scheme with a tight security reduction. In: Shoup, V. ed. CRYPTO 2005. LNCS, vol. 3621, pp. 511---526. Springer, Heidelberg 2005.
[14]
Chevallier-Mames, B., Joye, M.: A practical and tightly secure signature scheme without hash function. In: Abe, M. ed. CT-RSA 2007. LNCS, vol. 4377, pp. 339---356. Springer, Heidelberg 2006.
[15]
Coron, J.: A variant of boneh-franklin IBE with a tight reduction in the random oracle model. Des. Codes Cryptography 501, 115---133 2009
[16]
Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. ed. CRYPTO 1998. LNCS, vol. 1462, pp. 13---25. Springer, Heidelberg 1998.
[17]
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 226, 644---654 1976
[18]
Fiore, D., Gennaro, R.: Making the Diffie-Hellman protocol identity-based. In: Pieprzyk, J. ed. CT-RSA 2010. LNCS, vol. 5985, pp. 165---178. Springer, Heidelberg 2010.
[19]
Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. ed. CRYPTO 1999. LNCS, vol. 1666, pp. 537---554. Springer, Heidelberg 1999.
[20]
Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptology 261, 80---101 2013
[21]
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. eds. CRYPTO 1984. LNCS, vol. 196, pp. 10---18. Springer, Heidelberg 1985.
[22]
Gay, R., Hofheinz, D., Kiltz, E., Wee, H.: Tightly CCA-secure encryption without pairings. In: Fischlin, M., Coron, J.-S. eds. EUROCRYPT 2016. LNCS, vol. 9665, pp. 1---27. Springer, Heidelberg 2016.
[23]
Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudenay, S. ed. EUROCRYPT 2006. LNCS, vol. 4004, pp. 445---464. Springer, Heidelberg 2006.
[24]
Goh, E., Jarecki, S., Katz, J., Wang, N.: Efficient signature schemes with tight reductions to the diffie-hellman problems. J. Cryptology 204, 493---514 2007
[25]
Hofheinz, D., Jager, T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini, R., Canetti, R. eds. CRYPTO 2012. LNCS, vol. 7417, pp. 590---607. Springer, Heidelberg 2012.
[26]
Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: Jajodia, S., Atluri, V., Jaeger, T. eds. CCS 2003, pp. 155---164. ACM 2003
[27]
Kurosawa, K., Takagi, T.: Some RSA-based encryption schemes with tight security reduction. In: Laih, C.-S. ed. ASIACRYPT 2003. LNCS, vol. 2894, pp. 19---36. Springer, Heidelberg 2003.
[28]
Park, J.H., Lee, D.H.: An efficient ibe scheme with tight security reduction in the random oracle model. Des. Codes Crypt. 791, 63---85 2016
[29]
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: The 2000 Symposium on Cryptography and Information Security, vol. 45, pp. 26---28 2000
[30]
Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. ed. EUROCRYPT 2005. LNCS, vol. 3494, pp. 114---127. Springer, Heidelberg 2005.
- Iterated Random Oracle: A Universal Approach for Finding Loss in Security Reduction
Recommendations
Secure universal designated verifier signature without random oracles
In Asiacrypt 2003, the concept of universal designated verifier signature (UDVS) was introduced by Steinfeld, Bull, Wang and Pieprzyk. In the new paradigm, any signature holder (not necessarily the signer) can designate the publicly verifiable signature ...
Instantiability of Classical Random-Oracle-Model Encryption Transforms
Advances in Cryptology – ASIACRYPT 2022AbstractExtending work leveraging program obfuscation to instantiate random-oracle-based transforms (e.g., Hohenberger et al., EUROCRYPT 2014, Kalai el al., CRYPTO 2017), we show that, using obfuscation and other assumptions, there exist standard-model ...
Efficient and provably secure random oracle-free adaptive identity-based encryption with short-signature scheme
Identity-based encryption IBE is one of the important public key encryption techniques where not only the identity of the receiver is used for secure and efficient encryption, but it also has several merits over other traditional public-key ones. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 04 December 2016
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Jan 2025