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.
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 doi: 10.1016/0022-0000(84)90070-9
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 doi: 10.1007/978-3-642-00457-5_13
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 doi: 10.1007/978-3-642-19571-6_13
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 doi: 10.1016/0022-0000(79)90044-8
17
ImpagliazzoR, ZuckermanD. How to recycle random bits. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science. 1989, 248-253 doi: 10.1109/SFCS.1989.63486
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 doi: 10.1002/j.1538-7305.1949.tb00928.x
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 doi: 10.1007/11799313_21
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 doi: 10.1007/11681878_10
25
CanettiR, GoldreichO, HaleviS. The random oracle methodology, revisited. Journal of the ACM. 2004, 51(4): 557-594 doi: 10.1145/1008731.1008734
