How to make a message into a polynomial?

Question

I'm doing a project where I have to implement the NTRUEncrypt public key cryptosystem. This is the first step according to their guide in encrypting - "Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}" . I want to know how I can make my message into a polynomial. Thank you.

Answer 1

You can do it however you like. Perhaps the most straightforward way is to convert your message to a ternary representation

"Hello" -> 72, 101, 108, 108, 111 -> 02200, 10202, 11000, 11000, 11010

So I'm converting the characters to their ASCII representation and then converting those representations to their ternary representation (assuming that I'm limited to the 7-bit ASCII space I only need five ternary digits).

Then convert the ternary representation to a polynomial on {-1, 0, 1} by mapping the ternary digit 0 to 0, the ternary digit 1 to 1 and the ternary digit 2 to -1 and assuming that the digit corresponding to 3^k is the coefficient of x^k¹:

02200 -> p1(x) = 0 +    0 * x + (-1) * x^2 + (-1) * x^3 + 0 * x^4
10202 -> p2(x) = (-1) + 0 * x + (-1) * x^2 +    0 * x^3 + 1 * x^4
11000 -> p3(x) = 0    + 0 * x +    0 * x^2 +    1 * x^3 + 1 * x^4
11000 -> p4(x) = 0    + 0 * x +    0 * x^2 +    1 * x^3 + 1 * x^4
11010 -> p5(x) = 0    + 1 * x +    0 * x^2 +    1 * x^3 + 1 * x^4

and then my message is

p1(x) + x^5 * p2(x) + (x^5)^2 * p3(x) + (x^5)^3 * p4(x) + (x^5)^4 * p5(x)

so that my polynomial's coefficients are

(0, 0, -1, -1, 0, -1, 0, -1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1).

Regardless how you do it, the point is that you can represent your message as a polynomial however you like. It's just preferred that you find a bijection from your message space to the space of polynomials on {-1, 0, 1} that is easily computed and has an easily computed inverse.

¹ This is the crux of the transformation. A five-digit ternary number a4a3a2a1a0 corresponds exactly to evaluating the polynomial a4 * x^4 + a3 * x^3 + a2 * x^2 +a1 * x + a0 * x^0 at x = 3. So there is an obvious one-to-one correspondence between polynomials on {-1, 0, 1} and ternary numbers.

Answer 2

I'm also doing an implementation of this for my project, it is recommended that the message polynomial has binary coefficients (0 and 1 only) to reduce the running time of the algorithm, rather than ternary coefficients (1, 0, -1). The same technique as above (but obviously using binary coefficients) be used in this scenario.

So that 'Hello' becomes:[1001000,1100101,1101100,1101100,1101111].

How recommended is that? According to NTRU message polynomials should have binary coefficients anyways (see the advanced topics section).

Using a binary representation means that you also reduce a step in encoding (mapping 2 to -1).

Answer 3

I work for NTRU, so I'm glad to see this interest.

The IEEE standard 1363.1-2008 specifies how to implement NTRUEncrypt with the most current parameter sets. The method it specifies for binary->trinary conversion is:

Convert each three-bit quantity to two ternary coefficients as follows, and concatenate the resulting ternary quantities to obtain [the output].

{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}

To convert back:

Convert each set of two ternary coefficients to three bits as follows, and concatenate the resulting bit quantities to obtain [the output]:

{0, 0} -> {0, 0, 0}
{0, 1} -> {0, 0, 1}
{0, -1} -> {0, 1, 0}
{1, 0} -> {0, 1, 1}
{1, 1} -> {1, 0, 0}
{1, -1} -> {1, 0, 1}
{-1, 0} -> {1, 1, 0}
{-1, 1} -> {1, 1, 1}
{-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1}

Note that to encrypt a message securely you can't simply convert the message to trinary and apply raw NTRU encryption. The message needs to be pre-processed before encryption and post-processed after encryption to protect against active attackers who might modify the message in transit. The necessary processing is specified in IEEE Std 1363.1-2008, and discussed in our 2003 paper "NAEP: Provable Security in the Presence of Decryption Failures" (Available from http://www.ntru.com/cryptolab/articles.htm#2003_3, though be aware that this description is targeted at binary polynomials rather than trinary).

Hope this helps.

@Bert: at various times we've recommended binary or trinary polynomials. Trinary polynomials allow the same security with shorter keys. However, in the past we thought that binary polynomials allowed q (the big modulus) to be 256. This was attractive for 8-bit processors. We've since established that taking q = 256 reduces security unacceptably (specifically, it makes decryption failures too likely). Since we no longer have small q as a goal, we can take advantage of trinary polynomials to give smaller keys overall.