Sorting Method for Fully Homomorphic Encrypted Data Using the Cryptographic Single-Instruction Multiple-Data Operation

Pyung KIM  Younho LEE  Hyunsoo YOON  

Publication
IEICE TRANSACTIONS on Communications   Vol.E99-B   No.5   pp.1070-1086
Publication Date: 2016/05/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2015EBP3359
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
Keyword: 
sorting,  computation over encrypted data,  fully homomorphic encryption,  applied cryptography,  

Full Text: PDF(5.6MB)>>
Buy this Article




Summary: 
In this paper, we present a faster (wall-clock time) sorting method for numerical data subjected to fully homomorphic encryption (FHE). Owing to circuit-based construction and the FHE security property, most existing sorting methods cannot be applied to encrypted data without significantly compromising efficiency. The proposed algorithm utilizes the cryptographic single-instruction multiple-data (SIMD) operation, which is supported by most existing FHE algorithms, to reduce the computational overhead. We conducted a careful analysis of the number of required recryption operations, which are the computationally dominant operations in FHE. Accordingly, we verified that the proposed SIMD-based sorting algorithm completes the given task more quickly than existing sorting methods if the number of data items and (or) the maximum bit length of each data item exceed specific thresholds.