Cryptology ePrint Archive: Report 2008/164

On the (Im)Possibility of Key Dependent Encryption

Iftach Haitner and Thomas Holenstein

Abstract: We study the possibility of constructing encryption schemes secure under messages that are chosen depending on the key k of the encryption scheme itself. We give the following separation results: 1. Let H be the family of poly(n)-wise independent hash-functions. There exists no fully-black-box reduction from an encryption scheme secure against key-dependent inputs to one-way permutations (and also to families of trapdoor permutations) if the adversary can obtain encryptions of h(k) for h \in H.

2. Let G be the family of polynomial sized circuits. There exists no reduction from an encryption scheme secure against key-dependent inputs to, seemingly, any cryptographic assumption, if the adversary can obtain an encryption of g(k) for g \in G, as long as the reduction's proof of security treats both the adversary and the function g as black box.

Category / Keywords: foundations / Key-dependent input security, black-box separation

Date: received 11 Apr 2008

Contact author: iftach haitner at weizmann ac il

Available formats: PDF | BibTeX Citation

Version: 20080414:062249 (All versions of this report)

Discussion forum: Show discussion | Start new discussion