International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 24 July 2015

Hung Dang, Yun Long Chong, Francois Brun, Ee-Chien Chang
ePrint Report ePrint Report
We consider scenarios in sensor network where the sensed samples are each encrypted with a different key and streamed to a cloud storage. The large number of samples poses technical challenge in fine-grained sharing. For instance, if the data owner wants to grant a user access to a large subset of the samples, the straightforward solution of sending all corresponding keys to the user would overwhelm the data owner\'s network resources. Although existing solution such as Attribute-Based Encryption (ABE) and Key Aggregation Cryptosystem (KAC) can aggregate a number of keys into a single key of small size, each of the techniques has limitations in certain aspects, which render them impractical in our applications. In particular, ABE generally incurs large overhead in ciphertext size, while KAC, though attaining constant ciphertext size and aggregated key size, requires quadratic reconstruction time with respect to the number of keys to be reconstructed. In this paper, we made an observation that for a large class of queries, specifically the combination of range and down-sampling queries, there is a algorithmic enhancement for KAC that reduces its reconstruction time from quadratic to linear. Such improvement addresses the main hurdle in adopting KAC for large datasets. Experimental studies show that on those class of queries, the proposed algorithm outperforms the original KAC by at least $90$ times when reconstructing $2^{15}$ keys. We also give a Minimum Spanning Tree (MST)-based algorithm for general queries and a clustering algorithm to trade-off the reconstruction time with the size of aggregated key. Experimental studies show that these algorithms can reduce the reconstruction time for keys that are dense in small range.

Expand

Additional news items may be found on the IACR news page.