How to make a message into a polynomial?

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.

13.10.2009 19:52:28
If you intend to rely on this implementation for security, rather than this being pedagogical in nature, you're in for a world of hurt.
retracile 13.10.2009 21:29:20
2 ОТВЕТА

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^k1:

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

6
13.10.2009 20:20:23
Good answer. Might want to point out the more common approach of generating a random symmetric key, then encrypting that with the public key algorithm, too.
Nick Johnson 13.10.2009 20:28:21
That's really helpful answer but i would like to specify few details which are not understandable to me. Why do you express a five-digit ternary as a4a3a2a1a0 and not backward, from 0 to 4? Is it important somehow? Also i do not understand why x = 3. What does it mean? And when you make your message as 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? Sorry for asking all these dumb questions but i really need to understand how the stuff works.
Andrey Chernukha 29.11.2011 05:35:23
@Andrey Chernukha: 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.
jason 29.11.2011 14:12:14
@Andrey Chernukha: Also i do not understand why x = 3. What does it mean? Because we are talking about a ternary expansion. Just like the base-10 number 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.
jason 29.11.2011 14:16:49
@Andrey Chernukha: And when you make your message as 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?. 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 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?
jason 29.11.2011 14:22:50

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.

3
8.03.2010 20:43:09