Summary: Generalized Selective Decryption (GSD), introduced by S. Panjwani [TCC 2007, Lect. Notes Comput. Sci. 4392, 21–40 (2007; Zbl 1129.94033)], is a game for a symmetric encryption scheme \(\mathsf{Enc}\) that captures the difficulty of proving adaptive security of certain protocols, most notably the Logical Key Hierarchy (LKH) multicast encryption protocol. In the GSD game there are \(n\) keys \(k_1,\ldots ,k_n\), which the adversary may adaptively corrupt (learn); moreover, it can ask for encryptions \(\mathsf{Enc}_{k_i}(k_j)\) of keys under other keys. The adversary’s task is to distinguish keys (which it cannot trivially compute) from random. Proving the hardness of GSD assuming only IND-CPA security of \(\mathsf{Enc}\) is surprisingly hard. Using ”complexity leveraging” loses a factor exponential in \(n\), which makes the proof practically meaningless.{ }We can think of the GSD game as building a graph on \(n\) vertices, where we add an edge \(i\to j\) when the adversary asks for an encryption of \(k_j\) under \(k_i\). If restricted to graphs of depth \(\ell \), Panjwani gave a reduction that loses only a factor exponential in \(\ell \) (not \(n\)). To date, this is the only non-trivial result known for GSD.{ }In this paper we give almost-polynomial reductions for large classes of graphs. Most importantly, we prove the security of the GSD game restricted to trees losing only a quasi-polynomial factor \(n^{3\log n+5}\). Trees are an important special case capturing real-world protocols like the LKH protocol. Our new bound improves upon Panjwani’s on some LKH variants proposed in the literature where the underlying tree is not balanced. Our proof builds on ideas from the “nested hybrids” technique recently introduced by G. Fuchsbauer et al. [Asiacrypt 2014, Lect. Notes Comput. Sci. 8874, 82–101 (2014; Zbl 1317.94107)] for proving the adaptive security of constrained PRFs.
For the entire collection see [Zbl 1319.94002].