Secure integer comparison with third party without homomorphic encryption
Suppose a setting similar to Yao's Millionaire Problem, but with a third party: Multiple users of a (semi-trusted) cloud platform, each in possession of one natural number in the range between 1 and 1,000,000 (for instance), want to securely determine the largest number. That is, users must only learn the number, and the platform must not learn anything beyond the ciphertext of that number. The number of users is unlimited and not fixed over time, such that at any point a new user could join the platform and contribute a new (potentially largest) number. Because users cannot be expected to stay online all the time to participate in secure computations, homomorphic encryption schemes dedicated to secure comparisons are not applicable, as the platform would not be able to access any plaintexts. That means the platform must be equipped with some other way to compare numbers securely, only involving users currently trying to upload a number.
One way to achieve this is with additively homomorphic encryption. Whereas users have access to the public and private keys, the platform only knows the public key, as is standard in homomorphic encryption schemes. Comparisons are performed whenever a user interacts with the platform: Let's say two users have uploaded an encrypted number, i.e., E(13) and E(86). Before the third user uploads a number, the platform adds the same random scalar, e.g., 24, to both numbers (via homomorphic encryption). The third user is asked to perform a comparison, i.e., of E(37) and E(110), because the platform has no access to the private key and cannot evaluate this comparison by itself. The user then decrypts the numbers, compares them, and informs the platform about the result. Every comparison is additionally verified by the subsequent user. Because each user only performs one (and verfies one) comparison between linearly offset numbers, neither the server nor the user learn the actual numbers, but the largest number can be determined.
What security implications would adding offsets to and comparing plaintexts have? Without having to rely on homomorphic encryption, users could exchange one fixed offset instead of encryption keys. In the same (unspecified) way that the platform is prevented from learning the private key, it is now prevented from learning the offset. In the example above, the first two users would upload the unencrpyted numbers 37 and 110, which the platform compares on its own, eliminating any need for users to perform comparisons. Users can stay offline, and neither them nor the platform can learn the actual numbers. Because the platform knows either way what purpose it serves, i.e., comparing natural numbers, there is no harm in revealing unencrypted (but linearly offset) numbers to it. If the only information that any user transmits to the platform is a single integer value, "breaking" the offset should be impossible, because the actual numbers would be indistinguishable from their transformed counterparts. The only risk is posed by leaking the offset, but that is similarly the case for the private key in a homomorphic encryption scheme. In my opinion, there are no relevant security implications of transmitting transformed plaintext numbers instead of using homomorphically encrypted numbers. Is there anything I'm missing?
