On the security of padding-based encryption schemes – or – why we cannot prove OAEP secure in the standard model. (English) Zbl 1239.94054
Joux, Antoine (ed.), Advances in cryptology – EUROCRYPT 2009. 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26–30, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-01000-2/pbk). Lecture Notes in Computer Science 5479, 389-406 (2009).
Summary: We investigate the security of “padding-based” encryption schemes in the standard model. This class contains all public-key encryption schemes where the encryption algorithm first applies some invertible public transformation to the message (the “padding”), followed by a trapdoor permutation. In particular, this class contains OAEP and its variants.
Our main result is a black-box impossibility result showing that one cannot prove any such padding-based scheme chosen-ciphertext secure even assuming the existence of ideal trapdoor permutations. The latter is a strong ideal abstraction of trapdoor permutations which inherits all security properties of uniform random permutations.
For the entire collection see [Zbl 1161.94003].
Our main result is a black-box impossibility result showing that one cannot prove any such padding-based scheme chosen-ciphertext secure even assuming the existence of ideal trapdoor permutations. The latter is a strong ideal abstraction of trapdoor permutations which inherits all security properties of uniform random permutations.
For the entire collection see [Zbl 1161.94003].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Abe, M., Kiltz, E., Okamoto, T.: CCA-security with optimal ciphertext overhead. In: ASIACRYPT, pp. 355–371 (2008) · Zbl 1206.94047 |
| [2] | Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, pp. 62–73 (1993) · doi:10.1145/168588.168596 |
| [3] | Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995) · Zbl 0881.94010 · doi:10.1007/BFb0053428 |
| [4] | Bellare, M., Sahai, A.: Non-malleable encryption: Equivalence between two notions, and an indistinguishability-based characterization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 519–536. Springer, Heidelberg (1999) · Zbl 0942.94024 · doi:10.1007/3-540-48405-1_33 |
| [5] | Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998) · Zbl 0931.94017 · doi:10.1007/BFb0055716 |
| [6] | Boldyreva, A., Fischlin, M.: Analysis of random oracle instantiation scenarios for OAEP and other practical schemes. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 412–429. Springer, Heidelberg (2005) · Zbl 1145.94459 · doi:10.1007/11535218_25 |
| [7] | Boldyreva, A., Fischlin, M.: On the security of OAEP. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 210–225. Springer, Heidelberg (2006) · Zbl 1172.94563 · doi:10.1007/11935230_14 |
| [8] | Boneh, D.: Simplified OAEP for the RSA and rabin functions. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 275–291. Springer, Heidelberg (2001) · Zbl 1002.94526 · doi:10.1007/3-540-44647-8_17 |
| [9] | Brown, D.R.L.: What hashes make RSA-OAEP secure? Cryptology ePrint Archive, Report 2006/223 (2006), http://eprint.iacr.org/ |
| [10] | Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004) · Zbl 1204.94063 · doi:10.1145/1008731.1008734 |
| [11] | Canetti, R., Micciancio, D., Reingold, O.: Perfectly one-way probabilistic hash functions (preliminary version). In: STOC, pp. 131–140 (1998) · Zbl 1029.68536 · doi:10.1145/276698.276721 |
| [12] | Chevallier-Mames, B., Phan, D.H., Pointcheval, D.: Optimal asymmetric encryption and signature paddings. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 254–268. Springer, Heidelberg (2005) · Zbl 1126.68388 · doi:10.1007/11496137_18 |
| [13] | Coron, J.-S., Joye, M., Naccache, D., Paillier, P.: Universal padding schemes for RSA. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 226–241. Springer, Heidelberg (2002) · Zbl 1026.94526 · doi:10.1007/3-540-45708-9_15 |
| [14] | Cramer, R., Hanaoka, G., Hofheinz, D., Imai, H., Kiltz, E., Pass, R., Shelat, A., Vaikuntanathan, V.: Bounded CCA2-secure encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 502–518. Springer, Heidelberg (2007) · Zbl 1153.94363 · doi:10.1007/978-3-540-76900-2_31 |
| [15] | Damgård, I.: Collision free hash functions and public key signature schemes. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 203–216. Springer, Heidelberg (1988) · Zbl 0647.94011 · doi:10.1007/3-540-39118-5_19 |
| [16] | Dodis, Y., Freedman, M.J., Jarecki, S., Walfish, S.: Versatile padding schemes for joint signature and encryption. In: ACM CCS, pp. 344–353 (2004) · doi:10.1145/1030083.1030129 |
| [17] | Dodis, Y., Oliveira, R., Pietrzak, K.: On the generic insecurity of the full domain hash. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 449–466. Springer, Heidelberg (2005) · Zbl 1145.94440 · doi:10.1007/11535218_27 |
| [18] | Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP is secure under the RSA assumption. Journal of Cryptology 17(2), 81–104 (2004) · Zbl 1083.68038 · doi:10.1007/s00145-002-0204-y |
| [19] | Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: FOCS, pp. 305–313 (2000) · doi:10.1109/SFCS.2000.892119 |
| [20] | Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: FOCS, pp. 325–335 (2000) · doi:10.1109/SFCS.2000.892121 |
| [21] | Gertner, Y., Malkin, T.G., Myers, S.: Towards a separation of semantic and CCA security for public key encryption. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 434–455. Springer, Heidelberg (2007) · Zbl 1129.94021 · doi:10.1007/978-3-540-70936-7_24 |
| [22] | Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: FOCS, pp. 126–135 (2001) · doi:10.1109/SFCS.2001.959887 |
| [23] | Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC, pp. 25–32 (1989) · doi:10.1145/73007.73010 |
| [24] | Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS, pp. 102–115 (2003) |
| [25] | Haitner, I.: Implementing oblivious transfer using collection of dense trapdoor permutations. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 394–409. Springer, Heidelberg (2004) · Zbl 1197.94189 · doi:10.1007/978-3-540-24638-1_22 |
| [26] | Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 92–105. Springer, Heidelberg (2004) · Zbl 1104.94025 · doi:10.1007/978-3-540-28628-8_6 |
| [27] | Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: STOC, pp. 44–61 (1989) · Zbl 0718.68042 · doi:10.1145/73007.73012 |
| [28] | Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: FOCS, pp. 535–542 (1999) |
| [29] | Kobara, K., Imai, H.: OAEP++: A very simple way to apply OAEP to deterministic OW-CPA primitives. Cryptology ePrint Archive, Report 2002/130 (2002), http://eprint.iacr.org/ |
| [30] | Komano, Y., Ohta, K.: Efficient universal padding techniques for multiplicative trapdoor one-way permutation. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 366–382. Springer, Heidelberg (2003) · Zbl 1122.94381 · doi:10.1007/978-3-540-45146-4_22 |
| [31] | Lindell, Y.: A simpler construction of CCA2-secure public-key encryption under general assumptions. Journal of Cryptology 19(3), 359–377 (2006) · Zbl 1103.68528 · doi:10.1007/s00145-005-0345-x |
| [32] | Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: FOCS, pp. 120–130 (1999) · doi:10.1109/SFFCS.1999.814584 |
| [33] | Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC (1990) · doi:10.1145/100216.100273 |
| [34] | Okamoto, T., Pointcheval, D.: REACT: Rapid enhanced-security asymmetric cryptosystem transform. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 159–175. Springer, Heidelberg (2001) · Zbl 0991.94046 · doi:10.1007/3-540-45353-9_13 |
| [35] | Paillier, P., Villar, J.L.: Trading one-wayness against chosen-ciphertext security in factoring-based encryption. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 252–266. Springer, Heidelberg (2006) · Zbl 1172.94593 · doi:10.1007/11935230_17 |
| [36] | Phan, D.H., Pointcheval, D.: Chosen-ciphertext security without redundancy. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 1–18. Springer, Heidelberg (2003) · Zbl 1205.94096 · doi:10.1007/978-3-540-40061-5_1 |
| [37] | Phan, D.H., Pointcheval, D.: OAEP 3-round:A generic and secure asymmetric encryption padding. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 63–77. Springer, Heidelberg (2004) · Zbl 1094.94519 · doi:10.1007/978-3-540-30539-2_5 |
| [38] | Rackoff, C., Simon, D.R.: Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 433–444. Springer, Heidelberg (1993) · Zbl 0767.94006 · doi:10.1007/3-540-48071-4_30 |
| [39] | Rosen, A., Segev, G.: Chosen-ciphertext security via correlated products. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 419–436. Springer, Heidelberg (2009) · Zbl 1213.94130 · doi:10.1007/978-3-642-00457-5_25 |
| [40] | Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997) · doi:10.1007/3-540-69053-0_18 |
| [41] | Shoup, V.: OAEP reconsidered. Journal of Cryptology 15(4), 223–249 (2002) · Zbl 1023.94006 · doi:10.1007/s00145-002-0133-9 |
| [42] | Simon, D.R.: Findings Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998) · Zbl 0919.94032 · doi:10.1007/BFb0054137 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
