Return to Answer

The problem that you can run into, without a well-designed padding system, is that someone might be able to craft a ciphertext that the decryptor might be able to might decrypt properly, and might not be able to, and (here's the key point) whether he is able to will depend on the private key. Hence, the concern is that an attacker might be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and from the bits denoting the success/failures, deduce the private key.

To review how NTRU encryption works: to perform raw NTRU encryption, you select your message $M$ (as a polynomial), and a random lightweight polynomial $R$, and compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt, you compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; you then evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred), this strips off the $pRG$ term, giving us $FM \bmod p$; from that, we can recover $M$.

  However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod p$; this will give us the wrong $M$.

So, what can cause a wrap? Well, wraps will occur if a coefficient of the polynomial $RG$ is too large, that is, not considering the implicit $\bmod q$ operation, is outside the range $(-q/2, q/2)$. $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is effectively the private key (that is, knowledge of that makes it easy to recover the private key from the public key); hence by artfully selecting $R$ values, an attacker could probe $G$, and over time, recover it. You might note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

And, guidelines on how an honest encryption should select $R$ values so that decryption failures are improbable don't help; an attacker will ignore those guidelines.

  NAEP prevents this attack by making the polynomial $R$ a determanistic function of $M$ (and some random bits that are included in the message). So, after the decryptor recovers $M$ (and those random bits), we recomputes what $R$ should have been, and compares it to the $R$ that was actually used. If they're different, that also results in a decryption failure (hence an attacker cannot use a value of $R$ that is outside the guidelines).

Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the private key from the bits denoting the success/failures.

To review how raw NTRU encryption works: select a message $M$ (as a polynomial), select a random lightweight polynomial $R$ and then compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt it is required to compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; the next step is to evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred). T his strips off the $pRG$ term, giving $FM \bmod p$; from that, it is possible to recover $M$. However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod p$; this will give the wrong $M$.

So, what can cause a wrap? Well, wraps will occur if a coefficient of the polynomial $RG$ is too large. It is too large when it is outside the range $(-q/2, q/2)$ (not considering the implicit $\bmod q$ operation). $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is a value that can be used to calculate the private key from the public key. By artfully selecting $R$ values, an attacker could probe $G$ and - over time - recover it. Note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

There are guidelines on how an honest encryption should select $R$ values so that decryption failures don't leak information. An attacker will however ignore these guidelines. NAEP prevents the key recovery attack by making the polynomial $R$ a deterministic function of $M$ (and some random bits that are included in the message). So after the decryptor recovers $M$ (and those random bits) we can recompute what $R$ should have been. We can then compares it to the $R$ that was actually used. If they're different then that also results in a decryption failure. An attacker can therefore not use a value of $R$ that is outside the guidelines.

The problem that you can run into, without a well-designed padding system, is that someone might be able to craft a ciphertext that the decryptor might be able to might decrypt properly, and might not be able to, and (here's the key point) whether he is able to will depend on the private key. Hence, the concern is that an attacker might be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and from the bits denoting the success/failures, deduce the private key.

To review how NTRU encryption works: to perform raw NTRU encryption, you select your message $M$ (as a polynomial), and a random lightweight polynomial $R$, and compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt, you compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; you then evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred), this strips off the $pRG$ term, giving us $FM \bmod q$; from that, we can recover $M$.

However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod q$; this will give us the wrong $M$.

So, what can cause a wrap? Well, wraps will occur if a coefficient of the polynomial $RG$ is too large (outside the range $(-p/2, p/2)$. $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is effectively the private key (that is, knowledge of that makes it easy to recover the private key from the public key); hence by artfully selecting $R$ values, an attacker could probe $G$, and over time, recover it. You might note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

And, guidelines on how an honest encryption should select $R$ values so that decryption failures are improbable don't help; an attacker will ignore those guidelines.

NAEP prevents this attack by making the polynomial $R$ a determanistic function of $M$ (and some random bits that are included in the message). So, after the decryptor recovers $M$ (and those random bits), we recomputes what $R$ should have been, and compares it to the $R$ that was actually used. If they're different, that also results in a decryption failure (hence an attacker cannot use a value of $R$ that is outside the guidelines).

The problem that you can run into, without a well-designed padding system, is that someone might be able to craft a ciphertext that the decryptor might be able to might decrypt properly, and might not be able to, and (here's the key point) whether he is able to will depend on the private key. Hence, the concern is that an attacker might be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and from the bits denoting the success/failures, deduce the private key.

To review how NTRU encryption works: to perform raw NTRU encryption, you select your message $M$ (as a polynomial), and a random lightweight polynomial $R$, and compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt, you compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; you then evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred), this strips off the $pRG$ term, giving us $FM \bmod p$; from that, we can recover $M$.

However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod p$; this will give us the wrong $M$.

So, what can cause a wrap? Well, wraps will occur if a coefficient of the polynomial $RG$ is too large, that is, not considering the implicit $\bmod q$ operation, is outside the range $(-q/2, q/2)$. $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is effectively the private key (that is, knowledge of that makes it easy to recover the private key from the public key); hence by artfully selecting $R$ values, an attacker could probe $G$, and over time, recover it. You might note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

And, guidelines on how an honest encryption should select $R$ values so that decryption failures are improbable don't help; an attacker will ignore those guidelines.

NAEP prevents this attack by making the polynomial $R$ a determanistic function of $M$ (and some random bits that are included in the message). So, after the decryptor recovers $M$ (and those random bits), we recomputes what $R$ should have been, and compares it to the $R$ that was actually used. If they're different, that also results in a decryption failure (hence an attacker cannot use a value of $R$ that is outside the guidelines).

The problem that you can run into, without a well-designed padding system, is that someone might be able to craft a ciphertext that the decryptor might be able to might decrypt properly, and might not be able to, and (here's the key point) whether he is able to will depend on the private key. Hence, the concern is that an attacker might be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and from the bits denoting the success/failures, deduce the private key.

To review, to perform raw NTRU encryption, you select your message $M$, and a random lightweight polynomial $R$, and compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt, you compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; you then evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred), this strips off the $pRG$ term, giving us $FM \bmod q$; from that, we can recover $M$.

However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod q$; this will give us the wrong $M$.

So, what can cause a wrap? Well, wraps will occur if the a coefficient of $RG$ is too large (outside the range $(-p/2, p/2)$; $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is effectively the private key (that is, knowledge of that makes it easy to recover the private key from the public key); hence by artfully selecting $R$ values, an attacker could probe $G$, and over time, recover it.

And, guidelines on how an honest encryption should select $R$ values so that decryption failures are improbable don't help; an attacker will ignore those guidelines.

The problem that you can run into, without a well-designed padding system, is that someone might be able to craft a ciphertext that the decryptor might be able to might decrypt properly, and might not be able to, and (here's the key point) whether he is able to will depend on the private key. Hence, the concern is that an attacker might be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and from the bits denoting the success/failures, deduce the private key.

To review how NTRU encryption works: to perform raw NTRU encryption, you select your message $M$ (as a polynomial), and a random lightweight polynomial $R$, and compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt, you compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; you then evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred), this strips off the $pRG$ term, giving us $FM \bmod q$; from that, we can recover $M$.

However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod q$; this will give us the wrong $M$.

So, what can cause a wrap? Well, wraps will occur if a coefficient of the polynomial $RG$ is too large (outside the range $(-p/2, p/2)$. $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is effectively the private key (that is, knowledge of that makes it easy to recover the private key from the public key); hence by artfully selecting $R$ values, an attacker could probe $G$, and over time, recover it. You might note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

And, guidelines on how an honest encryption should select $R$ values so that decryption failures are improbable don't help; an attacker will ignore those guidelines.

NAEP prevents this attack by making the polynomial $R$ a determanistic function of $M$ (and some random bits that are included in the message). So, after the decryptor recovers $M$ (and those random bits), we recomputes what $R$ should have been, and compares it to the $R$ that was actually used. If they're different, that also results in a decryption failure (hence an attacker cannot use a value of $R$ that is outside the guidelines).