Robust encryption, revisited. (English) Zbl 1314.94068
Kurosawa, Kaoru (ed.) et al., Public-key cryptography – PKC 2013. 16th international conference on practice and theory in public-key cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36361-0/pbk). Lecture Notes in Computer Science 7778, 352-368 (2013).
Summary: We revisit the notions of robustness introduced by Abdalla, Bellare, and Neven [M. Abdalla et al., TCC 2010, Lect. Notes Comput. Sci. 5978, 480–497 (2010; Zbl 1274.94032)]. One of the main motivations for the introduction of strong robustness for public-key encryption (PKE) by Abdalla et al. is to prevent certain types of attack on Sako’s auction protocol. We show, perhaps surprisingly, that Sako’s protocol is still vulnerable to attacks exploiting robustness problems in the underlying PKE scheme, even when it is instantiated with a strongly robust scheme. This demonstrates that current notions of robustness are insufficient even for one of its most natural applications. To address this and other limitations in existing notions, we introduce a series of new robustness notions for PKE and explore their relationships. In particular, we introduce complete robustness, our strongest new notion of robustness, and give a number of constructions for completely robust PKE schemes.
For the entire collection see [Zbl 1258.94004].
For the entire collection see [Zbl 1258.94004].
MSC:
| 94A60 | Cryptography |
Citations:
Zbl 1274.94032References:
| [1] | Abdalla, M.; Bellare, M.; Catalano, D.; Kiltz, E.; Kohno, T.; Lange, T.; Malone-Lee, J.; Neven, G.; Paillier, P.; Shi, H., Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions, Journal of Cryptology, 21, 3, 350-391 (2008) · Zbl 1161.94378 · doi:10.1007/s00145-007-9006-6 |
| [2] | Abdalla, M.; Bellare, M.; Neven, G.; Micciancio, D., Robust Encryption, Theory of Cryptography, 480-497 (2010), Heidelberg: Springer, Heidelberg · Zbl 1274.94032 · doi:10.1007/978-3-642-11799-2_28 |
| [3] | Barth, A.; Boneh, D.; Waters, B.; Di Crescenzo, G.; Rubin, A., Privacy in Encrypted Content Distribution Using Private Broadcast Encryption, Financial Cryptography and Data Security, 52-64 (2006), Heidelberg: Springer, Heidelberg · Zbl 1152.94402 · doi:10.1007/11889663_4 |
| [4] | Bellare, M.; Boldyreva, A.; Desai, A.; Pointcheval, D.; Boyd, C., Key-Privacy in Public-Key Encryption, Advances in Cryptology - ASIACRYPT 2001, 566-582 (2001), Heidelberg: Springer, Heidelberg · Zbl 1064.94553 · doi:10.1007/3-540-45682-1_33 |
| [5] | Bellare, M.; Kohno, T.; Biham, E., A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications, Advances in Cryptology - EUROCRPYT 2003, 491-506 (2003), Heidelberg: Springer, Heidelberg · Zbl 1038.94520 · doi:10.1007/3-540-39200-9_31 |
| [6] | Black, J.; Rogaway, P.; Shrimpton, T.; Nyberg, K.; Heys, H., Encryption-Scheme Security in the Presence of Key-Dependent Messages, Selected Areas in Cryptography, 62-75 (2003), Heidelberg: Springer, Heidelberg · Zbl 1027.68594 · doi:10.1007/3-540-36492-7_6 |
| [7] | Boneh, D.; Di Crescenzo, G.; Ostrovsky, R.; Persiano, G.; Cachin, C.; Camenisch, J., Public Key Encryption with Keyword Search, Advances in Cryptology - EUROCRYPT 2004, 506-522 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.68424 · doi:10.1007/978-3-540-24676-3_30 |
| [8] | Boneh, D.; Katz, J.; Menezes, A., Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption, Topics in Cryptology - CT-RSA 2005, 87-103 (2005), Heidelberg: Springer, Heidelberg · Zbl 1079.94535 · doi:10.1007/978-3-540-30574-3_8 |
| [9] | Boneh, D.; Waters, B.; Vadhan, S. P., Conjunctive, Subset, and Range Queries on Encrypted Data, Theory of Cryptography, 535-554 (2007), Heidelberg: Springer, Heidelberg · Zbl 1156.94335 · doi:10.1007/978-3-540-70936-7_29 |
| [10] | Boyen, X.; Waters, B.; Dwork, C., Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles), Advances in Cryptology - CRYPTO 2006, 290-307 (2006), Heidelberg: Springer, Heidelberg · Zbl 1161.94390 · doi:10.1007/11818175_17 |
| [11] | Canetti, R.; Halevi, S.; Katz, J.; Cachin, C.; Camenisch, J., Chosen-Ciphertext Security from Identity-Based Encryption, Advances in Cryptology - EUROCRYPT 2004, 207-222 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94358 · doi:10.1007/978-3-540-24676-3_13 |
| [12] | Cramer, R.; Shoup, V.; Krawczyk, H., A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack, Advances in Cryptology - CRYPTO ’98, 13-25 (1998), Heidelberg: Springer, Heidelberg · Zbl 0931.94018 · doi:10.1007/BFb0055717 |
| [13] | Cramer, R.; Shoup, V., Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM Journal on Computing, 33, 167-226 (2003) · Zbl 1045.94013 · doi:10.1137/S0097539702403773 |
| [14] | Dodis, Y.; Kiltz, E.; Pietrzak, K.; Wichs, D.; Pointcheval, D.; Johansson, T., Message Authentication, Revisited, Advances in Cryptology - EUROCRYPT 2012, 355-374 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94117 · doi:10.1007/978-3-642-29011-4_22 |
| [15] | Farshim, P., Libert, B., Paterson, K.G., Quaglia, E.A.: Robust encryption, revisited. Cryptology ePrint Archive, Report 2012/673 (2012), Full version of this paper, http://eprint.iacr.org/ · Zbl 1314.94068 |
| [16] | Fischlin, M.; Stern, J., Pseudorandom Function Tribe Ensembles Based on One-Way Permutations: Improvements and Applications, Advances in Cryptology - EUROCRYPT ’99, 432-445 (1999), Heidelberg: Springer, Heidelberg · Zbl 0931.94044 · doi:10.1007/3-540-48910-X_30 |
| [17] | Hofheinz, D.; Kiltz, E.; Menezes, A., Secure Hybrid Encryption from Weakened Key Encapsulation, Advances in Cryptology - CRYPTO 2007, 553-571 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94051 · doi:10.1007/978-3-540-74143-5_31 |
| [18] | Hofheinz, D., Weinreb, E.: Searchable encryption with decryption in the standard model. Cryptology ePrint Archive, Report 2008/423 (2008), http://eprint.iacr.org/ |
| [19] | Katz, J.; Sahai, A.; Waters, B.; Smart, N. P., Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products, Advances in Cryptology - EUROCRYPT 2008, 146-162 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94323 · doi:10.1007/978-3-540-78967-3_9 |
| [20] | Kurosawa, K.; Desmedt, Y.; Franklin, M., A New Paradigm of Hybrid Encryption Scheme, Advances in Cryptology - CRYPTO 2004, 426-442 (2004), Heidelberg: Springer, Heidelberg · Zbl 1104.94028 · doi:10.1007/978-3-540-28628-8_26 |
| [21] | Libert, B.; Paterson, K. G.; Quaglia, E. A.; Fischlin, M.; Buchmann, J.; Manulis, M., Anonymous Broadcast Encryption: Adaptive Security and Efficient Constructions in the Standard Model, Public Key Cryptography - PKC 2012, 206-224 (2012), Heidelberg: Springer, Heidelberg · Zbl 1290.94107 · doi:10.1007/978-3-642-30057-8_13 |
| [22] | Mohassel, P.; Abe, M., A Closer Look at Anonymity and Robustness in Encryption Schemes, Advances in Cryptology - ASIACRYPT 2010, 501-518 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94062 · doi:10.1007/978-3-642-17373-8_29 |
| [23] | Sako, K.; Imai, H.; Zheng, Y., An Auction Protocol Which Hides Bids of Losers, Public Key Cryptography, 422-432 (2000), Heidelberg: Springer, Heidelberg · Zbl 0969.94023 · doi:10.1007/978-3-540-46588-1_28 |
| [24] | Shoup, V.: A proposal for an ISO standard for public key encryption (version 2.1). Cryptology ePrint Archive, Report 2001/112 (2001), http://eprint.iacr.org/ |
| [25] | Liu, Y.; Gu, D.; Liu, Z.; Li, W.; Ryan, M. D.; Smyth, B.; Wang, G., Impossible Differential Attacks on Reduced-Round LBlock, Information Security Practice and Experience, 97-108 (2012), Heidelberg: Springer, Heidelberg · Zbl 1291.94119 · doi:10.1007/978-3-642-29101-2_7 |
| [26] | Mace, F., Standaert, F.X., Quisquater, J.J.: ASIC Implementations of the Block Cipher SEA for Constrained Applications. Proceedings of the Third International Conference on RFID Security (2007), http://www.rfidsec07.etsit.uma.es/confhome.html |
| [27] | Mangard, S.; Standaert, F.-X., Cryptographic Hardware and Embedded Systems, CHES 2010 (2010), Heidelberg: Springer, Heidelberg · Zbl 1193.68012 |
| [28] | Matsui, M.; Helleseth, T., Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology - EUROCRYPT ’93, 386-397 (1994), Heidelberg: Springer, Heidelberg · Zbl 0951.94519 |
| [29] | Minematsu, K., Suzaki, T., Shigeri, M.: On Maximum Differential Probability of Generalized Feistel. In: Parampalli, Hawkes (eds.) [32], pp. 89-105 · Zbl 1280.94085 |
| [30] | Moradi, A.; Poschmann, A.; Ling, S.; Paar, C.; Wang, H.; Paterson, K. G., Pushing the Limits: A Very Compact and a Threshold Implementation of AES, Advances in Cryptology - EUROCRYPT 2011, 69-88 (2011), Heidelberg: Springer, Heidelberg · Zbl 1281.94044 · doi:10.1007/978-3-642-20465-4_6 |
| [31] | Özen, O.; Varıcı, K.; Tezcan, C.; Kocair, Ç.; Boyd, C.; González Nieto, J., Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT, Information Security and Privacy, 90-107 (2009), Heidelberg: Springer, Heidelberg · Zbl 1307.94084 · doi:10.1007/978-3-642-02620-1_7 |
| [32] | Parampalli, U.; Hawkes, P., Information Security and Privacy (2011), Heidelberg: Springer, Heidelberg · Zbl 1217.94003 |
| [33] | Poschmann, A.: Lightweight Cryptography - Cryptographic Engineering for a Pervasive World. Cryptology ePrint Archive, Report 2009/516 (2009), http://eprint.iacr.org/ |
| [34] | Poschmann, A., Ling, S., Wang, H.: 256 Bit Standardized Crypto for 650 GE - GOST Revisited. In: Mangard, Standaert (eds.) [27], pp. 219-233 · Zbl 1297.94098 |
| [35] | Preneel, B.; Takagi, T., Cryptographic Hardware and Embedded Systems - CHES 2011 (2011), Heidelberg: Springer, Heidelberg · Zbl 1223.68010 |
| [36] | Rinne, S.: Performance Analysis of Contemporary Light-Weight Cryptographic Algorithms on a Smart Card Microcontroller. SPEED - Software Performance Enhancement for Encryption and Decryption (2007), http://www.hyperelliptic.org/SPEED/start07.html |
| [37] | Rinne, S., Eisenbarth, T., Paar, C.: Performance Analysis of Contemporary Lightweight Block Ciphers on 8-bit Microcontrollers. SPEED-CC - Software Performance Enhancement for Encryption and Decryption and Cryptographic Compilers (2009), http://www.hyperelliptic.org/SPEED/ |
| [38] | Rolfes, C.; Poschmann, A.; Leander, G.; Paar, C.; Grimaud, G.; Standaert, F.-X., Ultra-Lightweight Implementations for Smart Devices - Security for 1000 Gate Equivalents, Smart Card Research and Advanced Applications, 89-103 (2008), Heidelberg: Springer, Heidelberg · Zbl 1184.68243 · doi:10.1007/978-3-540-85893-5_7 |
| [39] | Satoh, A.; Morioka, S.; Takano, K.; Munetoh, S.; Boyd, C., A Compact Rijndael Hardware Architecture with S-Box Optimization, Advances in Cryptology - ASIACRYPT 2001, 239-254 (2001), Heidelberg: Springer, Heidelberg · Zbl 1067.94563 · doi:10.1007/3-540-45682-1_15 |
| [40] | Shibutani, K., Isobe, T., Hiwatari, H., Mitsuda, A., Akishita, T., Shirai, T.: Piccolo: An Ultra-Lightweight Blockcipher. In: Preneel, Takagi (eds.) [35], pp. 342-357 · Zbl 1291.94154 |
| [41] | Shirai, T., Shibutani, K., Akishita, T., Moriai, S., Iwata, T.: The 128-Bit Blockcipher CLEFIA (Extended Abstract). In: Biryukov (ed.) [5], pp. 181-195 · Zbl 1186.94471 |
| [42] | Suzaki, T.; Minematsu, K.; Hong, S.; Iwata, T., Improving the Generalized Feistel, Fast Software Encryption, 19-39 (2010), Heidelberg: Springer, Heidelberg · Zbl 1279.94117 · doi:10.1007/978-3-642-13858-4_2 |
| [43] | Tsunoo, Y.; Tsujihara, E.; Shigeri, M.; Saito, T.; Suzaki, T.; Kubo, H.; Nyberg, K., Impossible Differential Cryptanalysis of CLEFIA, Fast Software Encryption, 398-411 (2008), Heidelberg: Springer, Heidelberg · Zbl 1154.94436 · doi:10.1007/978-3-540-71039-4_25 |
| [44] | Wu, W.; Zhang, L.; Lopez, J.; Tsudik, G., LBlock: A Lightweight Block Cipher, Applied Cryptography and Network Security, 327-344 (2011), Heidelberg: Springer, Heidelberg · Zbl 1250.94047 · doi:10.1007/978-3-642-21554-4_19 |
| [45] | Zheng, Y.; Matsumoto, T.; Imai, H.; Brassard, G., On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses, Advances in Cryptology - CRYPTO ’89, 461-480 (1990), Heidelberg: Springer, Heidelberg · Zbl 0722.94020 |
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.
