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

Pyung KIM; Younho LEE; Hyunsoo YOON

doi:10.1587/transcom.2015EBP3359

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

Pyung KIM, Younho LEE, Hyunsoo YOON

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Communications Vol.E99-B No.5 pp.1070-1086

Publication Date: 2016/05/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.2015EBP3359

Type of Manuscript: PAPER

Category: Fundamental Theories for Communications

Cite this

Copy

Pyung KIM, Younho LEE, Hyunsoo YOON, "Sorting Method for Fully Homomorphic Encrypted Data Using the Cryptographic Single-Instruction Multiple-Data Operation" in IEICE TRANSACTIONS on Communications, vol. E99-B, no. 5, pp. 1070-1086, May 2016, doi: 10.1587/transcom.2015EBP3359.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/communications/10.1587/transcom.2015EBP3359/_p

Copy

@ARTICLE{e99-b_5_1070,
author={Pyung KIM, Younho LEE, Hyunsoo YOON, },
journal={IEICE TRANSACTIONS on Communications},
title={Sorting Method for Fully Homomorphic Encrypted Data Using the Cryptographic Single-Instruction Multiple-Data Operation},
year={2016},
volume={E99-B},
number={5},
pages={1070-1086},
abstract={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.},
keywords={},
doi={10.1587/transcom.2015EBP3359},
ISSN={1745-1345},
month={May},}

Copy

TY - JOUR
TI - Sorting Method for Fully Homomorphic Encrypted Data Using the Cryptographic Single-Instruction Multiple-Data Operation
T2 - IEICE TRANSACTIONS on Communications
SP - 1070
EP - 1086
AU - Pyung KIM
AU - Younho LEE
AU - Hyunsoo YOON
PY - 2016
DO - 10.1587/transcom.2015EBP3359
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E99-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2016
AB - 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.
ER -