Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The scenario is described as following: Let $A$ an user that is transmitting an encrypted (with its own public key $PK_A$) data vector containing its position as $p = Enc(PK_A, [x,y])$ towards a group of users $U = [u_1, u_2, \dots, u_n]$.
Is it possible that each of these users belonged to the group $U$ positioned at different distances from $A$ can compute respective the euclidian distance on it (on the encrypted data that they received I mean)?
No, not in the system as described.
One sufficient reason: in any scheme matching the standard goals of public-key encryption, including homomorphic, nothing about information encrypted with a public key can be determined from the cryptogram without the matching private key. Thus $p$, encrypted under A's public key, can't be used by others (not knowing A's private key) to determine the distance of A to another point.
The normal thing would be that A signs her position (and date/time) with her private key, encrypts the outcome using other user's public keys, and trusts them not to collude to find her location. Such scheme allows the users to determine their respective distance to A, and protects them from third parties trying to misinform them about A's position.
The non-collusion hypothesis is necessary for geometrical reasons even if the devices used to determine the distance to A are designed not to leak her location. That's because multilateration¹ allows three users B, C, D at known locations and knowing their distance to A, to determine A's position, defeating the purpose of encryption.
That's a hard limit. Fully homomorphic encryption could allow a third party to compute the encrypted distances from the locations encrypted with the same public key, without knowing the locations or distances; but getting at the result requires the private key. That's about all I can imagine towards the question's goal.
¹ Essentially, assuming A,B,C,D are on a plan, A sits at the intersection of 3 circles of centers B, C, and D, of radius their respective distances to A. Two users are often enough to narrow A's position to just two locations, and perhaps one of them is unlikely. If the angles BAC, CAD, DAB are not overly acute, the third user's info narrows to one location, and tends to make the estimation of A's location precise, with an incertitude on that only a few times the incertitude on the positions of A B C D. The technique also works on a sphere of known radius, or in three dimensions with one extra point.
