Paper 2017/453

Subtleties in Security Definitions for Predicate Encryption with Public Index

Johannes Blömer and Gennadij Liske

Abstract

We take a critical look at established security definitions for predicate encryption (PE) with public index under chosen-plaintext attack (CPA) and under chosen-ciphertext attack (CCA). In contrast to conventional public-key encryption (PKE), security definitions for PE have to deal with user collusion which is modeled by an additional key generation oracle. We identify three different formalizations of key handling in the literature implicitly assumed to lead to the same security notion. Contrary to this assumption we prove that the corresponding models result in two different security notions under CPA and three different security notions under CCA. Similarly to the recent results for PKE and conventional key-encapsulation mechanism (KEM) (Journal of Cryptology, 2015) we also analyze subtleties in security definitions for PE and predicate key-encapsulation mechanism (P-KEM) regarding the so-called "no-challenge-decryption" condition. While the results for PE and PKE are similar, the results for P-KEM significantly differ from the corresponding results for conventional KEM. Our analysis is based on appropriate definitions of semantic security and indistinguishability of encryptions for PE under different attacks scenarios. These definitions complement related security definitions for identity-based encryption and functional encryption. As a result of our work we suggest security definitions for PE and P-KEM under different attack scenarios.