Implementing NTRU (truncated polynomials)

[kirtsar]

I've tried to implement something in the spirit on NTRU. In this cryptosystem we are interested in the rings of the form Zq[X]/(X^N - 1).

1. The first thing that is strange to me is that it is impossible to construct Z[X] / (X^N - 1), only QQ is allowed.

2. Given Z[X] / (X^N - 1), it seems impossible to take it "modulo q", which means take any f in this ring and reduce its coefficients modulo q. Instead one have to start with Zq[X], and then take the factor ring Zq[X]/(X^N - 1)

3. Given element f of Rq = Zq[X] / (X^N - 1), it seems impossible to obtains its inverse in Rq due to the fact that q may not be prime.

For example, take

q = 16
Zq = ResidueRing(ZZ, q)
ZX, x = Zq["X"]
Rq = ResidueRing(ZX, x^5 - 1)
f1 = Rq(3x^4 + 10x^3 + 7x^2 - 1)
f2 = Rq(5x^4 + 3x^3 + 13x^2 + 8x + 14)
@show f1 * f2     # equals 1
inv(f1)           # impossible

[wbhart]

1. As we've mentioned before, we could allow residue rings with monic polynomials. That's not currently the case. Someone would have to write the code, or send us a patch. In general we would probably only be able to support the case where q is prime in your example though.

2. What does it mean to take it modulo q in this ring? This wouldn't be the same as the ring you want.

3. I don't know a way to support q not prime at present. All the standard algorithms break. Some of the operations we support in our library probably wouldn't work at all (or at least, we might not have the mathematics for it). Suggestions are welcome.

[wbhart]

Question: How would I even factor X^N - 1 in Zq[x] if q is not prime? This would be required to do many things in the case that X^N - 1 is not irreducible. It seems very unlikely we will be able to handle the ring you are interested in.

[Keno]

@kirtsar You may be interested in https://github.com/JuliaComputing/ToyFHE.jl, which has a custom implementation of negacylic rings (power of two cyclotomics) as well as supporting Nemo for more general lattices. It doesn't implement NTRU because of the recent security concerns with that scheme, but perhaps you'll find the implementation helpful.

[wbhart]

Nemo now allows constructing residue rings with monic moduli.

We have not yet implemented inverse in the indicated ring.