The addition and rotation operations in the code do not understand, there are basic ideas or source papers?
The idea is as follows. Using a tree-based approach, we compute the signs of the differences of the halves of a vector in order to only select the smaller values for the next level of the tree. The subtraction and selection are done in CKKS, while the sign evaluation is done in FHEW.
Here is an example. Say the vector is [4 5 3 8 1 2 6 7]. First, subtract the second half from the first and obtain [3 3 -3 1]. The corresponding signs are [0 0 1 0]. In order to complete the selector, we also need the complement of these signs, so we subtract them from [1 1 1 1], resulting in [1 1 0 1]. The selector is the complement of the signs appended to the signs: [0 0 1 0 1 1 0 1]. This selector is multiplied to the initial vector, obtaining the values that were smaller in the difference [0 0 3 0 1 2 0 7]. We then add the second half to the first, to compress the vector to half of the size: [1 2 3 7]. By design, there will be no overlap between the added values from the left and the right halves.
The next iteration starts with [1 2 3 7] and continues in the same way as above. Subtract the second half from the first, evaluate the signs, compute the complements and append them to form the selector [1 1 0 0], then multiply with the initial vector and add the second half to the first, obtaining [1 2] for the next iteration. The final iteration continues the same, and its result is a ciphertext encrypting [1], which is the minimum of the vector.
For the minimum value, I only described what is going on in the corresponding part (first half, first quarter, first eighth) of the vector, because that was sufficient. For the position of the minimum, if oneHot = true (i.e., the output should be [0 0 0 0 1 0 0 0] instead of [4]), we need to account for what is happening in the whole vector in order to find the one hot representation of the position.
In the first iteration, the selector multiplies a vector of ones and returns [0 0 1 0 1 1 0 1]. In the second iteration, the selector [1 1 0 0] is appended to itself to form the expanded selector [1 1 0 0 1 1 0 0] (of the same length as the initial vector), then multiplied with the result from the first iteration to get [0 0 0 0 1 1 0 0]. In the final iteration, the selector formed by the sign and its complement [1 0] is appended to itself until the length of the initial vector is achieved [1 0 1 0 1 0 1 0], then multiplied with the result of the second iteration. This yields [0 0 0 0 1 0 0 0], which is the desired result. If oneHot = false, the initial multiplication of the selector is with [0 1 2 3 4 5 6 7] and at the end the result is summed to obtain [4].
Thank you for your answer. It’s very clear! So the onehot condition is used to output the position of the minimum value, and the core of the algorithm is to keep iterating and finding the half of the smallest value until only one remains.