DocumentCode :
2528100
Title :
Private range query by perturbation and matrix based encryption
Author :
Kawamoto, Junpei ; Yoshikawa, Masatoshi
Author_Institution :
Grad. Sch. of Inf., Kyoto Univ., Kyoto, Japan
fYear :
2011
fDate :
26-28 Sept. 2011
Firstpage :
211
Lastpage :
216
Abstract :
In this paper, we propose a novel approach for private query; IPP (inner product predicate) method. Private query is a query processing protocol to obtain requesting tuples without exposing any information about what users request to third persons including service providers. Existing works about private query such as PIR, which ensure information theoretic safety, have severe restriction because they do not support range queries nor allow tuples having a same value in queried attributes. Our IPP method, on the other hands, focuses range queries mainly and it allows tuples having a same value in any attributes. IPP method employs a query transform by trusted clients (QT) scheme and proposes transformation algorithms which make the correlation between plain queries and transformed queries and the correlation between plain attribute values and transformed attribute values small enough. Thus, the transformed queries and attribute values have resistance to frequency analysis attacks which implies IPP method prevents attackers, who know the plain distribution of them, from computing the plain queries and attribute values from transformed values. IPP method adds perturbations to queries and attribute values and gives them a matrix based encryption to achieve the above property. We also confirm the computational cost on servers belongs to O(n) with the number of tuples n and is virtually no correlation between the distributions of transformed queries and queried attribute values and the plain distributions of them by experimental evaluations.
Keywords :
cryptography; database management systems; matrix algebra; query processing; PIR; database as a service; frequency analysis attacks; inner product predicate method; matrix based encryption; perturbation based encryption; private range query; query processing protocol; query transform; trusted clients; Correlation; Encryption; Query processing; Servers; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Digital Information Management (ICDIM), 2011 Sixth International Conference on
Conference_Location :
Melbourn, QLD
ISSN :
Pending
Print_ISBN :
978-1-4577-1538-9
Type :
conf
DOI :
10.1109/ICDIM.2011.6093317
Filename :
6093317
Link To Document :
بازگشت