I am currently working on homomorphic encryption with the Microsoft SEAL library and I am looking for a way to encode one fixed-point number as multiple integers (integer vector of length $k$), so that addition and multiplications are valid. First thing I do is to scale the fixed-point number to an integer and work on from there.

My Question: Given rings $(\mathbb{Z}/n\mathbb{Z}, +,\cdot)$ and $(\{\mathbb{Z}/n\mathbb{Z}\}^k,+,\cdot)$, I am looking for a ring homomorphism $ \phi: \{\mathbb{Z}/n\mathbb{Z}\} \rightarrow \{\mathbb{Z}/n\mathbb{Z}\}^k$ but I can't seem to find find a trivial one and I tried extensively. Is there one I am overlooking?

Tested Solution 1: One trick was to encode one scaled integer using the Chinese Remainder theorem, which yields $m$ isomorph rings, on which I can perform additions and multiplications and in the end decode the correct result with the extended euclidean algorithm (if I choose the moduli accordingly). I tried this out and this works already, but I am interested whether there are more solutions.

Possible Other Solutions: So I have thought about taking $s$ unscaled fixed-point numbers that I want to encode as a vector and perform a discrete fourier analysis (DFT) and sample the $r$ largest (complex) frequencies and cast them to an integer. Since DFT is linear, I should also be able to perform additions and multiplications and still obtain the correct result on decoding. However, I see some problems with noise introduction due to the truncation of the frequencies and the integer casting of the frequency amplitude.

I hope this question isn't too confusing since I am not very educated with algebra and this seems address a niche I guess only a very few of you are working on.

Thank you in advance!

  • $\begingroup$ Some definitions of ring homomorphism require you to send $1$ to $1$, in which case there is only one possibility. Otherwise, there are exactly $n^k$ homomorphisms, given by $a\mapsto a\vec{v}$ for any $\vec{v}$ in the target. $\endgroup$ – Slade Apr 13 '18 at 8:51
  • $\begingroup$ As written, a morphism $x \mapsto (x,x,\dots x)$ works. $\endgroup$ – lisyarus Apr 13 '18 at 8:53
  • 1
    $\begingroup$ I strongly suspect the question you've asked is not actually one whose answer you're interested in. And since you seem to have some underlying goal, you'll probably get better results posting a question about your actual goal, rather than your idea about how to achieve it. I.e. this seems like an XY problem $\endgroup$ – Hurkyl Apr 13 '18 at 8:56
  • $\begingroup$ Haha yes, thank you Hurkyl. So what I really want to do is encoding several fixed-point numbers $a_1,..,a_r$ into a 2d matrix so that e.g. for $k=2, r=4$ , $Enc(a_1,..,a_r) =\begin{bmatrix} a_{1,1} & a_{1,2} & a_{2,1}& a_{2,2} \\ a_{3,1} & a_{3,2} & a_{4,1}& a_{4,2} \end{bmatrix}$ so that $a_1$ is decomposed somehow (this is the question) into $a_{1,1}$ and $a_{1,2}$. The restriction is that all decomposed parts $a_{i,j}$ have to be integer and I can only perform element-wise matrix operations (addition and multiplication). Rows can be swapped or ratated as a whole. $\endgroup$ – Overholt Apr 13 '18 at 9:03

Any ring homomorphism (or even any additive group homomorphism) with domain $\mathbb{Z} / n \mathbb{Z}$ is completely determined by the image of the multiplicative unit.

Since ring homomorphisms map multiplicative units to multiplicative units, there is only one possible function to consider, and it turns out to be a ring homomorphism. This function is the "diagonal" map

$$ x \mapsto (\underbrace{x, x, \ldots, x}_{k \text{ copies}}) $$

  • $\begingroup$ Thank you, I have a question however. Why can I use the Chinese Remainder theorem? Why can I correctly operate with: $x \rightarrow (x \mod m_1, x \mod m_2,..,x \mod m_k)$? $\endgroup$ – Overholt Apr 13 '18 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.