This study focuses on efficiently finding the location of the maximum value for large-scale values encrypted by the CKKS (Cheon—Kim—Kim–Song) method. To find the maximum value,
comparison operations and
rotation operations, and
[...] Read more.
This study focuses on efficiently finding the location of the maximum value for large-scale values encrypted by the CKKS (Cheon—Kim—Kim–Song) method. To find the maximum value,
comparison operations and
rotation operations, and
additions and
multiplications are required. However, there is no known way to find a
k-approximate maximum value, i.e., a value with the same most significant
k-bits as the maximum value. In this study, when the value range of all data in each slot in the ciphertext is [0, 1], we propose a method for finding all slot positions of values whose most significant
k-bits match the maximum value. The proposed method can find all slots from the input ciphertexts where their values have the same most significant
k-bits as the maximum value by performing
comparison operations,
multiplications,
additions, and
rotation operations. Through experiments and complexity analysis, we show that the proposed method is more efficient than the existing method of finding all locations where the
k MSB is equal to the maximum value. The result of this can be applied to various privacy-preserving applications in various environments, such as IoT devices.
Full article