  Privacy-preserving location-base services (LBS) have been proposed to protect
users' location privacy. However, there are still some problems in existing
schemes: (1) a semi-trusted third party (TTP) is required; or (2) both the
computation cost and communication cost to generate a query are linear in the
size of the queried area. In this paper, to improve query efficiency, an
oblivious location-based service query (OLBSQ) scheme is proposed. Our scheme
captures the following features: (1) a semi-trusted TTP is not required; (2) a
user can query services from a service provider without revealing her exact
location; (3) the service provider can only know the size of a query made by a
user; and (4) both the computation cost and the communication cost to generate
a query is constant, instead of linear in the size of the queried area. We
formalise the definition and security model of OLBSQ schemes. The security of
our scheme is reduced to well-known complexity assumptions. The novelty is to
reduce the computation cost and communication cost of making a query and enable
the service provider to obliviously and incrementally generate decrypt keys for
queried services. This contributes to the growing work of formalising
privacy-preserving LBS schemes and improving query efficiency.
