Implementations of prime fields with some 2-arity

[weikengchen]

This issue serves as a note on EMP-ZK for a prime field that is not of a Mersenne prime, but with a high two-arity (aka, p - 1 has a large k for 2^k).

This is needed in some situations:

• Integration with SPDZ using HE-based preprocessing, where the homomorphic encryption is based on ring-LWE, and the plaintext field (where QuickSilver may integrate) has some 2-arity.
• Other situations probably involving ring LWE/SIS problems.

The code in this secret gist (https://gist.github.com/weikengchen/ac6de8086f2144bd3677e2771aaf015c) is an example of a prime field:

p = 2^{62} - 2^{26} - 2^{25} + 1

So it has a high two-arity of ~25.

The code in this secret gist (https://gist.github.com/weikengchen/1d7dbe19706f1c229741933323d00a8a) is an example of a prime field:

p = 2^{62} - 2^{16} + 1

So it has a high two-arity of ~16.

The second one is about 2.5x slower than the Mersenne prime, which may improve if we batch x >= p? x - p : x with vector instructions, which appears to contribute to a large part of the overhead. These two gists did not apply a few optimizations in the original version (which may be indeed worthwhile to look into).

[wangxiao1254]

I think for large p (~64 bits), it should be easy to incorporate to the current system. The code for prime is mostly separated as the utility header you provided. There should be some no-cost way to enable changing the prime p.

[weikengchen]

And one thing that may be relevant is whether the Montgomery modular multiplication (https://en.wikipedia.org/wiki/Montgomery_modular_multiplication) would be useful here since I assume that the heaviest operation is in the offline phase where we evaluate the LPN map---which likely should involve chiefly multiplication. In which case, Montgomery modular multiplication may be able to close the gap between special prime numbers and generally chosen prime numbers.