How to encode and decode message into polynomial form on NTRU

Question

This question is based on a previously asked question. How to make a message into a polynomial on NTRU encryption?

I am tasked to implement NTRU with toy parameters such as $N=7$ or $N=11$ and I have some questions.

1. Does the message length have to be smaller than or equal to the parameter $N$? Can I do encryption on a message larger than parameter $N$ or do I have to break them up?
2. One method mentioned was to convert the message into ASCII and then ternary form and then add them up to be the input as follow:

h 01101000 X^3+X^5+X^6
e 01100101 1+X^2+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
o 01101111 1+X+X^2+X^3+X^5+X^6
w 01110111 1+X+X^2+X^4+X^5+X^6
o 01101111 1+X+X^2+X^3+X^5+X^6
r 01110010 X+X^4+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
d 01100100 X^2+X^5+X^6

However, in this case, how do I decrypt the message given that the decrypted message would be the addition of all the polynomials? Or do I have to encrypt and decrypt each letter separately?

Answer 1

NTRU operates on the ring $R = \mathbb Z[x]/(X^N -1)$. Therefore all parameters must be lie in this polynomial ring.

1.Does the message length have to be smaller than or equal to the parameter N? Can I do encryption on a message larger than parameter N or do I have to break them up?

That really depends on the encoding. The linked example suggested using binary encoding. In this case, if ASCII is used then you can encode it with degree 7 polynomials. Therefore, if your $N =7$ then you cannot encrypt more than one ASCII character. You have to divide your message character by character to encrypt, assuming that you are using ASCII characters for your messages.

Other encodings are possible like ternary $\{-1,0,1\}$, however, for simplicity keep the binary at the beginning.

2. However, in this case, how do I decrypt the message given that the decrypted message would be the addition of all the polynomials? Or do I have to encrypt and decrypt each letter separately?

You have to encrypt each of them separately. Note that the example is not ternary encoding it is the binary encoding. Check them like this;

$$ \texttt{h 01101000} = \color{red}{1}\cdot X^6 + \color{red}{1}\cdot X^5 + \color{blue}{0}\cdot x^4 + \color{red}{1}\cdot X^3 + \color{blue}{0}\cdot x^2 + \color{blue}{0}\cdot x^1 + \color{blue}{0}\cdot x^0$$

In ternary, actually, one expects to see some $-1x^i$ at least in some of the encodings if one doesn't select all of them deliberately not including the $-1$.

---

The below is a sample SageMath code for encoding a character into a polynomial. The full code running with the NTRU encrypt/decrypt is at GitHub.

Zx.<x> = ZZ[]

def encodeASCIIToPolynomial(c):
   
    C = ord(c)
    M = 0
    i = 0
    while(C > 0):
        M = M + x^i*(C %2)
        C = C//2
        i += 1
    return M
    
def decodePolynomialToASCII(D):

    x =0
    for t in D:
        x = x + t
        x = x *2
    return x

message = 'Z'
print("Message to Encrypt            ", message)
m = encodeASCIIToPolynomial(message)
print("Message encoded to Polynomial ", m)
print("Decoding back to character     ",chr(decodePolynomialToASCII(m)))