Aristeidis Tentes

Key Dependent Message Secure Schemes


Roughly speaking, KDM secure schemes are CPA secure encryption schemes, 
where the adversary is even allowed to ask for encryptions of h(sk), 
where h belongs to some function family H  and sk the secret key. We 
are going to cover the scheme of BHHO08, where H is the family of affine 
functions and its security is based on DDH assumption. Then we will see 
how we can use this scheme to construct a bounded KDM secure scheme, 
where H is the set of all functions which can be computed by circuits of 
bounded size. In the proof of security of the latter scheme the query 
function is used in a non black box way and we will see that this fact 
is actually inherent. These results are included in BHHI09.

LINKS (Related Papers):

[BHHO09]: Dan Boneh, Shai Halevi, Michael Hamburg, Rafail Ostrovsky: 
Circular-Secure Encryption from Decision Diffie-Hellman. CRYPTO 2008: 108-125 

[BHHI09]: Boaz Barak, Iftach Haitner, Dennis Hofheinz, Yuval Ishai:
Bounded Key-Dependent Message Security