  This paper proposes a system, entitled Concealer that allows sharing
time-varying spatial data (e.g., as produced by sensors) in encrypted form to
an untrusted third-party service provider to provide location-based
applications (involving aggregation queries over selected regions over time
windows) to users. Concealer exploits carefully selected encryption techniques
to use indexes supported by database systems and combines ways to add fake
tuples in order to realize an efficient system that protects against leakage
based on output-size. Thus, the design of Concealer overcomes two limitations
of existing symmetric searchable encryption (SSE) techniques: (i) it avoids the
need of specialized data structures that limit usability/practicality of SSE in
large scale deployments, and (ii) it avoids information leakages based on the
output-size, which may leak data distributions. Experimental results validate
the efficiency of the proposed algorithms over a spatial time-series dataset
(collected from a smart space) and TPC-H datasets, each of 136 Million rows,
the size of which prior approaches have not scaled to.
