SIMD operations Ring_Element and Rq_Element

[sknc]

Hello Marcel,
How do you implement SIMD as proposed by Smart and Vercauteren: https://eprint.iacr.org/2011/133.pdf in MP-SPDZ on Ring_Elements and Rq_Elements?

[mkskeller]

MP-SPDZ implements SIMD addition and multiplication as described in the documentation: https://mp-spdz.readthedocs.io/en/latest/homomorphic-encryption.html
The bit-slicing mentioned in the paper is not implemented.

[sknc]

Hello Marcel,

I am looking at he-example.cpp. I can see the multiple slots in the plaintext but I don't see where the encoding and decoding using the Chinese Remainder Theorem is occurring. I can see something that seems to be related to it in the void init(P2Data& P2D,const Ring& Rg) method NTL-Subs.cpp but am unsure how that relates.

[mkskeller]

This happens in Plaintext_::to_poly() and Plaintext::from_poly(). For prime-modulus cleartexts, this calls Ring_Element::change_rep(), and for binary cleartexts, it calls P2Data::forward() and P2Data::backward().

[sknc]

Isn't that the method using Fast Fourier Transform to change between coefficient and evaluation representation of polynomials? How does that relate to using CRT to encode multiple polynomials into a single one?

[mkskeller]

CRT is used in Rq_Element::to_vec_bigint.

[sknc]

I understand that but I don't see what that has to do with the FHE.

[mkskeller]

Maybe I misunderstood the question. What do you mean by encoding multiple polynomials into a single one?

[sknc]

Using the Chinese remainder theorem, for integers $x \in Z_p$, $y \in Z_q$, and $z \in Z_r$, one can calculate $w \in Z_{xyz}$. One can then operate over $w$ in lieu of operating over $x$, $y$, and $z$ separately. A similar thing can be done with polynomials to my understanding.

[mkskeller]

And you're referring to the CRT mentioned in Section 2 of the above paper? I think this happens in P2Data::forward(), and the init() function you've identified computes the linear relation depending on the polynomial degrees.