A Locality Sensitive Hashing Filter for Encrypted Vector Databases

• Autorzy: Kawamoto J.

Identyfikatory

DOI

10.3233/FI-2015-1180

• Języki publikacji: EN

Abstrakty

EN

We introduce a filtering methodology based on locality-sensitive hashing (LSH) and whitening transformation to reduce candidate tuples between which encrypted vector databases (EVDBs) must compute similarity for query processing. The LSH hashing methodology is efficient for estimating similarities between two vectors. It hashes a vector space using randomly chosen vectors. We can filter vectors that are less similar to the querying vectors by recording which hashed space each vector belongs to. However, if vectors in EVDBs are found locally, then most vectors are in the same hashed space, so the filter will not work. Because we can treat those cases using whitening transformation to distribute the vectors broadly, our proposed filtering methodology will work effectively on any vector space. We also show that our filter reduces the server’s query processing cost.

Słowa kluczowe

EN

query processing; encrypted databases; security and privacy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 2
• Strony: 291--304
• Opis fizyczny: Bibliogr. 19 poz., rys., wykr.

Twórcy

autor

Kawamoto J.

• Graduate School of Systems and Information Engineering University of Tsukuba 1-1-1 Tennodai, Tsukuba, Japan

Bibliografia

• [1] Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order Preserving Encryption for Numeric Data, Proc. of the 23rd ACM SIGMOD International Conference on Management of Data, ACM Press, New York, NY, USA, 2004, ISBN 1581138598.
• [2] Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-Preserving Symmetric Encryption, Proc. of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer-Verlag, Cologne, Germany, 2009.
• [3] Boldyreva, A., Chenette, N., Neill, A. O.: Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions, Proc. of the 31st International Cryptology Conference, Santa Barbara, CA, USA, 2011.
• [4] Charikar,M. S.: Similarity Estimation Techniques fromRoundingAlgorithms, Proc. of the 34th Annual ACM Symposium on Theory of Computing, ACM Press, Montreal, Quebec, Canada, 2002, ISBN 1581134959.
• [5] Gionis, A., Indyk, P., Motwani, R.: Similarity Search in High Dimensions via Hashing, Proc. of the 25th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1999.
• [6] Hacigumus, H., Iyer, B., Li, C., Mehrotra, S.: Executing SQL over Encrypted Data in the Database-Service-Provider Model, Proc. of the 21st ACM SIGMOD International Conference on Management of Data, ACM Press, Madison,WI, USA, 2002, ISBN 1581134975.
• [7] Hore, B., Mehrotra, S., Tsudik, G.: A Privacy-Preserving Index for Range Queries, Proc. of the 30th International Conference on Very Large Data Bases, VLDB Endowment, Toronto, ON, Canada, 2004.
• [8] Hua, Y., Xiao, B., Veeravalli, B., Feng, D.: Locality-Sensitive Bloom Filter for Approximate Membership Query, IEEE Transactions on Computers, 61(6), June 2011, 817–830, ISSN 0018-9340.
• [9] Kawamoto, J., Yoshikawa, M.: Private Range Query by Perturbation and Matrix Based Encryption, Proc. of the Sixth IEEE International Conference on Digital Information Management, IEEE Computer Society, Melbourne, Australia, 2011, ISBN 9781457715396.
• [10] Kirsch, A., Mitzenmacher, M.: Distance-Sensitive Bloom Filters, The 18th Workshop on Algorithm Engineering and Experiments, Miami, FL, USA, 2006.
• [11] Kulis, B., Grauman, K.: Kernelized Locality-Sensitive Hashing for Scalable Image Search, Proc. of the 12th IEEE International Conference on Computer Vision, IEEE Computer Society, Kyoto, Japan, 2009, ISBN 9781424444199.
• [12] Lu, Y.: Privacy-Preserving Logarithmic-time Search on Encrypted Data in Cloud, Proc. of the 19th Annual Network & Distributed System Security Symposium, San Diego, CA, USA, 2012.
• [13] Oliveira, S. R. M., Za¨ıane, O. R.: Privacy Preserving Clustering By Data Transformation, Proc. of the 18th Brazilian Symposium on Databases, UFAM, Manaus, AM, Brazil, 2003.
• [14] Rane, S., Sun, W., Vetro, A.: Privacy-preserving approximation of L1 distance for multimedia applications, In Proc. of the 2010 IEEE International Conference on Multimedia and Expo, IEEE Computer Society, Singapore, July 2010, ISBN 978-1-4244-7491-2, ISSN 1945-7871.
• [15] Wang, H., Lakshmanan, L. V. S.: Efficient Secure Query Evaluation over EncryptedXML Databases, Proc. Of the 32nd International Conference on Very Large Data Bases, VLDB Endowment, Seoul, Korea, September 2006.
• [16] Wang, J., Wu, S., Gao, H., Li, J., Ooi, B. C.: Indexing Multi-dimensional Data in a Cloud System, Proc. of the 30th ACM SIGMOD International Conference on Management of Data, ACM Press, Indianapolis, IN, USA, 2010.
• [17] Wang, Z.-F., Dai, J., Wang, W., Shi, B.-L.: Fast Query over Encrypted Character Data in Database, Computational and Information Science, 4(4), 2005, 1027–1033.
• [18] Wong, W. K., Cheung, D. W.-L., Kao, B., Mamoulis, N.: Secure kNN Computation on Encrypted Databases Categories and Subject Descriptors, Proc. of the 35th SIGMOD International Conference on Management of Data, ACM Press, Providence, RI, USA, 2009.
• [19] Zhang, Z., Ooi, B. C., Parthasarathy, S., Tung, A. K. H.: Similarity Search on Bregman Divergence: Towards Non-Metric Indexing, Proc. of the 35th International Conference on Very Large Data Bases, VLDB Endowment, Lyon, France, 2009.