Hello, in core crypto server key, there are a bunch of operations defined for crt ciphertexts and radix ciphertexts. In the radix module, there is a comparison.rs file, and there is no equivalent file in the crt module. Does it mean you compare two crt values by changing from the crt to radix representation?
Best
It is indeed not possible to compare integers encrypted with the CRT representation.
The radix representation is the focus of the implemented operations
Do you mean it is not possible in general?
If all modulus are odd, there is a way to compare two (clear) values, but it implies to almost reconstruct the whole number.
Say n = p1p2p3 , with p1,p2,p3 odd coprime numbers.
If you want to compare A and B, given that A and B are between 0 and n, you can do it by comparing the parity of the difference between A and B, knowing their own parity.
If A is even and B is even, the difference should be even. But if you do it modulo n, since n is odd, the difference becomes odd if B is greater than A, and not if it is smaller.
Say you have 3 modulus 3, 5, 7, the parity then do something like that
r1, r2, r3 | parity
0, 0, 0 | 0
1, 1, 1 | 1
2, 2, 2 | 0
0, 3, 3 | 1
1, 4, 4 | 0
1, 0, 5 | 1
etc…
So until the number is bigger than 7 its parity is the parity of r3.
Thus to find the parity of a number N = (n1,n2,n3) which is between 0 and n, you can parse a lookup table of all remainders starting from 0 until r3 = n3, then you look at the parity of n3 (which is just done by looking at the parity of n3 immediately) then you parse the lookup table using steps of size p3 changing parity at each step (because the p_i s are odd modulus, each time you add p3, the parity of the number changes) until r2=n2. (which can be done faster by some calculations), then you can parse the table by using steps of size p2*p3 until r1 = n1.
You actually do not need to really reconstruct the whole number, even if it’s not really far from it.
There is probably no generic way to make it work, as the algorithm you share has certain properties for the moduli (which is probably one of the reasons this was not implemented).
It would likely require the use of the wopbs which is slow and has limits on how many bits it can process.