PASS-Encrypt: a public key cryptosystem based on partial evaluation of polynomials

Abstract

A new hard problem in number theory, based on partial evaluation of certain classes of constrained polynomials, was introduced in Hoffstein et al. (Secure user identification based on constrained polynomials, 2000) and further refined in Hoffstein et al. (Polynomial rings and efficient public key authentication, 1999; Practical signatures from the partial Fourier recovery problem, 2013), Hoffstein and Silverman (Polynomial rings and efficient public key authentication. II, 2001) to create an efficient authentication and digital signature scheme called PASS. In this paper we present a public key cryptosystem called PASS-Encrypt that is based on the same underlying hard problem. We also provide an alternative description in terms of partial knowledge of discrete Fourier transforms.

1 Introduction

We present PASS-Encrypt, a public key cryptosystem whose security is based on the difficulty of reconstructing a small polynomial from some of its values, or equivalently, on the difficulty of reconstructing a short vector from partial knowledge of its discrete Fourier transfrom. PASS-Encrypt is a PKC companion to the digital signature scheme called PASS (Polynomial Authentication and Signature Scheme) that was introduced in [11] and further refined in [7, 9]. We give theoretical descriptions of two versions of PASS-Encrypt and explain how the underlying partial DFT problem is equivalent to finding short or close vectors in certain lattices. Items that we do not discuss in this paper include (1) the use of standard methods to turn our basic scheme into a system that has both semantic and chosen-ciphertext security; (2) the possibility of creating provably secure variants of PASS-Encrypt. Thus one may view this note as proposing a candidate trapdoor one-way function, rather than describing a fully-fledged encryption scheme.

2 Some historical remarks

The mid-1990s saw a flurry of activity around the use of hard lattice problems to create public key cryptosystems and digital signature schemes that were either extremely efficient [6, 8, 9] or had desirable theoretical properties [1]. Among the former, the NTRUEncrypt PKC [8] developed by the authors and Jill Pipher was presented at the Crypto 96 rump session and published in 1998. NTRUEncrypt relies directly on SVP and CVP in certain cyclic modular lattices whose special structure accounts for its efficiency. Various signature schemes based on NTRU-type lattices have been proposed over the years, but until recently [13] they all suffered from transcript information leakage. (See also [2, 5, 17, 18] for other work on amelioration of transcript leakage in NTRU signatures.) The mid-1990s also saw the introduction by the authors and Dan Lieman [7, 9] of a digital signature scheme called PASS that was based on the difficulty of reconstructing a small polynomial from a partial list of its values. PASS, which was published in 1999, also suffered from transcript leakage, although a recent variant [12] uses rejection sampling to eliminate this problem. Shortly after PASS was originally developed, the authors realized that the PASS problem could also be used as the basis for a public key cryptosystem, and they wrote up some preliminary notes (dated January 14, 1999). However, since it was clear at that time that NTRUEncrypt would be more efficient and have smaller key and ciphertext sizes, they did not further develop PASS-Encrypt.

The past decade has seen a resurgence of interest in lattice-based cryptosystems for a variety of reasons, including their potential resistance to quantum algorithms, their use by Gentry in the construction of a fully homomorphic encryption scheme [4], and other work such as the construction of multilinear pairings [3]. In view of this activity and the recent introduction of a transcript secure PASS signature scheme [12], the authors felt that it might be of interest to publish their practical and efficient PKC based on the PASS problem, despite the fact that PASS-Encrypt remains somewhat less efficient than NTRUEncrypt, and despite the fact that we have not investigated variants of PASS-Encrypt that might admit formal proofs of security.

3 Discrete Fourier transformations and polynomial evaluation

We set the following notation, which will remain fixed throughout this paper.

$\mathbb {F}_q$ :

a finite field with $q$ elements.

$N$ :

a prime satisfying $q\equiv 1\pmod {N}$.

$p$ :

a small prime that does not divide $q$.

$w$ :

a primitive $N^{\text {th}}$ root of unity in $\mathbb {F}_q$.

$S$ :

an ordered subset of $\{0,1,2,\ldots ,N-1\}$. Let $s=\#S$.

$S'$ :

the ordered complement of $S$, i.e., $S'=\{0\le i \le N-1 : i\notin S\}$. Let $s'=\#S'$.

For $\varvec{a}\in \mathbb {F}_q^N$, the Discrete Fourier Transformation of $\varvec{a}$ is the vector $\mathcal {F}(\varvec{a})\in \mathbb {F}_q^N$ whose $k^{\text {th}}$ coordinate is

$$\begin{aligned} \mathcal {F}(\varvec{a})_k = \sum _{i=0}^{N-1} a_iw^{ik}. \end{aligned}$$

The Inverse Discrete Fourier Transform $\mathcal {F}^{-1}$ is defined by the similar formula

$$\begin{aligned} \mathcal {F}^{-1}(\varvec{a})_k = \frac{1}{N}\sum _{i=0}^{N-1} a_iw^{-ik}. \end{aligned}$$

It is easy to verify that

$$\begin{aligned} \mathcal {F}^{-1}\circ \mathcal {F}(\varvec{a})=\varvec{a}\qquad \hbox {and}\qquad \mathcal {F}\circ \mathcal {F}^{-1}(\varvec{a})=\varvec{a}. \end{aligned}$$

Thus knowledge of a vector is equivalent to knowledge of its Fourier transform, albeit subject to a certain amount of computation.

For any subset $S=\{k_1,k_2,\ldots ,k_s\}$ of indices, we let $\mathcal {F}_S(\varvec{a})$ be the corresponding subset of the coordinates of $\mathcal {F}(\varvec{a})$:

$$\begin{aligned} \mathcal {F}_S(\varvec{a}) = \bigl (\mathcal {F}(\varvec{a})_{k_1},\mathcal {F}(\varvec{a})_{k_2},\ldots ,\mathcal {F}(\varvec{a})_{k_s}\bigr ). \end{aligned}$$

We call $\mathcal {F}_S(\varvec{a})$ a Partial Fourier Transform, in the sense that it contains partial information about the full Fourier transform. Note that knowledge of a partial Fourier transform is not, in general, sufficient to determine the original vector. Indeed, if $s\ne N$, then there will be many vectors with the same $S$-partial Fourier transform.

There are two types of products that are useful. The first is simply component-by-component multiplication,

$$\begin{aligned} \varvec{a}\cdot \varvec{b}= (a_0b_0,b_1b_1,\ldots ,a_{N-1}b_{N-1}). \end{aligned}$$

The second is the convolution product $a{\otimes }b$ whose $k^{\text {th}}$ coordinate is given by the formula

$$\begin{aligned} (\varvec{a}{\otimes }\varvec{b})_k = \sum _{i=0}^{N-1} a_i b_{k-i}, \end{aligned}$$

where it is understood that $b_j=b_{j+N}$ if $j<0$.

It is a standard, and very important, fact that the Fourier transform is a homomorphism from the ring of vectors with convolution product to the ring of vectors with component multiplication. That is, it satisfies

$$\begin{aligned} \mathcal {F}(\varvec{a}+\varvec{b})=\mathcal {F}(\varvec{a})+\mathcal {F}(\varvec{b})\qquad \hbox {and}\qquad \mathcal {F}(\varvec{a}{\otimes }\varvec{b})=\mathcal {F}(\varvec{a})\cdot \mathcal {F}(\varvec{b}). \end{aligned}$$

Remark 1

Fourier transformations and vector multiplications can also be described in terms of polynomials. To do this, we identify the vector $\varvec{a}$ with the polynomial

$$\begin{aligned} a(X) = a_0+a_1X+a_2X^2+\cdots +a_{N-1}X^{N-1}. \end{aligned}$$

Then the $k^{\text {th}}$ Fourier coefficient of $\varvec{a}$ is simply the value of $a(X)$ at $X=w^k$,

$$\begin{aligned} \mathcal {F}(\varvec{a})_k=a(w^k). \end{aligned}$$

Similarly, the inverse Fourier transform is $\mathcal {F}^{-1}(\varvec{a})_k=N^{-1}a(w^{-k})$. Notice that the partial Fourier transformation $\mathcal {F}_S(\varvec{a})$ is the list of values $a(w^k)$ for the indices $k\in S$.

Continuing with the polynomial interpretation, we note that the convolution product $\varvec{a}{\otimes }\varvec{b}$ is equal to the product $a(X)b(X)$ in the quotient ring $\mathbb {F}_q[X]/(X^N-1)$. In other words, the polynomial corresponding to $\varvec{a}{\otimes }\varvec{b}$ is equal to the polynomial obtained by first multiplying $a(X)b(X)$ as polynomials and then setting $X^{N+i}=X^i$ for $0\le i<N$.

4 PASS-Encrypt: version 1

• Public parameters: The quantities $q$, $N$, $w$, $S$, and $S'$ are public cryptosystem parameters that are chosen based on the desired speed and security level.

• Key creation: Bob’s private key is a small vector $\varvec{f}\in \mathbb {F}_q^N$. Bob’s public key is the partial Fourier Transform $\mathcal {F}_S(\varvec{f})$ of $f$. For decryption purposes, Bob will probably want to compute and store (privately) the full Fourier Transform $\mathcal {F}(\varvec{f})$.

• Encryption: Alice’s plaintext¹ is a moderately small vector $\varvec{m}\in \mathbb {F}_q^N$, where the actual information transmitted is the value of $\varvec{m}$ modulo $p$. She also chooses a small random vector $\varvec{r}\in \mathbb {F}_q^N$. She computes $\mathcal {F}(\varvec{m})$ and $\mathcal {F}(\varvec{r})$. Using these values and Bob’s public key $\mathcal {F}_S(\varvec{f})$, she computes the following three quantities:

  $$\begin{aligned} \varvec{e}&=p\mathcal {F}_S(\varvec{f})\cdot \mathcal {F}_S(\varvec{r})+\mathcal {F}_S(\varvec{m}).\\ \varvec{e}'&=\mathcal {F}_{S'}(\varvec{r}).\\ \varvec{e}''&=\mathcal {F}_{S'}(\varvec{m}). \end{aligned}$$

  She transmits to Bob the ciphertext $(\varvec{e},\varvec{e}',\varvec{e}'')$. Note that since $\varvec{e}'$ and $\varvec{e}''$ are only partial Fourier Transforms of $\varvec{r}$ and $\varvec{m}$, they do not allow an attacker to directly reconstruct $\varvec{r}$ and $\varvec{m}$.

• Decryption: Bob combines his private knowledge of $\mathcal {F}_{S'}(\varvec{f})$ with the values $\varvec{e}'$ and $\varvec{e}''$ that he received from Alice to compute

  $$\begin{aligned} p\mathcal {F}_{S'}(\varvec{f})\cdot \mathcal {F}_{S'}(\varvec{r})+\mathcal {F}_{S'}(\varvec{m}). \end{aligned}$$

  Combining this with $\varvec{e}$, Bob knows the value of

  $$\begin{aligned} p\mathcal {F}(\varvec{f})\cdot \mathcal {F}(\varvec{r})+\mathcal {F}(\varvec{m}). \end{aligned}$$

  Taking the inverse Fourier transform of this quantity yields

  $$\begin{aligned} p\varvec{f}{\otimes }\varvec{r}+\varvec{m}. \end{aligned}$$

  Since the coefficients of $\varvec{f}$ and $\varvec{r}$ are small relative to $q$, this vector may be reduced modulo $p$ to yield the message $\varvec{m}$.

Table 1 illustrates the information that is public and the information that is private. An attacker knows only the four boxes marked Public, which is insufficient information to recover the message. Bob additionally knows the Private Key box, and using that information he is able to reconstruct the information that belongs in the empty box. He then knows the complete last column, i.e., he knows the complete discrete Fourier transformation of $p\varvec{f}{\otimes }\varvec{r}+\varvec{m}$, so he is able to recover $p\varvec{f}{\otimes }\varvec{r}+\varvec{m}$ itself, and then by reduction modulo $p$ he recovers $\varvec{m}$.

Table 1 The PASS-Encrypt public key cryptosystem

5 Homomorphic properties

In view of the current widespread interest in homomorphic encryption, we make some brief remarks on homomorphic properties of PASS-Encrypt. Addition works in a straightforward way. Alice computes the sums

$$\begin{aligned} (\varvec{e}_1,\varvec{e}_1',\varvec{e}_1'') + (\varvec{e}_2,\varvec{e}_2',\varvec{e}_2'') \end{aligned}$$

and returns them to Bob. Bob can then reconstruct the full Fourier transform

$$\begin{aligned}&p\mathcal {F}(\varvec{f})\cdot \mathcal {F}(\varvec{r}_1)+\mathcal {F}(\varvec{m}_1)+p\mathcal {F}(\varvec{f})\cdot \mathcal {F}(\varvec{r}_2)+\mathcal {F}(\varvec{m}_2) \\&\quad = \mathcal {F}\bigl (p\varvec{f}{\otimes }(\varvec{r}_1+\varvec{r}_2)+(\varvec{m}_1+\varvec{m}_2)\bigr ), \end{aligned}$$

and hence he can recover

$$\begin{aligned} p\varvec{f}{\otimes }(\varvec{r}_1+\varvec{r}_2)+(\varvec{m}_1+\varvec{m}_2). \end{aligned}$$

Assuming that the coefficients are not too large, i.e., have magnitude at most $q/2$, reduction modulo $p$ yields the plaintext sum $\varvec{m}_1+\varvec{m}_2$.

The situation with products is less straightforward due to the presence of cross terms. In order to recover $\varvec{m}_1{\otimes }\varvec{m}_2$ from a computation involving the encryptions of $\varvec{m}_1$ and $\varvec{m}_2$, Bob needs to know the following four quantities:

$$\begin{aligned} \varvec{e}_1\cdot \varvec{e}_2,\qquad \varvec{e}'_1\cdot \varvec{e}'_2,\qquad \varvec{e}''_1\cdot \varvec{e}''_2,\qquad \varvec{e}'_1\cdot \varvec{e}''_2 + \varvec{e}'_2\cdot \varvec{e}''_1. \end{aligned}$$

(1)

To make it clear why Bob needs the fourth quantity, we set the notation that if $\varvec{v}=\mathcal {F}_{S'}(\varvec{u})$ is the $S'$-partial DFT of the vector $\varvec{u}$, then $\mathcal {C}(\varvec{v})=\mathcal {F}_{S}(\varvec{u})$ is the complementary $S$-partial DFT of $\varvec{u}$. In particular, knowledge of both $\varvec{v}$ and $\mathcal {C}(\varvec{v})$ is enough to recover $\varvec{v}$ via the inverse DFT.

With this notation, we see that

$$\begin{aligned} \varvec{e}_1\cdot \varvec{e}_2&= \Bigl (p\mathcal {F}_S(\varvec{f})\cdot \mathcal {F}_S(\varvec{r}_1)+\mathcal {F}_S(\varvec{m}_1)\Bigr ) \cdot \Bigl (p\mathcal {F}_S(\varvec{f})\cdot \mathcal {F}_S(\varvec{r}_2)+\mathcal {F}_S(\varvec{m}_2)\Bigr ) \\&= \Bigl (p\mathcal {F}_S(\varvec{f})\cdot \mathcal {C}(\varvec{e}'_1)+\mathcal {C}(\varvec{e}''_1)\Bigr ) \cdot \Bigl (p\mathcal {F}_S(\varvec{f})\cdot \mathcal {C}(\varvec{e}'_2)+\mathcal {C}(\varvec{e}''_2)\Bigr ) \\&= p^2 \mathcal {F}_S(\varvec{f})\cdot \mathcal {F}_S(\varvec{f})\cdot \mathcal {C}(\varvec{e}'_1)\cdot \mathcal {C}(\varvec{e}'_2) \\&\qquad {} + p \mathcal {F}_S(\varvec{f})\cdot \Bigl (\mathcal {C}(\varvec{e}'_1)\cdot \mathcal {C}(\varvec{e}''_2) + \mathcal {C}(\varvec{e}'_2)\cdot \mathcal {C}(\varvec{e}''_1)\Bigr ) + \mathcal {C}(\varvec{e}''_1)\cdot \mathcal {C}(\varvec{e}''_2). \end{aligned}$$

Hence using the four quantities (1) and his knowledge of the full DFT of $\varvec{f}$, Bob can recover the full Fourier transform

$$\begin{aligned}&\Bigl (p\mathcal {F}(\varvec{f})\cdot \mathcal {F}(\varvec{r}_1)+\mathcal {F}(\varvec{m}_1)\Bigr ) \cdot \Bigl (p\mathcal {F}(\varvec{f})\cdot \mathcal {F}(\varvec{r}_2)+\mathcal {F}(\varvec{m}_2)\Bigr ) \\&\quad = \mathcal {F}\Bigl ((p\varvec{f}{\otimes }\varvec{r}_1+\varvec{m}_1){\otimes }(p\varvec{f}{\otimes }\varvec{r}_2+\varvec{m}_2)\Bigr ). \end{aligned}$$

Applying the inverse DFT gives

$$\begin{aligned} (p\varvec{f}{\otimes }\varvec{r}_1+\varvec{m}_1){\otimes }(p\varvec{f}{\otimes }\varvec{r}_2+\varvec{m}_2), \end{aligned}$$

and again assuming that the coefficients are not too large, reduction modulo $p$ gives the value of $\varvec{m}_1{\otimes }\varvec{m}_2\mod p$.

In general, to decrypt an $n$-fold product requires $n+2$ polynomial combinations of the original encrypted values. The first of these is simply $\varvec{e}_1\cdot \varvec{e}_2\cdots \varvec{e}_n$. For the others, we obtain one for each $0\le k\le n$ by computing

$$\begin{aligned} \sum _{\begin{array}{c} I\subset \{1,2,\ldots ,n\}\\ \#I=k\\ \end{array}} \prod _{i\in I} \varvec{e}_i' \cdot \prod _{i\notin I} \varvec{e}_i'' \quad \text {(the product is coordinate-wise)}. \end{aligned}$$

These values and the knowledge of $\varvec{f}$ allow Bob to recover the full Fourier transform of

$$\begin{aligned} \prod _{i=1}^n (p\varvec{f}{\otimes }\varvec{r}_i+\varvec{m}_i) \quad \text {(the product is convolution)}, \end{aligned}$$

and then reduction modulo $p$ recovers $\prod \varvec{m}_i\mod p$ if the coefficients are not too large.

6 PASS-Encrypt: version 2

At the cost of some additional computation, it is possible to improve various operating characteristics of PASS-Encrypt, including key sizes and bandwidth. The basic idea is to switch the $p$ factor from the product $\varvec{f}{\otimes }\varvec{r}$ to the plaintext $\varvec{m}$. The cryptosystem parameters and the public and private keys are the same in both versions of PASS-Encrypt, so a single key can be used.

For concreteness, we make the following choices:

• $p=3$

• $\varvec{f}$ and $\varvec{r}$ are chosen as random vectors with coordinates equal to $-1$, $0$, or $1$.

• $\varvec{m}$ is chosen with coordinates in the range $-M/2<m_i\le M/2$. An appropriate choice for $M$ is $M\approx q/6$.

• Public Parameters: As in Version 1, the quantities $q$, $N$, $w$, $S$, and $S'$ are public cryptosystem parameters as before.

• Key Creation: As in Version 1, Bob’s private key is a small vector $\varvec{f}\in \mathbb {F}_q^N$ and Bob’s public key is the partial Fourier Transform $\mathcal {F}_S(\varvec{f})$ of $f$.

• Encryption: Alice’s plaintext is a vector $\varvec{m}\in \mathbb {F}_q^N$ with coordinates $-M/2<m_i\le M/2$. She also chooses a small random vector $\varvec{r}\in \mathbb {F}_q^N$ as in Version 1. She computes $\mathcal {F}(\varvec{m})$ and $\mathcal {F}(\varvec{r})$. Using these values and Bob’s public key $\mathcal {F}_S(\varvec{f})$, she computes the following three quantities:

  $$\begin{aligned} \varvec{e}&=\mathcal {F}_S(\varvec{f})\cdot \mathcal {F}_S(\varvec{r})+p\mathcal {F}_S(\varvec{m}).\\ \varvec{e}'&=\mathcal {F}_{S'}(\varvec{r}).\\ \varvec{e}''&=\mathcal {F}_{S'}(\varvec{m}). \end{aligned}$$

  She transmits to Bob the encrypted message $(\varvec{e},\varvec{e}',\varvec{e}'')$.

• Decryption: Bob combines his private knowledge of $\mathcal {F}_{S'}(\varvec{f})$ with the values $\varvec{e}'$ and $\varvec{e}''$ that he received from Alice to compute

  $$\begin{aligned} \mathcal {F}_{S'}(\varvec{f})\cdot \mathcal {F}_{S'}(\varvec{r})+p\mathcal {F}_{S'}(\varvec{m}). \end{aligned}$$

  Combining this with $\varvec{e}$, Bob knows the value of

  $$\begin{aligned} \mathcal {F}(\varvec{f})\cdot \mathcal {F}(\varvec{r})+p\mathcal {F}(\varvec{m}). \end{aligned}$$

  Taking the inverse Fourier transform of this quantity yields

  $$\begin{aligned} \varvec{f}{\otimes }\varvec{r}+p\varvec{m}. \end{aligned}$$

  For appropriate choices of parameters, the coordinates of this vector will be in the range from $-q/2$ to $q/2$, so reduction modulo $p$ yields the value of the product $\varvec{f}{\otimes }\varvec{r}\mod p$. Since Bob knows $\varvec{f}$, he can multiply by $\varvec{f}^{-1}\mod p$ to recover $\varvec{r}\mod p$. But $\varvec{r}$ has coordinates $0$ and $\pm 1$, so its value modulo $p$ (with $p=3$) determines $\varvec{r}$ exactly. Finally, Bob has all of the information necessary to compute

  $$\begin{aligned} \frac{(\varvec{f}{\otimes }\varvec{r}+p\varvec{m}) - \varvec{f}{\otimes }\varvec{r}}{p} = \varvec{m}\end{aligned}$$

  in $\mathbb {F}_q^N$, and since the coordinates of $m$ satisfy $|m_i|\le M<q/2$, this identifies $m$ exactly.

7 Security analysis of lattice reduction attacks

In this section we reformulate the PASS-Encrypt problem as a lattice problem and briefly discuss its practical security against lattice reduction algorithms. See [12], Sect. 5.2.1] for further discussion.

7.1 Reduction of PASS-Encrypt to a lattice problem

In this section we describe how to recover a PASS-Encrypt key by searching for a small vector in a lattice. We leave for the reader the analogous reduction of the plaintext recovery problem to a closest vector problem. We also note that one may formulate the key recovery problem as a CVP, but in practice CVP is solved by converting it to an SVP, which is what we do explicitly.

Recall that the public key is the partial Fourier transfrom $\mathcal {F}_S(\varvec{f})$, or equivalently, some of the values of the polynomial $\varvec{f}$. Treating the coordinates of $\varvec{f}$ as unknowns, the attacker knows that these coordinates satisfy the following system of linear congruences modulo $q$:

$$\begin{aligned} \sum _{i=0}^{N-1} f_iw^{ik} \equiv A_k\pmod {q} \quad \hbox {for } k\in S. \end{aligned}$$

Here $w$ and the $A_k$’s are known quantities. The first step is to solve the $s$ congruences for $s$ of the $f_i$’s in terms of the others. Note that this is done over the finite field $\mathbb {F}_q$, so is elementary linear algebra. This yields:

$$\begin{aligned} f_{N-s+j} \equiv \sum _{i=0}^{N-s-1} B_{ij}f_i + C_j\pmod {q}, \quad 0\le j<s. \end{aligned}$$

(2)

Here the $B_{ij}$’s and the $C_j$’s are known quantities, and the attacker is looking for a solution where the $f_i$’s are small. To do this, he forms the lattice $L$ generated by the rows of the following $(N+1)$-by-$(N+1)$ matrix, where to ease notation, we let $M=N-s-1$:

$$\begin{aligned} \left( \begin{array}{cccc|c|cccc} 1 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad B_{00} &{}\quad B_{01} &{}\quad \cdots &{}\quad B_{0,s-1} \\ 0 &{}\quad 1 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad B_{10} &{}\quad B_{11} &{}\quad \cdots &{}\quad B_{1,s-1} \\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots &{}\quad 0 &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ 0 &{}\quad 0 &{}\quad \cdots &{}\quad 1 &{}\quad 0 &{}\quad B_{M0} &{}\quad B_{M1} &{} \quad \cdots &{}\quad B_{M,s-1} \\ \hline 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 1 &{}\quad C_0 &{}\quad C_1 &{}\quad \cdots &{}\quad C_{s-1} \\ \hline 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad q &{} \quad 0 &{}\quad \cdots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad q &{}\quad \cdots &{}\quad 0 \\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots &{}\quad 0 &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad q \\ \end{array}\right) \end{aligned}$$

(3)

The small target vector in $L$ is created by multipying the top rows of the matrix by $f_0,f_1,\ldots ,f_M$, adding them to the middle row (i.e., the row with the $C_j$’s), and then adding appropriate multiples of the bottom rows (i.e., the $q$-rows) so that the congruences (2) give the other $f_i$’s. In this way we see that the following vector is in $L$:

$$\begin{aligned} \varvec{v}= ( f_0, f_1,\ldots , f_M,1,f_{M+1},\ldots ,f_{N-1}). \end{aligned}$$

For an appropriate choice of PASS-Encrypt parameters (with $p=3$), the coordinates of the vector $\varvec{f}$ consist of an approximately equal number of 0’s, 1’s, and $-1$’s, so the length $\tau$ of the target vector is

$$\begin{aligned} \tau = {\Vert }\varvec{v}{\Vert } \approx \sqrt{2N/3}. \end{aligned}$$

The lattice $L$ has dimension $N+1$ and discriminant $q^s$, so the Gaussian heuristic [10], Sect. 6.5.3] says that the smallest expected nonzero vector in $L$ should have length approximately

$$\begin{aligned} \sigma =\sqrt{\frac{\dim L}{2\pi e}}\cdot ({\text {Disc}}L)^{1/\dim L} =\sqrt{\frac{N+1}{2\pi e}}\cdot q^{s/(N+1)}. \end{aligned}$$

Typical PASS-Encrypt parameters sets have $s\approx N/2$ with $q=2N+1$ and $N$ large, so

$$\begin{aligned} \sigma \approx N/\sqrt{\pi e }. \end{aligned}$$

This leads to a target-to-Gaussian ratio

$$\begin{aligned} \frac{\tau }{\sigma } \approx \sqrt{\frac{2\pi e}{3N}} = O\left( \frac{1}{\sqrt{\dim L}}\right) . \end{aligned}$$

Many experiments using varied implementations of lattice reduction algorithms have shown that such lattice problems tend to be exponentially hard as a function of the dimension; see for example [7–9, 12, 14].

Remark 2

The lattice generated by the rows of (3) has some resemblence to the standard NTRU lattice [8], but with an important difference. Ignoring the middle column and row, the upper-right “$B$-block” in an an NTRU lattice has a cyclic structure; each row of an NTRU $B$-block is a barrel-cyclic shift of the previous row. This means that the NTRU lattice may be viewed as a rank-2 $R$-module for the ring $R=\mathbb {Z}[X]/(X^N-1)$, or even as an ideal in a quadratic extension of $R$. But the $B$-block of the PASS lattice does not appear to have any sort of cyclic structure, and thus it is not an ideal (nor a module of low rank) for a ring of the form $\mathbb {Z}[X]/(P(X))$. However, at the cost of increasing the lattice dimension, we can search for a PASS key in a lattice that does have a cyclic structure, although it is a vanderMonde-type cyclicity, rather than the shift cyclicity of the NTRU lattice. Thus let $S=\{k_1,k_2,\ldots ,k_s\}$ and consider the row-span of the $(N+s)$-by-$(N+s)$ matrix

$$\begin{aligned} \left( \begin{array}{cccc|c|cccc} 1 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 1 &{}\quad \cdots &{}\quad 1 \\ 0 &{}\quad 1 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad w^{k_1} &{}\quad w^{k_2} &{}\quad \cdots &{}\quad w^{k_s} \\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots &{}\quad 0 &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ 0 &{}\quad 0 &{}\quad \cdots &{}\quad 1 &{}\quad 0 &{}\quad w^{(N-1)k_1} &{}\quad w^{(N-1)k_2} &{}\quad \cdots &{}\quad w^{(N-1)k_s} \\ \hline 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 1 &{}\quad -A_{k_1} &{}\quad -A_{k_2} &{}\quad \cdots &{}\quad -A_{k_s} \\ \hline 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{} \quad q &{}\quad 0 &{}\quad \cdots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad q &{}\quad \cdots &{}\quad 0 \\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots &{}\quad 0 &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad q \\ \end{array}\right) \end{aligned}$$

This lattice contains the short vector $(f_0,f_1,\ldots ,f_N,1,0,\ldots ,0)$.

Remark 3

Alexander May [15] has suggested an improved lattice attack on the NTRU cryptosystem, and these ideas were further extended in [16]. However, virtually all of the gain in May’s idea comes from the fact that the convolution modular lattices used for NTRU have a large number of target vectors that are related to one another by rotational symmetries of their coordinates. It is easily seen that PASS-Encrypt lattices do not have this property. With very high probability, there is exactly one valid target vector in the lattice $L$; that is, exactly one vector that can be used to decrypt a message. (More precisely, it is possible that a small multiple of $\varvec{v}$, say $2\varvec{v}$ or $3\varvec{v}$, will also decrypt, so what we should really say is that there is a unique one-dimensional target subspace of $L$.) Hence the ideas described in [15, 16] are not helpful for PASS-Encrypt lattices.

8 Sample parameters

We list some sample parameter sets in Table 2. For these sets, we assume that $S$ and $S'$ have approximately $N/2$ elements, and that the coordinates of the vectors $\varvec{f}$ and $\varvec{r}$ are chosen randomly uniformly from the set $\{-1,0,1\}$. Thus $\varvec{f}$ and $\varvec{r}$ are chosen from a sample space of size $3^N$, so a collision search requires $3^{N/2}$ comparisons. Even for the smallest value of $N$ in Table 2, the bit security of a collision search is $3^{N/2}=3^{359/2}\approx 2^{284.5}$.

The public key consists of roughly $\frac{1}{2}N$ numbers modulo $q$, as do each of the three components of the ciphertext. So we have roughly

$$\begin{aligned} \text {Key Size} \approx \left\lceil \frac{N}{2}\log _2(q) \right\rceil ~\text {bits}, \qquad \text {Ciphertext} \approx \left\lceil \frac{3N}{2}\log _2(q) \right\rceil ~\text {bits}, \end{aligned}$$

Table 2 Sample PASS-Encrypt parameters

The operating characteristics of PASS-Encrypt depend primarily on the speed of computing $N$-dimensional mod $q$ discrete Fourier transforms and of generating $N$-dimensional random vectors (e.g., via SHA). When done naively, we note that a DFT requires $O(N^2)$ multiplications modulo $q$, but fast Fourier transforms reduce this to $O(N\log N)$, in which case a DFT becomes comparable to component-wise addition or multiplication. (Similarly for convolution products.) Table 3 lists the number of $N$-dimensional DFTs, random vectors, convolution multiplications, and component-wise additions and multiplications required for each aspect of PASS-Encrypt.

Table 3 Operations used by PASS-Encrypt

Since actual operating speeds may vary by an order of magnitude or more depending on the implementation of the basic operations, and since neither of the authors is skilled at programming optimizations, we use [12], Sect. 6] to make rough speed comparisons. The implementation of PASS signatures in [12] uses $N\in \{577,769,1153\}$, but takes values of $q$ that are much larger than $2N+1$, which tends to make the underlying lattice problem easier, while making operations modulo $q$ more time consuming. Doing a rough interpolation/extrapolation using [12], Table 3], we obtain the estimates given in Table 4.

Table 4 Estimated PASS-Encrypt operating characteristics with comparisons to other systems

We performed experiments on PASS-Encrypt lattices with $N$ ranging from $101$ to $181$ using a standard implementation of the LLL-BKZ algorithm and fit the output to a regression line of the form

$$\begin{aligned} \log (\text {Running Time}) = a \dim (L) + b. \end{aligned}$$

The correlation coefficient was $0.979$, so the linearity of the log-running time is quite good. Extrapolating to higher dimensional lattices gives the estimated running times in Table 5. For comparison, we note that the estimated times to break RSA-1024 and RSA-2048 are, respectively, $3\times 10^{11}$ MIPS-years and $3\times 10^{28}$ MIPS-years.

Table 5 Extrapolated LLL-BKZ lattice breaking time for PASS-Encrypt