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 that hold both in the private and in the public key settings: \begin{itemize} \item Let~$\mathcal{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 messages to one-way permutations (and also to families of trapdoor permutations) if the adversary can obtain encryptions of~$h(k)$ for~$h \in \mathcal{H}$.

\item There exists no reduction from an encryption scheme secure against key-dependent messages to, essentially, \emph{any} cryptographic assumption, if the adversary can obtain an encryption of~$g(k)$ for an \emph{arbitrary} $g$, as long as the reduction's proof of security treats both the adversary and the function $g$ as black boxes. \end{itemize}

Category / Keywords: Key-dependent input, Black-box separations, One-way functions

Publication Info: Will Appear in TCC 2009

Date: received 11 Apr 2008, last revised 29 Dec 2008

Contact author: iftachh at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20081229:205442 (All versions of this report)

Short URL: ia.cr/2008/164

Discussion forum: Show discussion | Start new discussion