Cryptology ePrint Archive: Report 2016/1163

Using Fully Homomorphic Encryption for Statistical Analysis of Categorical, Ordinal and Numerical Data

Wen-jie Lu and Shohei Kawasaki and Jun Sakuma

Abstract: In recent years, there has been a growing trend towards outsourcing of computational tasks with the development of cloud services. The Gentry’s pioneering work of fully homomorphic encryption (FHE) and successive works have opened a new vista for secure and practical cloud computing. In this paper, we consider performing statistical analysis on encrypted data. To improve the efficiency of the computations, we take advantage of the batched computation based on the Chinese-Remainder-Theorem. We propose two building blocks that work with FHE: a novel batch greater-than primitive, and matrix primitive for encrypted matrices. With these building blocks, we construct secure procedures and protocols for different types of statistics including the histogram (count), contingency table (with cell suppression) for categorical data; k-percentile for ordinal data; and principal component analysis and linear regression for numerical data. To demonstrate the effectiveness of our methods, we ran experiments in five real datasets. For instance, we can compute a contingency table with more than 50 cells from 4000 of data in just 5 minutes, and we can train a linear regression model with more than 40k of data and dimension as high as 6 within 15 minutes. We show that the FHE is not as slow as commonly believed and it becomes feasible to perform a broad range of statistical analysis on thousands of encrypted data.

Category / Keywords: cryptographic protocols / secure outsourcing, statistics, fully homomorphic encryption.

Original Publication (with minor differences): NDSS'17
DOI:
http://dx.doi.org/10.14722/ndss.2017.23119

Date: received 19 Dec 2016

Contact author: riku at mdl cs tsukuba ac jp

Available format(s): PDF | BibTeX Citation

Version: 20161228:140542 (All versions of this report)

Short URL: ia.cr/2016/1163

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]