Skip to main content
Cryptography

Return to Question

Use the same notation for c_k in the products of interest.
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

We'll be working with polynomials with degree $<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, their product is $$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$ where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

The key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is: $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$ or more plainly: $$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are polynomials of degree $<n$ with integer coefficients $q_i$ with $0 \leq q_i < q$, and $p_i$ with $0 \leq p_i < p$, where $q$ and $p$ are predefined integers ($q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p$$ that is, if we define $G=F \cdot F_q$$C=F \cdot F_q$, its coefficients $g_i$$c_k$ must verify $g_0\bmod q=1$, and $g_i\bmod q=0$ when $1\le i<n$; and $$c_k\bmod q=\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}$$ and same for $F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

We'll be working with polynomials with degree $<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, their product is $$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$ where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

The key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is: $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$ or more plainly: $$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are polynomials of degree $<n$ with integer coefficients $q_i$ with $0 \leq q_i < q$, and $p_i$ with $0 \leq p_i < p$, where $q$ and $p$ are predefined integers ($q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p$$ that is, if we define $G=F \cdot F_q$, its coefficients $g_i$ must verify $g_0\bmod q=1$, and $g_i\bmod q=0$ when $1\le i<n$; and same for $F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

We'll be working with polynomials with degree $<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, their product is $$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$ where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

The key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is: $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$ or more plainly: $$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are polynomials of degree $<n$ with integer coefficients $q_i$ with $0 \leq q_i < q$, and $p_i$ with $0 \leq p_i < p$, where $q$ and $p$ are predefined integers ($q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p$$ that is, if we define $C=F \cdot F_q$, its coefficients $c_k$ must verify $$c_k\bmod q=\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}$$ and same for $F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

Precise defintion or the reduction modulo q
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

The keyWe'll be working with polynomials with degree $F$ is a polynomial chosen from a set of$<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, thattheir product is to say, $$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$ where each coefficient $F$$c_k$ is always of the formcalculated by³:

$$f_0\,x^0 + f_1\,x^1 + \ldots + f_{n-1}\,x^{n-1}\ \text{ where }\ f_i \in \{0, 1,-1\}.$$ $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

An example ofThe key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is:

   $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$

or or more plainly:

   $$1 + x^3 - x^4 - x^5$$

$F$ functionsfunctions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are of the same form as $F$ (polynomialspolynomials of degree at most $n-1$) except their$<n$ with integer coefficients are $p_i$$q_i$ with $0 \leq p_i < p$ or$0 \leq q_i < q$, and $q_i$$p_i$ with $0 \leq q_i < q$$0 \leq p_i < p$, where $p$$q$ and $q$$p$ are predefined integers ($p$ is prime, $q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q$$$$F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p$$ that is $$F \cdot F_q \equiv [ 1\,x^0 + 0\,x^1 + 0\,x^2 + 0\,x^3 + 0\,x^4 + 0\,x^5 + 0\,x^6 ] \pmod q$$ and same for, if we define $F \cdot F_p \equiv 1 \pmod p$

Adding and subtracting these polynomials functions normally$G=F \cdot F_q$, however multiplying these polynomials works different¹². Given two polynomialits coefficients $A$$g_i$ must verify $g_0\bmod q=1$, and $B$ of degree$g_i\bmod q=0$ when $<n$:

$$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$

where each coefficient$1\le i<n$; and same for $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.$F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

The key $F$ is a polynomial chosen from a set of polynomials of degree $<n$, that is to say, $F$ is always of the form:

$$f_0\,x^0 + f_1\,x^1 + \ldots + f_{n-1}\,x^{n-1}\ \text{ where }\ f_i \in \{0, 1,-1\}.$$

An example of $F$ (where $n=7$) is:

 $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$

or more plainly:

 $$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are of the same form as $F$ (polynomials of degree at most $n-1$) except their integer coefficients are $p_i$ with $0 \leq p_i < p$ or $q_i$ with $0 \leq q_i < q$, where $p$ and $q$ are predefined integers ($p$ is prime, $q$ is coprime with $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q$$ that is $$F \cdot F_q \equiv [ 1\,x^0 + 0\,x^1 + 0\,x^2 + 0\,x^3 + 0\,x^4 + 0\,x^5 + 0\,x^6 ] \pmod q$$ and same for $F \cdot F_p \equiv 1 \pmod p$

Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$:

$$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$

where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

We'll be working with polynomials with degree $<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, their product is $$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$ where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

The key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is:  $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$ or more plainly:  $$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are polynomials of degree $<n$ with integer coefficients $q_i$ with $0 \leq q_i < q$, and $p_i$ with $0 \leq p_i < p$, where $q$ and $p$ are predefined integers ($q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p$$ that is, if we define $G=F \cdot F_q$, its coefficients $g_i$ must verify $g_0\bmod q=1$, and $g_i\bmod q=0$ when $1\le i<n$; and same for $F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

typo
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

The key $F$ is a polynomial chosen from a set of polynomials of degree $<n$, that is to say, $F$ is always of the form:

$$f_0\,x^0 + f_1\,x^1 + \ldots + f_{n-1}\,x^{n-1}\ \text{ where }\ f_i \in \{0, 1,-1\}.$$

An example of $F$ (where $n=7$) is:

$$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$

or more plainly:

$$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are of the same form as $F$ (polynomials of degree at most $n-1$) except their integer coefficients are $p_i$ with $0 \leq p_i < p$ or $q_i$ with $0 \leq q_i < q$, where $p$ and $q$ are predefined integers ($p$ is prime, $q$ is coprime with $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q$$ that is $$F \cdot F_q \equiv [ 1\,x^0 + 0\,x^1 + 0\,x^2 + 0\,x^3 + 0\,x^4 + 0\,x^5 + 0\,x^6 ] \pmod q$$ and same for $F \cdot F_p \equiv 1 \pmod p$

Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$:

$$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$

where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n-1}a_i\,b_{(k-i\bmod n)}$$$$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

The key $F$ is a polynomial chosen from a set of polynomials of degree $<n$, that is to say, $F$ is always of the form:

$$f_0\,x^0 + f_1\,x^1 + \ldots + f_{n-1}\,x^{n-1}\ \text{ where }\ f_i \in \{0, 1,-1\}.$$

An example of $F$ (where $n=7$) is:

$$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$

or more plainly:

$$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are of the same form as $F$ (polynomials of degree at most $n-1$) except their integer coefficients are $p_i$ with $0 \leq p_i < p$ or $q_i$ with $0 \leq q_i < q$, where $p$ and $q$ are predefined integers ($p$ is prime, $q$ is coprime with $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q$$ that is $$F \cdot F_q \equiv [ 1\,x^0 + 0\,x^1 + 0\,x^2 + 0\,x^3 + 0\,x^4 + 0\,x^5 + 0\,x^6 ] \pmod q$$ and same for $F \cdot F_p \equiv 1 \pmod p$

Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$:

$$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$

where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n-1}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

The key $F$ is a polynomial chosen from a set of polynomials of degree $<n$, that is to say, $F$ is always of the form:

$$f_0\,x^0 + f_1\,x^1 + \ldots + f_{n-1}\,x^{n-1}\ \text{ where }\ f_i \in \{0, 1,-1\}.$$

An example of $F$ (where $n=7$) is:

$$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$

or more plainly:

$$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are of the same form as $F$ (polynomials of degree at most $n-1$) except their integer coefficients are $p_i$ with $0 \leq p_i < p$ or $q_i$ with $0 \leq q_i < q$, where $p$ and $q$ are predefined integers ($p$ is prime, $q$ is coprime with $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q$$ that is $$F \cdot F_q \equiv [ 1\,x^0 + 0\,x^1 + 0\,x^2 + 0\,x^3 + 0\,x^4 + 0\,x^5 + 0\,x^6 ] \pmod q$$ and same for $F \cdot F_p \equiv 1 \pmod p$

Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$:

$$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$

where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
² Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
edited body
Source Link
kelalaka
kelalaka
  • 49.5k
  • 12
  • 118
  • 205
edited body
Source Link
kelalaka
kelalaka
  • 49.5k
  • 12
  • 118
  • 205
some polish with latex eea means?
Source Link
kelalaka
kelalaka
  • 49.5k
  • 12
  • 118
  • 205
some polish with latex eea means?
Source Link
kelalaka
kelalaka
  • 49.5k
  • 12
  • 118
  • 205
some polish with latex
Source Link
kelalaka
kelalaka
  • 49.5k
  • 12
  • 118
  • 205
Source Link
Aran Smeallie
Aran Smeallie
  • 43
  • 4