# Homomorphic encryption for vector addition

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?

-
How would providing "only 6 pre-computed vectors representing unit relative moves" enforce "that $\oplus$'s time complexity is just hyperlinear to" that distance? $\:$ It seems to me that providing such vectors would make $\oplus$'s time complexity either linear or slightly hyperlinear in $|a|\hspace{-0.03 in}+\hspace{-0.03 in}|b|\hspace{-0.03 in}+\hspace{-0.03 in}|c|$. $\;\;\;$ –  Ricky Demer Jan 31 '14 at 21:18
I don't see how the effort required depends on $\: \langle x,\hspace{-0.03 in}y\hspace{-0.02 in},\hspace{-0.02 in}z\rangle \;$. $\;\;\;\;$ –  Ricky Demer Jan 31 '14 at 21:55
It would seem that given encryptions of the 6 possible moves and say a starting position I could figure out all plaintext/ciphertext pairs (depending on the size of the space). Subtract the starting position from itself and you have $(0,0,0)$. Then use the 6 possible moves to enumerate other PT/CT pairs. –  mikeazo Jan 31 '14 at 23:15
@uosɐſ : $\:$ Why does your post say "that $\oplus$'s time complexity is just $\hspace{1.72 in}$ hyperlinear to the distance ||(x,y,z)−(a,b,c)||"? $\;\;\;$ –  Ricky Demer Jan 31 '14 at 23:34
@uosɐſ : $\;\;\;$ (For some reason, it's not letting me login to chat.) $\:$ I was interpreting "just hyperlinear" as you just described. $\:$ Read my "I don't see how ..." comment and your response to that comment, and then notice that ||(x,y,z)−(a,b,c)|| does depend on ⟨x,y,z⟩. $\;\;\;\;\;\;$ –  Ricky Demer Feb 1 '14 at 21:21

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).

-
Do you mean the $in your inline equations? Feels like they're typo's from your TeX, but I've left them just in case I've misunderstood. – figlesquidge Feb 3 '14 at 15:37 No worries - I'll clear out my comments in a minute – figlesquidge Feb 3 '14 at 17:36 D.W. - Thanks for the added detail. I tried to get some help understanding your response on chat, but didn't get far. What is the significance of p, q, and r? My first guess is that it is related to the bit-size of x, y, and z since Z/pZ is an integer field mod p, right? - so 2^32 if they're 32-bit (although signed is preferred). But I think that's a bad guess since you seem to anticipate that p, q, and r would be different and perhaps prime. – uosɐſ Feb 5 '14 at 22:00 @uosɐſ, as you correctly anticipated, the integer arithmetic is going to wrap around eventually: keep incrementing, and eventually you'll get back to zero. This is pretty much inevitable, especially since we're working with modular arithmetic.$p$is the number where wrap-around happens for the first component. Take$\langle 1,0,0 \rangle$and keep adding it to itself. You'll get$\langle 2,0,0 \rangle$,$\langle 3,0,0 \rangle$, etc. until$\langle p-1,0,0 \rangle$: then when you add one, it wraps around to$\langle 0,0,0 \rangle$. Similarly,$q,r$are the modulus for the 2nd/3rd component. – D.W. Feb 6 '14 at 0:24$p$could be something like$2^{32}$... but depending upon the scheme, it might also be something like a large prime number. Different schemes will be able to support different values for$p,q,r$. So, if you want us to propose a scheme, you'll need to tell us whether you have any specific requirements on what kinds of values of$p,q,r$will work for you. If there are any combinations of$p,q,r$that won't work for you, tell us that. If you absolutely must have wraparound occur at$p=q=r=2^{32}\$ for all three components, tell us that. etc. –  D.W. Feb 6 '14 at 0:26