Suppose that we are working with the original version of NTRU with parameters $(N,p,q,k,d_f,d_g,d_\phi)$.

In this case we are working with the original NTRU with the digital envelope and the parameter $k$ is described below.

Suppose that we encrypt a message $m$ that is in $\frac{\mathbb{Z}[X]}{\langle X^N-1 \rangle}$.

Recall that $m$ has coeffcients between $-\frac{1}{2}(p-1)$ and $-\frac{1}{2}(p-1)$ and has degree at most $n-k-1$.

The ciphertext is then $e=p\phi \circledast h + m$.

It is said that the message expansion is equal to $\frac{n}{n-k}\log_p(q)$-to-$1$.

Can someone help me explaining why do we have this equalty? I don't quite understand what is said to be "message expansion" in this context...

Thanks in advance.


1 Answer 1


I guess you are taking this information from this document.

In Section 2.1 you can see a table with different sizes. In particular, a plaintext block (that is, an encoded message) has size $(n-k) \log_2 p$ bits, while a ciphertext has size $n \log_2 q$ bits. The explanation is simple: ciphertexts are actually polynomials of $n$ terms (since degree is $n-1$), where each coefficient can be represented with $\log_2 q$ bits, while encoded messages are polynomials of $n-k$ terms (since degree is $n-k-1$), where each coefficient can be represented with $\log_2 p$ bits.

Now, the "message expansion" (also known as "ciphertext expansion") is simply the ratio between the ciphertext size and the plaintext size. In other words, it is an indication of how much a ciphertext increases with respect to the original message. Ideally, you don't want it to expand too much for obvious reasons, although it can be shown that some expansion must exist for the encryption to be semantically secure (in the case of public-key schemes, like NTRU). In this case, it is $\frac{n \log_2 q}{(n-k) \log_2 p}$. Finally, by the properties of logarithms we have that $\frac{\log_2 q}{\log_2 p} = \log_p q$, so the final message expansion is $\frac{n}{n-k}\log_p q$.


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.