For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Sorting Method for Fully Homomorphic Encrypted Data Using the Cryptographic Single-Instruction Multiple-Data Operation
Pyung KIM Younho LEE Hyunsoo YOON
IEICE TRANSACTIONS on Communications
Publication Date: 2016/05/01
Online ISSN: 1745-1345
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
sorting, computation over encrypted data, fully homomorphic encryption, applied cryptography,
Full Text: PDF(5.6MB)>>
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.