Reduced message expansion in NTRU

Question

In the original NTRU proposal from 1998, it says on page 16:

It may be worth mentioning, though, that there is a simple. masking technique that can be used to significantly reduce message expansion. With this approach, Alice sends a pair of polynomials $(e_1, e_2)$. The first polynomial is the encryption $e_1 =r_1 \cdot h+r_2 \mod q$, where $r_2$ is a randomly chosen polynomial with all coefficients equal to -1, 0 and 1. The second polynomial is $e_2 =r_2 \cdot h+ m' \mod q$, where $m'$ is the plaintext message in a suitable digital envelope modulo $q$.

Since Bob can decrypt $e_1$ to recover $r_2$, he is able to recover $m' \mod q$. In other words, at the cost of doubling the length of the encrypted message to $2 n \log_2 q$ bits, Alice is able to send to Bob a $n \log_2 q$ bits of information. In principle, this reduces message expansion to 2-to-1, although the use of a digital envelope will naturally increase message expansion.

Is this still possible in the current instantiation of NTRU?

Answer 1

I work for Security Innovation, which owns the NTRU algorithms. Glad to see this interest!

You can look on this approach as two separate encryptions: one public-key encryption to transport $r_2$, and one symmetric encryption using $r_2$ as the key to encrypt $m$. This makes it look much more like standard practice in asymmetric crypto, where you typically use a public key crypto algorithm to agree a key and then use a symmetric algorithm to encrypt the data.

So the question is, is using $r_2*h + m$ a good symmetric encryption scheme? And the answer is no, it isn't really. For example:

• It's not secure against chosen plaintext attacks. Consider an attacker who knows one of the messages 00000... and 11111... has been encrypted. She takes the ciphertext and multiplies by $h^{-1}$. If the result has the form of $r$, she knows the message was 00000... . If it doesn't, she knows the message was 11111... .

• It's not authenticated. An attacker who knows I'm sending the message "pay \$200" can easily change it to "pay \$999".

• It's not clear how best to encrypt multi-block messages. You can come up with ad hoc constructions such as CBC of course, but this would need to be defined.

You can address all of these problems, but at the cost of additional processing time. Probably, although the raw encryption mechanism is very fast, if you do it securely it won't be any faster than using a standard symmetric algorithm. So we would recommend just using NTRUEncrypt for key transport or for encrypting small messages, and if you have more data to encrypt, doing it with a strong symmetric algorithm.