A quasipolynomial reduction for generalized selective decryption on trees Conference Paper

Author(s): Fuchsbauer, Georg; Jafargholi, Zahra; Pietrzak, Krzysztof
Title: A quasipolynomial reduction for generalized selective decryption on trees
Title Series: LNCS
Affiliation IST Austria
Abstract: Generalized Selective Decryption (GSD), introduced by Panjwani [TCC’07], is a game for a symmetric encryption scheme 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 k1,..., kn, which the adversary may adaptively corrupt (learn); moreover, it can ask for encryptions Encki (kj) 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 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 → j when the adversary asks for an encryption of kj under ki. If restricted to graphs of depth ℓ, Panjwani gave a reduction that loses only a factor exponential in ℓ (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 n3 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 Fuchsbauer et al. [Asiacrypt’14] for proving the adaptive security of constrained PRFs.
Keywords: Adaptive security; Non-trivial; Trees (mathematics); Complexity leveraging; Forestry; Cryptography; Encryption protocols; Logical key hierarchy; Polynomial reduction; Quasi-poly-nomial; Symmetric encryption schemes
Conference Title: CRYPTO: International Cryptology Conference
Volume: 9215
Conference Dates: August 16 - 20, 2015
Conference Location: Santa Barbara, CA, USA
Publisher: Springer  
Date Published: 2015-08-01
Start Page: 601
End Page: 620
Sponsor: G. Fuchsbauer and K. Pietrzak—Supported by the European Research Council, ERC Starting Grant (259668-PSPC).
DOI: 10.1007/978-3-662-47989-6_29
Notes: We would like to thank the anonymous reviewers for their valuable comments.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work