2
$\begingroup$

How polynomial based encryption schemes such as NTRU encode messages in to polynomials? Is there a generic conversion?

$\endgroup$
1
  • $\begingroup$ My first guess would be using a random message and deriving a symmetric key from it by hashing (e.g. using HKDF). $\endgroup$ Mar 25, 2016 at 10:14

1 Answer 1

3
$\begingroup$

In NTRUEncrypt, a raw message m of octet string of length l octets is encoded through the following steps:

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

  2. This M byte string is then converted to a binary string Mbin using octect-string-to-binary-string-primitive (OS2BSP).

  3. 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}
  4. 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.