Construction of a key-dependent message secure symmetric encryption scheme in the ideal cipher model

Abstract

Key-dependent message (KDM) security is an important security issue that has attracted much research in recent years. In this paper, we present a new construction of the symmetric encryption scheme in the the ideal cipher model (ICM); we prove that our scheme is KDM secure against active attacks with respect to arbitrary polynomialtime challenge functions. Our main idea is to introduce a universal hash function (UHF) h as a random value for each encryption, and then use s = h(sk) as the key of the ideal cipher F, where sk is the private key of our symmetric encryption scheme. Although many other schemes that are secure against KDM attacks have already been proposed, in both the ideal standard models, the much more significance of our paper is the simplicity in which we implement KDM security against active attacks.

Keywords

symmetric encryption / key-dependent message / challenge function / universal hash function / ideal cipher model

References

[1] AdãoP, BanaG, HerzogJ, ScedrovA. Soundness of formal encryption in the presence of key-cycles. In: Proceedings of the 10th European Symposium on Research in Computer Security. 2005, 374-369

[2] BlackJ, RogawayP, ShrimptonT. Encryption-scheme security in the presence of key-dependent messages. In: Proceedings of the 9th Annual International Workshop. 2002, 62-75

[3] CamenischJ, LysyanskayaA. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Proceedings of the 20th International Conference on the Theory and Application of Cryptographic Techniques. 2001, 93-118

[4] HaleviS, KrawczykH. Security under key-dependent inputs. In: Proceedings of the 14th ACM Conference on Computer and communications security. 2008, 466-475

[5] GoldwasserS, MicaliS. Probabilistic encryption. Journal of Computer and System Sciences, 1984, 28(2): 270-299

[6] BackesM, PfitzmannB, ScedrovA. Key-dependent message security under active attacks-BRSIM/UC-soundness of Dolev-Yao-style encryption with key cycles. Journal of Computer Security, 2008, 16(5): 497-530

[7] HofheinzD, UnruhD. Towards key-dependent message security in the standard model. In: Proceedings of the 27th International Conference on the Theory and Application of Cryptographic Techniques. 2008, 108-126

[8] HaitnerI, HolensteinT. On the (im)possibility of key dependent encryption. In: Proceedings of the 6th Theory of Cryptography Conference. 2009, 202-219

[9] ApplebaumB, CashD, PeikertC, SahaiA. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 595-618

[10] BarakB, HaitnerI, HofheinzD, IshaiY. Bounded key-dependent message security. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptographic Techniques. 2010, 423-444

[11] BonehD, HaleviS, HamburgM, OstrovskyR. Circular-secure encryption from decision Diffie-Hellman. In: Proceedings of the 28th Annual International Cryptology Conference. 2008, 108-125

[12] BrakerskiZ, GoldwasserS. Circular and leakage resilient public-key encryption under subgroup indistinguishability. In: Proceedings of the 30th Annual International Cryptology Conference. 2010, 1-20

[13] CamenischJ, ChandranN, ShoupV. A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In: Proceedings of the 28th International Conference on the Theory and Application of Cryptographic Techniques. 2009, 351-368

[14] BrakerskiZ, GoldwasserS, KalaiY T. Black-Box Circular-secure encryption beyond affine functions. In: Proceedings of the 8th Theory of Cryptography Conference. 2011, 201-218

[15] ApplebaumB. Key-dependent message security: Generic amplification and completeness theorems. In: Proceedings of the 30th International Conference on the Theory and Application of Cryptographic Techniques. 2011, 527-546

[16] CarterL, wegmanM N. Universal classes of hash functions. Journal of Computer and System Science, 1979, 18(2): 143-154

[17] ImpagliazzoR, ZuckermanD. How to recycle random bits. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science. 1989, 248-253

[18] ImpagliazzoR, LevinL A, LubyM. Pseudo-random generation from one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing. 1989, 12-24

[19] StinsonD R. Universal hash families and the leftover hash lemma, and applications to cryptography and computing. Journal of Combinatorial Mathematics and Combinatorial Computing. 2002, 42: 3-31

[20] ShannonC. Communication theory of secrecy systems. Bell Systems Technical Journal. 1949, 28(4): 656-715

[21] BlackJ. The Ideal-Cipher Model, Revisited: An uninstantiable blockbased hash function. In: Proceedings of the 13th International Workshop Fast Software Encryption. 2006, 328-340

[22] HolensteinT, KünzlerR, TessaroS. The equivalence of the random oracle model and the ideal cipher model, revisited. In: Proceedings of the 43rd ACM Symposium on Theory of Computing. 2011, 89-98

[23] CoronJ S, PatarinJ, SeurinY. The random oracle model and the ideal cipher model are equivalent. In: Proceedings of the 28th Annual International Cryptology Conference. 2008, 1-20

[24] DodisY, PuniyaP. On the relation between the ideal cipher and the random oracle models. In: Proceedings of the 3rd Theory of Cryptography Conference. 2006, 184-206

[25] CanettiR, GoldreichO, HaleviS. The random oracle methodology, revisited. Journal of the ACM. 2004, 51(4): 557-594

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg