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.

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^{1}:

```
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.

^{1} This is the crux of the transformation. A five-digit ternary number `a`

_{4}`a`

_{3}`a`

_{2}`a`

_{1}`a`

_{0} corresponds exactly to evaluating the polynomial `a`

_{4} `* x^4 + a`

_{3} `* x^3 + a`

_{2} `* x^2 +a`

_{1} `* x + a`

_{0} `* x^0`

at `x = 3`

. So there is an obvious one-to-one correspondence between polynomials on `{-1, 0, 1}`

and ternary numbers.

*that*with the public key algorithm, too.

*Why do you express a five-digit ternary as a4a3a2a1a0 and not backward, from 0 to 4?*It's standard practice to give the index of the subscript (i.e., the 0, 1, 2, etc.) the same value as the value of the exponent (i.e.,

`a_j`

corresponds to the coefficient of `x^j`

). *Is it important somehow?*Only insofar as it's standard practice and it makes following along easier. You, could, if you wanted, write

`a33a52a21a104a69`

and declare that `a69`

is the coefficient of `x^0`

, etc. but you will quickly lose readers as it's much harder to follow along.*Also i do not understand why*Because we are talking about a ternary expansion. Just like the base-10 number

`x = 3`

. What does it mean?`143`

means `1 * 10^2 + 4 * 10^1 + 3 * 10^0`

, the base-3 number `12022`

means 1 * 3^4 + 2 * 3^3 + 0 * 3^2 + 2 * 3^1 + 2 * 3^0`. Note that this means that `

143` is the same as evaluating the polynomial `p(x) = 1 * x^2 + 4 * x^1 + 3 * x^0`

at `x = 10`

and `12022`

is the same as evaluating the polynomial `q(x) = 1 * x^4 + 2 * x^3 + 0 * x^2 + 2 * x^1 + 2 * x^0`

at `x = 3`

.*And when you make your message as*. No, it's because I'm assuming 7-bit ASCII, and thus I need five ternary bits to represent all of the possible 7-bit ASCII characters. Then, to separate the characters, we have multiply the polynomial corresponding to each one by successive powers of

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

- the power of `x`

is five cause message consists of 5 characters, right?`x^5`

(that's why you see `x^5`

, `(x^5)^2`

, etc.) so that none of the polynomials have any common terms. Do you see why we want that?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.