Paper 2015/955

On the Power of Pair Encodings: Frameworks for Predicate Cryptographic Primitives

Mridul Nandi and Tapas Pandit

Abstract

Recently Attrapadung (Eurocrypt 2014) proposed a generic framework for fully (adaptively) secure predicate encryption (PE) based on a new primitive, called pair encodings. The author shows that if the underlying pair encoding scheme is either perfectly secure or computationally (doubly-selectively) secure, then the PE scheme will be fully secure. Although the pair encodings were solely introduced for PE, we show that these can also be used to construct predicate signatures, a signature analogue of PE. More precisely, we propose a generic construction for predicate signature (PS) from the pair encoding schemes. Our construction provides the signer privacy, and unforgeability in the adaptive-predicate model. Thereafter, we instantiate many PS schemes with new results, e.g., the first practical PS schemes for regular languages, the first attribute-based signature (ABS) scheme with constant-size signatures in adaptive-predicate model, the unbounded ABS with large universes in key-policy flavor, etc. Following the CCA conversions of Yamada et al. (PKC 2011, 2012) and Nandi et al. (ePrint Archive: 2015/457), one can have CCA-secure PE from CPA-secure PE if the primitive PE has either verifiability or delegation. We show that the fully secure CPA-construction of Attrapadung possesses the verifiability. The aforesaid approach degrades the performance of the resultant CCA-secure PE scheme. As an alternative, we provide a direct fully secure CCA-construction for PE from the pair encoding scheme. This costs an extra computation of group element in encryption and three extra pairing computations in decryption as compared to the CPA-construction of Attrapadung. The predicate signcryption (PSC) is a super class of the existing class, the attribute-based signcryption (ABSC), where the confidentiality, unforgeability and signer privacy are well preserved. By combining the proposed frameworks for PS and PE, we provide a generic construction for PSC from the pair encodings. It achieves the perfect privacy, and the strong unforgeability and CCA security in the adaptive-predicates model. The construction has the support of combined-setup, where the distributions of public parameters and keys in the underlying signature and encryption schemes are identical. The proposed PSC provides many new results, e.g., the first PSC schemes for regular languages, the first ABSC with constant-size signcryptions and constant-size keys respectively, the unbounded ABSC with large universes in adaptive-predicates model, etc.

Note: We correct some mistakes and typos.