Approximating Max Function in Fully Homomorphic Encryption

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, (Formula presented.) comparison operations and (Formula presented.) rotation operations, and (Formula presented.) additions and (Formula presented.) 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 (Formula presented.) comparison operations, (Formula presented.) multiplications, (Formula presented.) additions, and (Formula presented.) 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.