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 INDCPA 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 nontrivial result known for GSD. In this paper we give almostpolynomial reductions for large classes of graphs. Most importantly, we prove the security of the GSD game restricted to trees losing only a quasipolynomial factor n3 log n+5. Trees are an important special case capturing realworld 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; Nontrivial; Trees (mathematics); Complexity leveraging; Forestry; Cryptography; Encryption protocols; Logical key hierarchy; Polynomial reduction; Quasipolynomial; 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:

20150801

Start Page: 
601

End Page:

620

Sponsor: 
G. Fuchsbauer and K. Pietrzak—Supported by the European Research Council, ERC Starting Grant (259668PSPC).

URL: 

DOI: 
10.1007/9783662479896_29

Notes: 
We would like to thank the anonymous reviewers for their valuable comments.

Open access: 
yes (repository) 