Paper 2024/1648
SIMD-style Sorting of Integer Sequence in RLWE Ciphertext
Abstract
This article discusses fully homomorphic encryption and homomorphic sorting. Homomorphic encryption is a special encryption technique that allows all kinds of operations to be performed on ciphertext, and the result is still decryptable, such that when decrypted, the result is the same as that obtained by performing the same operation on the plaintext. Homomorphic sorting is an important problem in homomorphic encryption. Currently, there has been a volume of work on homomorphic sorting. In these works, each integer in a sequence is encrypted in a separate ciphertext, there is a lack of research on sorting sequences of integers encrypted in a single ciphertext. This paper addresses the sorting problem by utilizing Single Instruction Multiple Data (SIMD) technology to provide new algorithms to improve computational efficiency. The content includes the following aspects.
For plaintexts encrypted word-wise, this paper studies sorting an integer sequence stored in one or multiple ciphertexts, and proposes a new SIMD-style homomorphic sorting algorithm. On theoretical complexity, compared with three existing sorting algorithms, namely, homomorphic sorting by polynomial computation over a finite field, by TFHE bootstrapping, or by Liu-Wang parallel bootstrapping, the new algorithm achieves a speedup of
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint.
- Contact author(s)
-
lizijing @ amss ac cn
hli @ mmrc iss ac cn
wangzhengyang22 @ mails ucas ac cn - History
- 2024-10-15: revised
- 2024-10-13: received
- See all versions
- Short URL
- https://ia.cr/2024/1648
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1648, author = {Zijing Li and Hongbo Li and Zhengyang Wang}, title = {{SIMD}-style Sorting of Integer Sequence in {RLWE} Ciphertext}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1648}, year = {2024}, url = {https://eprint.iacr.org/2024/1648} }