About computation in ring.

[DuanYuFi]

Hi, I wonder if there is support for computation in Z2k and extension ring? I noticed that all examples (site) are about Galois Field, not ring. I tried to use ZZ_p with p=2^64, but it is so slow. Thanks.

[victorshoup]

It actually will work with composite p, so long as you don’t try to do anything that doesn’t make sense (like GCD of polynomials). If you use ZZ_p, it will use big ints, so pretty slow. For faster code, you can use zz_p….however, this restrict the modules to be 60 bits (or 62 bits with a compile flag), so you can’t use this for p=2^64. That’s an unfortunate restriction, since for p=2^64 this restriction seems unnecessary, as it was intended to make it easy to implement arithmetic mod p. It might make sense to design a new class that works explicitly with small powers of 2. When I designed these classes, I didn’t see a lot of important use cases for this setting. Could you share with me your application?

Thanks Victor

On Feb 10, 2023, at 1:59 AM, DuanYuFi @.***> wrote:

 Hi, I wonder if there is support for computation in Z2k and extension ring? I noticed that all examples (site) are about Galois Field, not ring. I tried to use ZZ_p with p=2^64, but it is so slow. Thanks.

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you are subscribed to this thread.

[DuanYuFi]

Thanks for your reply. Yeah, I'm now studying in Secure Multiparty Computation and we want to implement our protocol which needs extension ring (Z2^k[X] / f(x)). MP-SPDZ (an SMPC framework) has its implementation about Z2^k, but it didn't have polynomials and extension rings, which makes us find other ways to solve the problem.

And there's one more thing which might be helpful. Note that there are intel instructions that can do binary extension field multiplication for F_{2^64} in one instruction. I didn't find it in libntl. I think it will be a meaningful optimization for GF2E.

Thanks for your help and the wonderful library.

[victorshoup]

That's actually already in there -- and should be automatically used when available.

On Feb 10, 2023, at 7:59 AM, DuanYuFi @.***> wrote:

And there's one more thing which might be helpful. Note that there are intel instructions that can do binary extension field multiplication for F_{2^64} in one instruction. I didn't find it in libntl. I think it will be a meaningful optimization for GF2E.

[DuanYuFi]

Oh sorry, my fault. Thanks for your reply.