Generic Construction of Publicly Verifiable Predicate
Encryption
Chuting Tan
Harbin Institute of Technology
Shenzhen Graduate School
Shenzhen 518055, China
cttanhit13@cs.hitsz.edu.cn
Zoe L.jiang
∗
Harbin Institute of Technology
Shenzhen Graduate School,
and Guangdong Provincial
Key Laboratory of High
Perfor mance Computing
Shenzhen 518055, China
zoeljiang@gmail.com
Xuan Wang
†
Harbin Institute of Technology
Shenzhen Graduate School,
Public Service Platform of
Mobile Internet Application
Security Industry
Shenzhen 518055, China
wangxuan@cs.hitsz.edu.cn
S.M. Yiu
The University of Hong Kong
HKSAR, China
smyiu@cs.hku.hk
Junbin Fang
Jinan University
Guangzhou, 510632, China
junbinfang@gmail.com
Jin Li
Guangzhou University
Guangzhou, 510006, China
jinli71@gmail.com
Yabin Jin
Harbin Institute of Technology
Shenzhen Graduate School
Shenzhen 518055, China
jinyabin@cs.hitsz.edu.cn
Jiajun Huang
Harbin Institute of Technology
Shenzhen Graduate School
Shenzhen 518055, China
jiajunhuang@cs.hitsz.edu.cn
ABSTRACT
There is an increasing trend for data owners to store their
data in a third-party cloud server and buy the service from
the cloud server to provide information to other users. To
ensure confidentiality, the data is usually encrypted. There-
fore, a searching scheme for encrypted data (without de-
crypting the data) with privacy preserving property is of
paramount importance. Predicate encryption (PE) is one
of the attractive solutions due to its attribute-hiding merit.
Also, as the cloud service provider is not always trusted,
verifying the searched results is also crucial. In this paper,
we first propose a generic construction for a Publicly Ver-
ifiable Predicate Encryption (PVPE) scheme which allows
users to verify the results returned by the server. We then
prove the security of the PVPE scheme by reducing it to
the security of PE. To make the scheme more practical, we
further improve the PVPE scheme to reduce both the com-
munication and computation overheads with a trade-off of
having a small probability that the verification may fail.
∗
joint first author
†
Corresponding author
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full cita-
tion on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-
publish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
ASIA CCS ’16, May 30-June 03, 2016, Xi’an, China
c
2016 ACM. ISBN 978-1-4503-4233-9/16/05. . . $15.00
DOI: http://dx.doi.org/10.1145/2897845.2897919
Keywords
predicate encryption; publicly verifiable computation; cloud
computation
1. INTRODUCTION
Advances in networking technology and an increase in the
need for computing resources have prompted many organiza-
tions to outsource their storage and computing needs. This
new economic and computing model is commonly achievable
by cloud computing [16]. With the advent of cloud comput-
ing, data owners are motivated to outsource their complex
data management systems from local sites to the commer-
cial public cloud for greater flexibility and economic sav-
ings. However to protect data privacy, sensitive data has to
be encrypted before outsourcing, which obsoletes traditional
data utilization based on plaintext keyword search. Thus,
enabling an encrypted cloud data search service (without
decrypting the data) is of paramount importance.
The notion of Predicate Encryption (PE) was explicitly
presented by Katz, etc. [17] as a generalized (fine-grained)
notion of encryption that covers Identity-Based Encryption
(IBE) [8], Hidden-Vector Encryption (HVE) [9] and Attribute-
Based Encryption (ABE) [14, 5]. The characteristics of PE
include attribute-hiding and supporting multiple search cri-
teria which are suitable for searching encrypted data.
Informally, a secret key sk
f
in a predicate encryption
scheme corresponds to a predicate f ∈ F. A sender as-
sociates a ciphertext c ∈ C with an attribute set I ∈ Σ; the
ciphertext c associated with the attribute set I can be de-
crypted by the secret key sk
f
corresponding to the predicate
f if and only if f(I) = 1, meaning that I satisfies f . In ad-
dition, a security notion for PE, attribute-hiding, which is
stronger than the basic security requirement (payload hid-