How polynomial based encryption schemes such as NTRU encode messages in to polynomials? Is there a generic conversion?
1 Answer
In NTRUEncrypt, a raw message m of octet string of length l octets is encoded through the following steps:
Padded it with a random salt of b byte and a few extra information to form the actual octet string M that is to be encrypted.
This M byte string is then converted to a binary string Mbin using octect-string-to-binary-string-primitive (OS2BSP).
In NTRUEncrypt, the message is actually a ternary polynomial, so for every 3 bits in Mbin, use a binary to ternary mapping as follows to convert it into a ternary string Mtrin.
- {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}
Finally the message polynomial m(x) is to take each element in Mtrin as the corresponding coefficient.
See section 8 for more details of conversion, and section 10.2.2 for encryption procedure. https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf