Homomorphic encryption for vector addition

Question

Building on the question and answer from Addition-only PHE in F# which ponders homomorphic cryptosystems to navigate, relatively, a single dimension without revealing absolute position (an encrypted counter?), I am now interested in extending this to multiple dimensions, the ability to do vector addition in HE. i.e. $\varepsilon((x, y, z)) \oplus \varepsilon((a, b, c))$.

As in the referenced question, it is desirable to me that $\oplus$'s time complexity is just hyperlinear to the distance $|| (x, y, z) - (a, b, c) ||$. One way to enforce this (but not the only way, perhaps) is to provide only 6 pre-computed $\varepsilon((a, b, c))$ ciphertexts representing unit relative moves. If this is complete, then it seems to me that the key, whether symmetric or asymmetric, can be discarded. I don't particularly like this because it has a bias in moving parallel to axes. This paragraph has been causing a lot of confusion in the comments, but I'm too dense to understand the confusion.

If all 26 precomputed "cell" moves are provided, then moving diagonally has the bias. Ideally, the time required should be proportional to the distance moved. The complication here is that the time complexity for $\varepsilon(\overrightarrow{X}) \oplus \varepsilon(\overrightarrow{A})$ likely equals $\varepsilon(\overrightarrow{A}) \oplus \varepsilon(\overrightarrow{X})$, and of course since we'd know the magnitude of $\overrightarrow{A}$ then the time of the $\oplus$ operation would indicate the magnitude of $\overrightarrow{X}$ which is bad and would already be absent from any cryptosystem. The only improvement I can think of is an FHE encoded custom $\oplus$ routine that cleverly incorporates the appropriate penalty.

The system should be deterministic - that is, there is only one ciphertext of any absolute position.

Is there an upper bound on the size of the ciphertext for, say, any 192-bit vector? I believe that ciphertexts will not necessarily be the same width as the plaintext. But then maybe that's only true for non-deterministic systems.

(... Otherwise,) if only the ciphertexts are seen, how easy is it to discover the bit width of the vector? (short of finding the periodicity which is not practical)

I assume that any $\oplus$ is blind to arithmetic overflow and just wraps around, which is desirable here.

I think the function I'm asking for is just a scrambled/hidden mapping between $\mathbb{Z}^3$ spaces. Is this an unnecessarily complicated way of going about that?

$\varepsilon((0,0,0))$ cannot be obtained from $\varepsilon(\overrightarrow{X}) \oplus (\varepsilon(\overrightarrow{A}) \otimes -1)$ or $\varepsilon(\overrightarrow{X}) \ominus \varepsilon(\overrightarrow{A})$ if $\ominus$ and $\otimes$ are not available.

Thanks!

Edited to incorporate some of the comments discussion

New approach?

What about this new Indistinguishability Obfuscation (1, 2)? Could a quine-like program, but one which takes a direction symbol as input, do the trick? Each executable contains an embedded (and now secret) "point". When the program is run, it outputs itself but with a modification of the resulting "point" instead of the exact original. The program would have to also know how to indistinguishably obfuscate itself. Are all the necessary operations bootstrappable like that? The obfuscated programs are the coordinates.

How compact could they be?

Answer 1

A very simple way to do something like this is by using the following construction:

$$E^*(\langle x,y,z \rangle) = \langle E(x), E(y), E(z) \rangle,$$

where $E$ is an additively homomorphic cryptosystem. (To avoid attacks, use three different public keys to encrypt the three components.) Now $E^*$ has your desired homomorphic property.

I don't understand what the hyperlinear business is, so I've ignored that part.

The problem with this construction is that the three components are separable. For instance, given $E^*(\langle x,y,z \rangle)$, it is possible to recover $E^*(\langle x,0,0 \rangle)$. Or, given $E^*(\langle x_1,y_1,z_1 \rangle)$ and $E^*(\langle x_2,y_2,z_2 \rangle)$, it is possible to compute (say) $E^*(\langle x_1+x_2,y_1,z_1 \rangle)$. These are values that it might not be possible to derive with just $\oplus$.

So, can we do better? That's what I'll answer next.

Can we do better?

The answer is probably, it depends. There are a bunch of situations where it is simply not possible to do better -- it's not possible to achieve what you want. To identify whether it will be possible to achieve what you want, we need to dig a bit deeper into the specific details of exactly what you want, in greater precision.

Suppose we want an encryption scheme

$$E^*: \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/r\mathbb{Z} \to R$$

that is additively homomorphic on $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/r\mathbb{Z}$. In other words,

$$E^*(\langle x_1,y_1,z_1 \rangle)\oplus E^*(\langle x_2,y_2,z_2 \rangle) = E^*(\langle x_1+x_2,y_1+y_2,z_1+z_2 \rangle),$$

and $\oplus$ is the only method we have for combining ciphertexts.

If $p,q,r$ are three different numbers that are pairwise relatively prime, it is definitely not possible to do what you want. Here's why. Given $E^*(\langle x,y,z \rangle)$ and an integer $n$, it is always possible to efficiently compute $E^*(\langle nx,ny,nz \rangle)$ using just $\oplus$ (use repeated doubling). Set $n_1=r \times (r^{-1} \bmod q)$. Then given $E^*(\langle x,y,z \rangle)$, we can compute $E^*(\langle n_1 x,y,0 \rangle)$ via the formula

$$E^*(\langle n_1 x,n_1 y,n_1 z \rangle) = E^*(\langle n_1 x,y,0 \rangle),$$

using that we know how to get the left-hand side of the formula above from $E^*(\langle x,y,z \rangle)$ and $n_1$. Next, set $n_2 = q \times (q^{-1} \bmod p) \times (n_1 \bmod p)$. Now given $E^*(\langle n_1 x,y,0 \rangle)$, we can compute $E^*(\langle x,0,0 \rangle)$ using the formula

$$E^*(\langle n_2 n_1 x,n_2 y,0 \rangle) = E^*(\langle x,0,0 \rangle).$$

So in this case, given $E^*(\langle x,y,z \rangle)$, we were able to compute $E^*(\langle x,0,0 \rangle)$ using just the operation $\oplus$. This shows that if $p,q,r$ are mutually co-prime, then it's guaranteed that the three components will be separable, no matter what we do. So, in this case you might as well use the very simple construction shown at the top of my answer.

What if $p=q=r$? This looks like one case where it might be possible to achieve your desired property. However, we have to be a bit careful. If we know ciphertexts $E^*(\langle x_1,y_2,z_3 \rangle),\dots,E^*(\langle x_k,y_k,z_k \rangle)$ where the linear span of these three vectors is all of $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}$, then we can separate the three components and we're back to something that is no better than my very simple construction at the top of the answer.

In conclusion, it's only going to be possible to achieve what you want if you pick $p,q,r$ very carefully and if you severely limit what ciphertexts are available to the eavesdropper. Moreover, the specific construction might depend on your specific choice of $p,q,r$. Did you have a strategy to deal with these challenges? You might want to edit your question to tell us about what values of $p,q,r$ you had in mind and how they'll be chosen and how they're related (mutually different, mutually co-prime, all the same, whatever).