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.
601 - 620
CRYPTO: International Cryptology Conference
Santa Barbara, CA, USA
2015-08-16 – 2015-08-20
Fuchsbauer G, Jafargholi Z, Pietrzak KZ. A quasipolynomial reduction for generalized selective decryption on trees. In: Vol 9215. Springer; 2015:601-620. doi:10.1007/978-3-662-47989-6_29
Fuchsbauer, G., Jafargholi, Z., & Pietrzak, K. Z. (2015). A quasipolynomial reduction for generalized selective decryption on trees (Vol. 9215, pp. 601–620). Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, USA: Springer. https://doi.org/10.1007/978-3-662-47989-6_29
Fuchsbauer, Georg, Zahra Jafargholi, and Krzysztof Z Pietrzak. “A Quasipolynomial Reduction for Generalized Selective Decryption on Trees,” 9215:601–20. Springer, 2015. https://doi.org/10.1007/978-3-662-47989-6_29.
G. Fuchsbauer, Z. Jafargholi, and K. Z. Pietrzak, “A quasipolynomial reduction for generalized selective decryption on trees,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, USA, 2015, vol. 9215, pp. 601–620.
Fuchsbauer G, Jafargholi Z, Pietrzak KZ. 2015. A quasipolynomial reduction for generalized selective decryption on trees. CRYPTO: International Cryptology Conference, LNCS, vol. 9215. 601–620.
Fuchsbauer, Georg, et al. A Quasipolynomial Reduction for Generalized Selective Decryption on Trees. Vol. 9215, Springer, 2015, pp. 601–20, doi:10.1007/978-3-662-47989-6_29.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
IST-2016-674-v1+1_389.pdf 505.62 KB