Cryptology ePrint Archive: Report 2015/919

Privacy-preserving computation with trusted computing via Scramble-then-Compute

Hung Dang and Anh Dinh and Ee-Chien Chang and Beng Chin Ooi

Abstract: We consider privacy-preserving computation of big data using trusted computing primitives with limited private memory. Simply ensuring that the data remains encrypted outside the trusted computing environment is insufficient to preserve data privacy, for data movement observed during computation could leak information. While it is possible to thwart such leakage using generic solution such as ORAM [43], designing efficient privacy-preserving algorithms is challenging. Besides computation efficiency, it is critical to keep trusted code bases lean, for large ones are unwieldy to vet and verify. In this paper, we advocate a simple approach wherein many basic algorithms (e.g., sorting) can be made privacy-preserving by adding a step that securely scrambles the data before feeding it to the original algorithms. We call this approach Scramble-then-Compute (StC), and give a sufficient condition whereby existing external memory algorithms can be made privacy-preserving via StC. This approach facilitates code-reuse, and its simplicity contributes to a smaller trusted code base. It is also general, allowing algorithm designers to leverage an extensive body of known efficient algorithms for better performance. Our experiments show that StC could offer up to 4.1 speedups over known, application-specific alternatives.

Category / Keywords: privacy-preserving, outsourced database, trusted computing

Date: received 22 Sep 2015, last revised 16 Jan 2017, withdrawn 20 Feb 2017

Contact author: hungdang at comp nus edu sg

Available format(s): (-- withdrawn --)

Note: This is an updated version of the report 2015/919

Version: 20170220:094220 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]