How is the field size, p, determined?

[danxinnoble]

I'm writing a program in which it is useful to do operations modulo the size of the field, p, that SPDZ supports. I also need to be able to find primitive roots of unity in this field. 

I'm compiling with the option -p 128. I looked at the file Compiler/config.py and used the value listed under P_VALUES for 128 there (17203...). But then I did some tests (exponentiated up powers of 2 and saw when values became negative) and found out in my tests that operations were actually being done a different 128-bit prime modulus (namely 198766463529478683931867765928436695041).

How is the value of p determined? Is the same value of p always used for a given bit-length (e.g 128)?

In case you are wondering, the reason I am doing this is a want to implement fast polynomial multiplication in the field Z/(X^(2^k + 1)).

[danxinnoble]

I think I've figured out where p is generated.

There is a function generate_prime in Math/Setup.cpp that seems to generate p. It also seems that the value of p depends on some value m which is defined at the start of Setup.cpp. These m seem to be powers of 2. It seems that (p-1) will be divisible by this value m.

I am looking at a use case where it is helpful for (p-1) to be divisible by a large power of 2. Can I do this just by changing m to a larger power of 2? If I do are you aware of any problems this would cause?

[Marcel Keller]

On 26/04/18 19:36, danxinnoble wrote:
> I think I've figured out where p is generated.
>
> There is a function generate_prime in Math/Setup.cpp that seems to
> generate p. It also seems that the value of p depends on some value m
> which is defined at the start of Setup.cpp. These m seem to be powers of
> 2. It seems that (p-1) will be divisible by this value m.
>
> I am looking at a use case where it is helpful for (p-1) to be divisible
> by a large power of 2. Can I do this just by changing m to a larger
> power of 2? If I do are you aware of any problems this would cause?

Not in the context of the online phase because the only requirement
there is that p is prime. p-1 has to be divisible by m (the degree of
the polynomial defining the ciphertext ring) for the FFT to work, so a
larger power of two might work as well there.

Marcel

> On Sunday, April 22, 2018 at 9:43:54 AM UTC-4, danxinnoble wrote:
>
> I'm writing a program in which it is useful to do operations modulo
> the size of the field, p, that SPDZ supports. I also need to be able
> to find primitive roots of unity in this field.
>
> I'm compiling with the option -p 128. I looked at the file
> Compiler/config.py and used the value listed under P_VALUES for 128
> there (17203...). But then I did some tests (exponentiated up powers
> of 2 and saw when values became negative) and found out in my tests
> that operations were actually being done a different 128-bit prime
> modulus (namely 198766463529478683931867765928436695041).
>
> How is the value of p determined? Is the same value of p always used
> for a given bit-length (e.g 128)?
>
> In case you are wondering, the reason I am doing this is a want to
> implement fast polynomial multiplication in the field Z/(X^(2^k + 1)).
>

> --
> You received this message because you are subscribed to the Google
> Groups "SPDZ Discussion Group" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to spdz+uns...@googlegroups.com
> <mailto:spdz+uns...@googlegroups.com>.
> To post to this group, send email to sp...@googlegroups.com
> <mailto:sp...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/spdz.
> To view this discussion on the web, visit
> https://groups.google.com/d/msgid/spdz/ee1c5c45-087b-4c88-b047-d8e103878f13%40googlegroups.com
> <https://groups.google.com/d/msgid/spdz/ee1c5c45-087b-4c88-b047-d8e103878f13%40googlegroups.com?utm_medium=email&utm_source=footer>.
> For more options, visit https://groups.google.com/d/optout.

[danxinnoble]

Interesting. So any prime p such that m divides (p-1) should work, right?

Are there issues if p is chosen to be quite small (say 40 bits rather than 128)? Does this impact security?

Thanks
Daniel

[Nigel Smart]

Hi

If you wait a few weeks then the use of different prime sizes,
and user defined prime sizes, will be supported in a new release
of the system. However, for full-threshold adversaries you
will only be able to pick a prime size. An extension for Q2
adversaries will allow you to choose any prime you want.

More details soon....

Think of this email as a teaser to the list  ;-)

Nigel

To unsubscribe from this group and stop receiving emails from it, send an email to spdz+uns...@googlegroups.com.
To post to this group, send email to sp...@googlegroups.com.

Visit this group at https://groups.google.com/group/spdz.

To view this discussion on the web, visit https://groups.google.com/d/msgid/spdz/9306320b-ea9a-47ba-ad65-af06aa85dca4%40googlegroups.com.

[danxinnoble]

Hi

Thanks for your responses.

Marcel, you mentioned that there would be no problems in the online phase. What about if I want to do the pre-processing securely? Would tweaking the SPDZ source-code to set p to a prime of my choosing, subject to p = 1 (mod m), break anything (correctness/security) in the secure pre-processing phase?

Best
Daniel