# Good Gottesman-Kitaev-Preskill codes from the NTRU cryptosystem

Jonathan Conrad<EMAIL_ADDRESS>Dahlem Center for Complex Quantum
Systems, Physics Department, Freie Universität Berlin, Arnimallee 14, 14195
Berlin, Germany  Helmholtz-Zentrum Berlin für Materialien und Energie, Hahn-
Meitner-Platz 1, 14109 Berlin, Germany  Jens Eisert  Dahlem Center for Complex
Quantum Systems, Physics Department, Freie Universität Berlin, Arnimallee 14,
14195 Berlin, Germany  Helmholtz-Zentrum Berlin für Materialien und Energie,
Hahn-Meitner-Platz 1, 14109 Berlin, Germany  Fraunhofer Heinrich Hertz
Institute, Einsteinufer 37, 10587 Berlin, Germany  Jean Pierre Seifert
Electrical Engineering and Computer Science Department, Technische Universität
Berlin, Straße des 17. Juni 135, 10587 Berlin, Germany  Fraunhofer Institute
for Secure Information Technology, Rheinstraße 75, 64295 Darmstadt, Germany

(1.3.2023)

We introduce a new class of random Gottesman-Kitaev-Preskill (GKP) codes
derived from the cryptanalysis of the so-called NTRU cryptosystem. The derived
codes are good in that they exhibit constant rate and average distance scaling
$\Delta\propto\sqrt{n}$ with high probability, where $n$ is the number of
bosonic modes, which is a distance scaling equivalent to that of a GKP code
obtained by concatenating single mode GKP codes into a qubit-quantum error
correcting code with linear distance. The derived class of NTRU-GKP codes has
the additional property that decoding for a stochastic displacement noise
model is equivalent to decrypting the NTRU cryptosystem, such that every
random instance of the code naturally comes with an efficient decoder. This
construction highlights how the GKP code bridges aspects of classical error
correction, quantum error correction as well as post-quantum cryptography. We
underscore this connection by discussing the computational hardness of
decoding GKP codes and propose, as a new application, a simple public key
quantum communication protocol with security inherited from the NTRU
cryptosystem.

##  1 Introduction

In recent years, notions of bosonic quantum-error correction with the
_Gottesman-Kitaev-Preskill_ (GKP) code [1] have seen a rapid increase of
interest both in theory and in experiment, primarily due to the perspective of
them contributing to a viable route towards large scale quantum computing
using integrated _photonic_ [2, 3] and _superconducting platforms_ [4]. Such
codes have highly attractive features for systems in which quantum information
is encoded in continuous variable degrees of freedom and are specifically
suitable to accommodate photon loss [5, 6, 7, 8]. While much research has been
dedicated to obtain effective qubits from single-mode systems that are to be
integrated into larger qubit-based networks [9, 10], this approach is arguably
only scratching the surface of the potential quantum computing with the GKP
code offers compared to the toolbox offered by the more general, lattice
theoretic perspective on this class of codes [11, 12, 13, 14].

To corroborate this claim, in this work, we construct random good GKP codes
derived from a cryptographic attack on the NTRU cryptosystem [15]. We define
and discuss a goodness property for GKP codes in the lattice theoretic
framework analogous to the notion of goodness in conventional quantum- and
classical error correcting codes as a stepping stone towards scalable codes.
We investigate the decoding problem of this class of codes and show how the
native decryption routine of the NTRU cryptosystems with access to its secret
key can serve as decoder for the corresponding GKP code.

We investigate the complexity of decoding general GKP codes and highlight how
our NTRU-GKP codes can be viewed as a trapdoor decodable quantum error
correcting code, where decoding of the associated quantum error correcting
code is expected to by computationally hard in general but becomes
significantly easier when supplemented with additional (secret) information
about the structure of the code. We consider this a first step towards
cryptographic protocols built on the decoding problem of GKP codes which we
believe can have wide application for secure quantum communication and cloud-
based quantum computing and hope that this article stimulates interest in this
new direction of research.

This article is structured as follows. In Section 2, we introduce basic
principles of the GKP code, describe relevant aspects of the general decoding
problem for the GKP code and define goodness of a GKP code family. In Section
3, we discuss a selection of notable examples of GKP codes and summarize their
properties. The NTRU cryptosystem and GKP codes built on this are discussed in
Section 4 where we provide evidence that they form a family of good randomized
GKP codes. We discuss the decoding problem for the NTRU-GKP codes in Section 5
and discuss a quantum _public key cryptosystem_ (PKC) designed around the
NTRU-GKP codes. Finally, we conclude and provide outlook in Section 6.

##  2 The GKP code

We build our framework on our recent exposition [12] which we refer to for an
in-depth discussion; see also the original work [1] as well as references [11,
16, 13, 14]. The _GKP code_ [1] is a _stabilizer code_ acting on the Hilbert
space of $n$ bosonic modes, where stabilizers are given by displacement
operators

$\displaystyle
D\left(\bm{\xi}\right)=\exp\left\\{-i\sqrt{2\pi}\bm{\xi}^{T}J\bm{\hat{x}}\right\\},$
(1)

where

$\displaystyle J_{2n}=\begin{pmatrix}0&1\\\ -1&0\end{pmatrix}\otimes
I_{n}=\begin{pmatrix}0&I_{n}\\\ -I_{n}&0\end{pmatrix}$ (2)

is the symplectic form, $\bm{\xi}\in\mathbb{R}^{2n}$, and
$\bm{\hat{x}}=\left(\hat{q}_{1}\hat{q}_{2}\dots\hat{p}_{n-1}\hat{p}_{n}\right)^{T}$
is the generalized quadrature operator. Its stabilizer group is specified by
fixing $2n$ linearly independent vectors $\bm{\xi}_{i},\,i=1,\dots,2n$,

$\mathcal{S}=\big{\langle}D\left(\bm{\xi}_{1}\right)\ldots
D\left(\bm{\xi}_{2n}\right)\big{\rangle}=\left\\{e^{i\phi_{M}\left(\bm{\xi}\right)}D\left(\bm{\xi}\right),\;\bm{\xi}\in\mathcal{L}\right\\},$
(3)

where $M=\left(\bm{\xi}_{1}\ldots\bm{\xi}_{2n}\right)^{T}$ is a generator for
the lattice $\mathcal{L}=\mathbb{Z}^{2n}M$ 111For clarity of presentation, we
sometimes assume row- vs. column vector conventions to be clear from context.
and we have

$\phi_{M}\left(\bm{\xi}\right)=\pi\bm{a}^{T}A_{\leavevmode\hbox to4.5pt{\vbox
to4.5pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{} {}{} {}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{4.09703pt}{0.0pt}\pgfsys@lineto{0.0pt}{4.09703pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\bm{a},\;\bm{a}^{T}=\bm{\xi}^{T}M^{-1},$
(4)

to denote the phase-sector when we have chosen $M$ to be the basis for which
each associated displacement operator is fixed to eigenvalue $+1$ by eq. (3).
$A=MJM^{T}$ denotes the symplectic Gram matrix and $A_{\leavevmode\hbox
to4.5pt{\vbox to4.5pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{} {}{} {}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{4.09703pt}{0.0pt}\pgfsys@lineto{0.0pt}{4.09703pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ its left lower
triangle.

While the stabilizer group $\mathcal{S}\sim\mathcal{L}$ is isomorphic to the
lattice $\mathcal{L}$, its centralizer within the displacements
$\mathcal{C}\left(\mathcal{S}\right)\sim\mathcal{L}^{\perp}$ – i.e. the set of
displacement operators that commute with every element in $\mathcal{S}$ – is
isomorphic to its symplectic dual lattice
$\mathcal{L}^{\perp}:=\left\\{\bm{x}\in\mathbb{R}^{2n},\,\bm{x}^{T}J\bm{\xi}\in\mathbb{Z}\,\forall\bm{x}\in\mathcal{L}\right\\}$.
$\mathcal{S}$ is Abelian iff
$\mathcal{S}\subseteq\mathcal{C}\left(\mathcal{S}\right)$ which is equivalent
to $\mathcal{L}\subseteq\mathcal{L}^{\perp}$ and $A$ being integer. Compactly,
GKP codes are represented by weakly symplectically self-dual lattices
$\mathcal{L}\subseteq\mathcal{L}^{\perp}$ where the elements in the symplectic
dual quotient $\mathcal{L}^{\perp}/\mathcal{L}$ label the group of logical
Pauli-operations of the code encoding $D$ dimensions, which has size
$|\det\left(A\right)|=D^{2}$. When we encode collections of qubits,
$k=\log_{2}\left(D\right)=\log_{2}\left(|\det\left(M\right)|\right)=\log_{2}\left(|\det\left(\mathcal{L}\right)|\right)$
denotes the number of encoded logical qubits, which grows logarithmically with
the determinant of the stabilizer lattice.

#### Code distance.

The (Euclidean) code _distance_ of the GKP code is defined as
$\Delta=\min_{\bm{x}\in\mathcal{L}^{\perp}\setminus\mathcal{L}}\|x\|$, the
length of the shortest vector in $\mathcal{L}^{\perp}$ not in $\mathcal{L}$.
The distance as defined here is a meaningful indicator for the code
performance in a stochastic displacement error model if the probability that a
certain displacement is realized scales inversely with its length.

The distance is also the smallest power of $q$ in the complex polynomial

$Q_{\mathcal{L}}\left(z\right)=\Theta_{\mathcal{L}^{\perp}}\left(z\right)-\Theta_{\mathcal{L}}\left(z\right)=N_{\Delta^{2}}q^{\Delta^{2}}+O\left(q^{\Delta^{2}}\right),$
(5)

where $q=e^{i\pi z}$,
$z\in\mathcal{H}=\\{z\in\mathbb{C},\,\operatorname{Im}z>0\\}$ and

$\Theta_{\mathcal{L}}\left(z\right)=\sum_{\bm{x}\in\mathcal{L}}q^{\|\bm{x}\|^{2}}$
(6)

is the _theta function_ of the lattice $\mathcal{L}$ and $N_{\Delta^{2}}$ in
$Q_{\mathcal{L}}\left(z\right)$ counts the number of lattice points in
$\mathcal{L}^{\perp}\setminus\mathcal{L}$ of squared length $\Delta^{2}$. It
is expected that the relative scaling of $N_{\Delta^{2}}$ with $\Delta^{2}$
significantly impacts the existence and scale of the threshold of a GKP code
family and is responsible for the entropic contribution to the decoding
problem [9, 17]. We comment on this further in Appendix A. The theta function
and distance are by construction symmetric under orthogonal transformations
$O\in\mathcal{O}\left(2n\right)$ of the lattice $\mathcal{L}\mapsto
O\mathcal{L}$, while $N_{\Delta^{2}}$ scales with the number of orthogonal
automorphisms of the lattice.

#### Decoding GKP codes via the closest vector problem.

Upon measuring the stabilizers on displacement error $D\left(\bm{e}\right)$
and obtaining the syndromes $\bm{s}=MJ\bm{e}\mod 1$, one strategy is to
correct back to the code space by applying a displacement in phase space with
$\bm{\eta}=\left(MJ\right)^{-1}\bm{s}$. Since the choice of the generator $M$
is ambiguous, it is generally necessary to append this initial correction by a
logical post-correction to minimize the probabilty of imposing a logical
error. Algorithms finding the correction that minimizes logical errors given
the syndromes are called _decoders_ in this context. Assuming a Gaussian
displacement error model with variance $\overline{\sigma}^{2}$ 222We use the
overline to denote the rescaled variance that for shifts implemented by the
non-standard choice of displacement operators in eq. (1). The physical
variance $\sigma^{2}$ is related to it by
$\sigma^{2}=2\pi\overline{\sigma}^{2}$., one derives the optimal post-
correction [12] to be applied after an initial correction $\bm{\eta}$ to be
given by _maximum likelihood decoding_ (MLD)

$\overline{\bm{\xi}}^{\perp}=\operatorname*{arg\,max}_{\bm{\xi}^{\perp}\in\mathcal{L}^{\perp}/\mathcal{L}}\Theta_{\bm{\eta}+\bm{\xi}^{\perp}+\mathcal{L}}\left(\frac{i}{2\pi\overline{\sigma}^{2}}\right).$
(7)

For small error rates $\overline{\sigma}\rightarrow 0$, the most likely coset
as computed in MLD is given by the most likely individual error consistent
with the syndrome. We refer to decoding based on the most likely individual
error consistent with the syndrome as minimum energy decoding (MED) [9], to
which the solution is presented by the _closest vector problem_ (CVP),
$\overline{\bm{\xi}}^{\perp}=\mathtt{CVP}\left(\bm{\eta},\,\mathcal{L}^{\perp}\right)$
(see ref. [12]), that is, in this limit MLD reduces to CVP.

#### Bounded distance decoding (BDD).

By nature of the Gaussian error model, it is unlikely to sample an error
larger than $\|\bm{e}\|>\sqrt{2n\overline{\sigma}^{2}}$ [16, 11]. Hence, it is
reasonable to restrict the decoding problem to bounded-distance-decoding
($\mathtt{BDD}_{\epsilon}\left(\bm{\eta},\mathcal{L}^{\perp}\right)$), which
is CVP with an additional promise that
$\text{dist}\left(\bm{\eta},\mathcal{L}^{\perp}\right)\leq\epsilon$. Given
that typical Gaussian errors will be overwhelmingly of length
$\|\bm{e}\|\leq\sqrt{2n\overline{\sigma}^{2}}$ we expect to decode
successfully by solving
$\mathtt{BDD}_{\epsilon}\left(\bm{\eta},\mathcal{L}^{\perp}\right)$ with
$\epsilon=\sqrt{2n\overline{\sigma}^{2}}$. Provided a lattice basis $M$ and
its Gram-Schmidt orthogonalization
$\tilde{M}=\left(\bm{\tilde{\xi}}_{1},\ldots,\bm{\tilde{\xi}}_{2n}\right)^{T}$
it is known that Babai’s nearest plane algorithm solves BDD when
$\epsilon<\min_{i}\|\bm{\tilde{\xi}}_{i}\|/2=:\|\tilde{M}\|/2$ [18, 19], that
is when we are in possession of a lattice basis such that its Gram-Schmidt
reduced vectors are sufficiently long
$\|\tilde{M}\|\geq\sqrt{8n\overline{\sigma}^{2}}$.

function $\mathtt{NearestPlane}$($B,\bm{t}$)

if $len\left(B\right)==0$ then

return $0^{len\left(\bm{t}\right)}$

else

set $B^{*}=\mathtt{GramSchmidt}\left(B\right)$

set $c=\lfloor\bm{t}^{T}B^{*}_{-1}/\|B^{*}_{-1}\|^{2}\rceil$

return $cB_{-1}+\mathtt{NearestPlane}\left(B_{:-1},\bm{t}-cB_{-1}\right)$

end if

end function

Figure 1: Babai’s nearest plane algorithm [18].

When considering code families with growing dimension $2n$, errors up to the
typical length $\sqrt{2n\overline{\sigma}^{2}}$ are correctible via CVP
decoding only if $\Delta=O\left(\sqrt{n}\right)$. The scaling
$\Delta\propto\sqrt{n}$ is the distance scaling of a GKP code obtained by
concatenating fixed single-mode GKP codes with a qubit quantum error
correcting code with linear distance $d\propto n$. Such scaling is predicted
to exist by the quantum Gilbert-Varshamov bound [20, 21] and explicit or
randomized constructions exhibiting such scaling have been investigated in the
literature, see e.g. ref. [22, 23, 24, 25] and references therein. We define
the analogous goodness property for families of GKP codes.

######  Definition 1 (Good GKP codes).

A GKP code family $\mathcal{L}_{n}\subset\mathbb{R}^{2n}$ parametrized by
lattice dimension $2n$ with asymptotically non-vanishing rate

$\lim_{n\rightarrow\infty}\log\det\left(\mathcal{L}_{n}\right)/n>0$ (8)

and distance scaling

$\Delta^{2}=O\left(n\right)$ (9)

is good.

The existence of such a family of good GKP codes has been established by
Harrington and Preskill in refs. [16, 11]. Their proof, based on the existence
of good GKP codes obtained from re-scaling symplectically self-dual lattices
with shortest vector length $\lambda_{1}\left(\mathcal{L}\right)\geq
O\left(\sqrt{n}\right)$, whose existence had been shown by Buser and Sarnak
[26], however, is non-constructive. In the following, we will review this
construction of GKP codes, which we have called scaled GKP codes in ref. [12],
list some notable examples and show how the NTRU scheme [15] yields a
randomized construction of good GKP codes.

##  3 Constructions of GKP codes

#### Scaled GKP codes

Central to the construction of GKP codes are the class of scaled GKP codes,
first introduced and analysed in refs. [1, 11], where a GKP code is obtained
by scaling a symplectically self-dual lattice (which we will refer to as
symplectic lattice) by a factor $\sqrt{\lambda},\,\lambda\in\mathbb{N}$. Let
$\mathcal{L}_{0}=\mathcal{L}\left(M_{0}\right)$ be such a $2n-$dimensional
lattice, where we choose $M_{0}$ as the symplectic basis [27], i.e., $M_{0}$
is such that

$A_{0}=M_{0}JM_{0}^{T}=J.$ (10)

Clearly, $A_{0}$ is integer. Hence the scaled lattice
$M=\sqrt{\lambda}M_{0},\,\lambda\in\mathbb{N}$, also retains a symplectically
integral Gram matrix

$A=MJM^{T}=\lambda J.$ (11)

Such lattices are sometimes also called q-symplectic [28] with $q=\lambda$.
The total encoded dimension and distance are

$\displaystyle D$ $\displaystyle=\sqrt{|\det\left(A\right)|}=\lambda^{n},$
(12) $\displaystyle\Delta$
$\displaystyle=\lambda^{-\frac{1}{2}}\lambda_{1}\left(\mathcal{L}_{0}\right),$
(13)

where $\lambda_{1}\left(\mathcal{L}_{0}\right)$ is the length of the shortest
vector in the symplectic lattice $\mathcal{L}_{0}$. The sympletic dual lattice
is generated by $M^{\perp}=\lambda^{-\frac{1}{2}}M_{0}$. If $M_{0}$ is stated
in the symplectic basis one can immediately read off pairs of vectors with
_symplectic inner product_

$\left(\bm{\xi}^{\perp}_{i}\right)^{T}J\bm{\xi}^{\perp}_{i+n}=\frac{1}{\lambda};\;i=1,\dots,n$
(14)

and symplectic inner product $0$ with any other row in $M_{0}$. The
corresponding displacement operators anti-commute up to phase
$\omega_{\lambda}=e^{i\frac{2\pi}{\lambda}}$ and commute with each
displacement associated to every other row of $M^{\perp}$, such that they form
the logical generalized Pauli group

$\overline{X}_{i}=D\left(\bm{\xi}^{\perp}_{i}\right),\,\overline{Z}_{i}=D\left(\bm{\xi}^{\perp}_{n+i}\right);\hskip
8.5359pt\overline{X}_{i}^{\lambda},\overline{Z}_{i}^{\lambda}\in\mathcal{S}.$
(15)

Some examples of symplectically self-dual lattices are well known in the
literature and also have been re-derived by exhaustive numerical search in
ref. [11], which we list in fig. 2 along with other symplectically integral
lattices that produce notable GKP codes. The smallest GKP lattices in that
table include

  * •

The $\mathbb{Z}^{2}$ lattice with basis

$M_{\mathbb{Z}^{2}}=I_{2}.$ (16)

This is also the symplectic basis [27] for $\mathbb{Z}^{2}$, i.e., it is such
that $M_{\mathbb{Z}^{2}}JM_{\mathbb{Z}^{2}}^{T}=J$. We refer to the scaling of
this lattice or its $N$-fold direct sum by the factor
$\sqrt{\lambda}=\sqrt{2}$ as the square GKP code

$\mathcal{L}_{N\square}=\sqrt{2}\mathbb{Z}^{2N}.$ (17)

It has already been noticed in ref. [1] that all Clifford operation for this
code can be performed by means of symplectic operations. Furthermore, ref.
[29] noticed that performing stabilizer measurements and corrective shifts on
the vaccum produces the logical $\ket{H+}$ magic state vector. This is due to
the fact that $J_{2}$ is a symplectic orthogonal automorphism (the logical
Hadamard) of the lattice. This is by far the most simple and most popular GKP
code discussed in the literature, which also is also owed to the fact the
lattice is orthogonal such that decoding via CVP becomes a simple one-
dimensional rounding protocol [18].

  * •

The hexagonal $A_{2}$ lattice with symplectic basis

$M_{A_{2}}=\frac{1}{\sqrt[4]{12}}\begin{pmatrix}2&0\\\
1&\sqrt{3}\end{pmatrix}.$ (18)

This lattice is one of the root lattices in $2$ dimensions and is known to
yield the densest sphere packing there, capable of tightly packing spheres of
radius $\lambda_{1}\left(A_{2}\right)/2=\frac{1}{\sqrt[4]{12}}\approx
0.537\ldots$. The scaling to a qubit-GKP code $\mathcal{L}=\sqrt{2}A_{2}$ has
distance

$\Delta_{\sqrt{2}A_{2}}=\frac{1}{\sqrt[4]{3}}\approx 0.76\ldots,$ (19)

which is the highest distance one can obtain for a single-mode GKP code
encoding a single qubit as it is the densest lattice packing in two dimensions
[30]. Interestingly, code states of the hexagonal GKP code have also been
rederived in a numerical search for the most robust encoding of a qubit into
an oscillator under photon loss [6].

Other high dimensional GKP codes built by scaling symplectic self-dual root
lattices become increasingly complex and interesting, such as the GKP code
built upon the dihedral root system $D_{4}$ examined in ref. [13], the _Gosset
lattice_ obtained from the exceptional Lie algebra $E_{8}$ or the Leech
lattice $\Lambda_{24}$, and warrant much further investigation in the future.

$n$ | $\dim\left(\mathcal{L}_{0}\right)\,\left(\mathcal{L}\right)$ | $\mathcal{L}_{0}$ | $\left(\lambda_{1}\left(\mathcal{L}\right)\right)^{2}$ | Symp. self-dual | Eucl. self-dual | Concatenated
---|---|---|---|---|---|---
$1$ | $2$ | $\mathbb{Z}^{2}$ | $1$ | ✓ | ✓ | –
$1$ | $2$ | $A_{2}$ | $\frac{2}{\sqrt{3}}$ | ✓ | ✓ | –
$2$ | $4$ | $D_{4}$ | $\sqrt{2}$ | ✓[11] | ✓ |  $\mathcal{L}_{\rm triv}\sim\mathbb{Z}^{4}$ w/ repetition code [13]
$4$ | $8$ | $E_{8}$ | $2$ | ✓ | ✓ |  $\mathcal{L}_{\rm triv}\sim 2\mathbb{Z}^{8}$ w/ Hamming code [30] $\mathcal{H}_{8}=[8,4,4]$
$6$ | $12$ | $K_{12}$ |  $\frac{4}{\sqrt{3}}$ [11] | ✓[11] | ✓ |  $\mathcal{L}_{\rm triv}\sim A_{2}^{6}$ [31]
$12$ | $24$ | $\Lambda_{24}$ | 4 [30] | ✓[26] | ✓ |  $\mathcal{L}_{\rm triv}\sim 2\mathbb{Z}^{8}$ w/ Golay code∗ [30] $\mathcal{C}_{24}=[24,12,8]$
$n$ | $2n$ | $\sqrt{\lambda/q}L_{\rm NTRU}$ | $\Delta\sim O\left(\sqrt{n/\lambda}\right)$ | ✓ | ✓ | $\mathcal{L}_{\rm triv}\sim\sqrt{\lambda q}\mathbb{Z}^{2n}$
$N$ | $2N$ | $\Lambda_{\square}\left(\mathcal{Q}\right)$ | $\Delta\geq\sqrt{d/2}$ | x | x | $\mathcal{Q}=[\\![N,k,d]\\!]$
$N$ | $2N$ | $\Lambda\left(\mathcal{Q}\right)$ | $\Delta=\sqrt{d/\sqrt{3}}$ | x | x | $\mathcal{Q}=[\\![N,k,d]\\!]$

Figure 2: Some notable weakly symplectically self-dual (symplectic) lattices
that yield GKP codes. The lower block indicates the concatenation of single
mode $\mathcal{L}_{\square}=\sqrt{2}\mathbb{Z}^{2}$ square GKP and
$\mathcal{L}=\sqrt{2}A_{2}$ hexagonal GKP codes with qubit quantum error
correcting- or detecting codes. Note that concatenation with $\mathcal{L}$
does not formally produce a Construction A lattice, but is related by a
symplectic transformation $S^{n}=\oplus_{i}^{n}S$, $S=M_{A_{2}}^{T}$ to the
concatenation with the square GKP code generated by
$M_{\mathbb{Z}^{2}}=I_{2}$, which in fact is Construction A. The
symplectically self-dual root lattices listed in this table and their use as
GKP codes have previously been identified in ref. [11]. The re-scaled $L_{\rm
NTRU}$ lattices that we use here to to construct NTRU-GKP codes are indicated
between those and the “more genuine” lattices corresponding to concatenated
codes. The statements about (symplectic) self-duality are generally up to
scaling and rotations.

#### Concatenated GKP codes.

Once a logical qubit is obtained by means of a scaled GKP code, one can
concatenate it with a _quantum error correcting_ \- or _quantum error
detecting code_ (QECC/QEDC) $\mathcal{Q}=[\\![N,k,d]\\!]$ to obtain a GKP
lattice with larger minimum distance. If $Q$ is the set of symplectic vectors
representing the stabilizers of a QECC/QEDC or generally, any set of (binary)
vectors such that $\forall p,q\in Q:\;p^{T}Jq=0\mod\,2$, we can construct a
GKP lattice by means of Construction A [30, 12], which yields

$\Lambda\left(Q\right):=\left\\{\bm{x}\in\mathbb{R}^{2n}\big{|}\sqrt{2}\bm{x}\mod
2\in Q\right\\}.$ (20)

This lattice can be interpreted as the full-rank embedding of $Q$ into
$\mathbb{R}^{2n}$ and inherits its main properties immediately from the code
properties of $Q$ including decoding algorithms. In refs. [32, 33, 9, 34, 35],
known decoding algorithms for quantum error correcting codes such as minimum-
weight-perfect-matching (MWPM, which is an MED decoder) have been adapted to
decode diverse concatenations of the single mode square GKP code with the
popular _surface_ , _toric_ , _color_ , and _quantum low-density-parity-check_
(QLDPC) codes, where the corresponding GKP-lattices can all be understood as
Construction A lattices. As noted previously, we denote the underlying multi-
mode square-GKP code as $\mathcal{L}_{N\square}$ and the full lattice
corresponding to the concatenated code as $\mathcal{L}=\Lambda\left(Q\right)$,
such that we have $\mathcal{L}_{N\square}\subseteq\mathcal{L}$ and reversely
$\mathcal{L}^{\perp}\subseteq\mathcal{L}_{N\square}^{\perp}$. These procedures
have in common that one decodes in two steps provided the syndrome and a
generic correction $\bm{\eta}$: 1. Solve CVP on the superlattice
$\mathcal{L}_{N\square}^{\perp}$, perform the corresponding correction. This
step returns one to $\mathcal{L}_{N\square}^{\perp}$ and the residual syndrome
is a genuine binary syndrome for $Q$. 2. The qubit-level decoder solves some
version of (approximate) CVP on $\mathcal{L}^{\perp}$ provided that one starts
out from $\mathcal{L}_{N\square}^{\perp}$. Before applying this decoder one
computes a metric from the syndrome on $\mathcal{L}_{N\square}$ to take
advantage of the continuous information held by the full GKP syndrome. Finally
one applies the qubit-level decoder with the amended metric. In total, this
decoder can be pictured as a sequence

$\mathbb{R}^{2n}\rightarrow\mathcal{L}_{N\square}^{\perp}\xrightarrow{\mathtt{CVP}\left(\mu\right)}\mathcal{L}^{\perp}.$
(21)

It is also known that one can solve CVP exactly on any Construction A lattice
provided a soft decoder for the underlying binary code $Q$, see ref. [30, p.
450]. This observation has, e.g., been used to construct CVP algorithms for
the $E_{8}$, which can also be understood as a Construction A lattice on the
$\mathcal{H}_{8}=[8,4,4]$ Hamming code.

###  3.1 Decoding complexity of GKP codes

Due to the lattice theoretic nature of GKP codes and their respective decoding
problems and the well developed literature on lattice problems, it is
interesting to investigate the computational complexity of decoding GKP codes
from this perspective. Before we continue to construct GKP codes from a
cryptosystem proposed for post-quantum cryptography in the next section, we
show that 1. for GKP codes, MLD decoding is at least as hard as MED decoding
and 2. MED decoding a concatenated (qubit-) GKP code implies a decoder for the
corresponding qubit-code.

We include these statments here because we find the proofs illustrative and
wish to highlight that decoding complexity of GKP codes is an interesting
question deserving of our attention. Denote by eMLD the problem of evaluating
the MLD probabilty given by the theta function on the RHS in eq. (7)

######  Lemma 1.

($\mathtt{eMLD}\geq\mathtt{MED}$) Given an oracle that evaluates

$\mathtt{eMLD}\left(\bm{x},\bm{\xi}^{\perp},\mathcal{L},\overline{\sigma}\right)=\Theta_{\mathcal{L}+\bm{\xi}^{\perp}+\bm{x}}\left(\frac{i}{2\pi\overline{\sigma}^{2}}\right),$

$\mathtt{CVP}\left(\bm{x},\mathcal{L}^{\perp}\right)$ can be solved
efficiently.

###### Proof.

Denote by $\mathtt{DecCVP}\left(\bm{x},\mathcal{L},r\right)$ the decisional
CVP problem that outputs $\mathtt{True}$ if
$\text{dist}\left(\bm{x},\mathcal{L}\right)\leq r.$ This is polynomially
equivalent to the optimization- and search variants of $\mathtt{CVP}$ [36].
First notice that we generally have

$\displaystyle\Theta_{\mathcal{L}^{\perp}+\bm{x}}\left(\frac{i}{2\pi\overline{\sigma}^{2}}\right)$
$\displaystyle=\sum_{\bm{\xi}^{\perp}\in\mathcal{L}^{\perp}/\mathcal{L}}\Theta_{\mathcal{L}+\bm{\xi}^{\perp}+\bm{x}}\left(\frac{i}{2\pi\overline{\sigma}^{2}}\right)$
$\displaystyle\geq
e^{-\frac{1}{2\overline{\sigma}^{2}}\text{dist}\left(\bm{x},\mathcal{L}^{\perp}\right)^{2}}.$
(22)

If $\mathtt{DecCVP}\left(\bm{x},\mathcal{L},r\right)$ is true, then we further
have

$e^{-\frac{1}{2\overline{\sigma}^{2}}\text{dist}\left(\bm{x},\mathcal{L}^{\perp}\right)^{2}}\geq
e^{-\frac{r^{2}}{2\overline{\sigma}^{2}}}$ (23)

for all $\overline{\sigma}\in\mathbb{R}$, and hence we can solve
$\mathtt{DecCVP}\left(\bm{x},\mathcal{L}^{\perp},r\right)$ by checking if
above condition is true for sufficiently small $\overline{\sigma}<r$.
Alternatively, w.l.o.g. assume that $\mathcal{L}\subset\mathbb{Z}^{n}$ and
$\bm{x}\in\mathbb{Z}$. Given access to

$\Theta_{\mathcal{L}^{\perp}+\bm{x}}\left(z\right)=\sum_{m\in\mathbb{N}}a_{m}e^{i\pi
zm},$

we can compute

$2a_{m}=e^{m\pi\tau}\int_{-1}^{1}dt\,e^{-it\pi
m}\Theta_{\mathcal{L}^{\perp}+\bm{x}}\left(t+i\tau\right)$ (24)

to evaluate $\\{a_{m}\\}$ for $m=1,\dots,M$, where $M$ can be bounded by
Mikowskis convex body theorem, to find the smallest non-zero coefficient
$a_{m}$. This solves optimization-CVP which is polynomially equivalent to its
search version.∎

Note that here we did not show that the full $\mathtt{MLD}$ problem

$\mathtt{MLD}\left(\bm{x},\mathcal{L},\overline{\sigma}\right)=\operatorname*{arg\,max}_{\bm{\xi}^{\perp}\in\mathcal{L}^{\perp}/\mathcal{L}}\Theta_{\mathcal{L}+\bm{\xi}^{\perp}+\bm{x}}\left(\frac{i}{2\pi\overline{\sigma}^{2}}\right)$
(25)

is hard.

In ref. [30, p. 450], it has (constructively) been shown that given a soft
decoder for a binary code $C$, we can always solve $\mathtt{CVP}$ on the
corresponding Construction A lattice $\Lambda\left(C\right)$. We explain this
point, which also clarifies the geometric picture on decoding concatenated
codes presented in eq. (21).

######  Lemma 2 ([30], p. 450).

$\mathtt{CVP}\left(\cdot,\,\Lambda\left(C\right)\right)=\mathtt{Decode\left(C\right)}.$
(26)

###### Proof.

$C$ is embedded in $\mathbb{Z}^{n}$ by identifying the (scaled and shifted)
Construction A lattice $\Lambda\left(C\right)=1-2C+4\mathbb{Z}^{n}$, where
every bit string $\bm{b}\in C$ is mapped to $1-2\bm{b}\in\\{-1,1\\}^{n}$. In
this representation we consecutively solve
$\mathtt{CVP}\left(\cdot,4\mathbb{Z}^{n}\right)$ and then apply the soft
decoder for $C$, which finds the closest transformed code word $\bm{c}\in
1-2C\in\\{-1,1\\}^{n}$ to input $\bm{x}^{\prime}\in\mathbb{R}^{n}$. As both
decoders are exact, with a little care (see ref. [30, p. 450]), this solves
CVP exactly. Note that the reverse direction is trivially true via the
embedding of $C$ into $\mathbb{R}^{n}$ provided by Construction A and taking
modulo $4\mathbb{Z}^{n}$. A hard decoder, that solves

$\operatorname*{arg\,min}_{\bm{c}\in
C}d_{H}\left(\bm{c}_{b},\bm{x}_{b}\right)$ (27)

on binary input $\bm{x}\in\\{-1,1\\}^{n}$ is also derived from a soft decoder
by noticing that
$\|\bm{c}-\bm{x}\|_{2}^{2}=4d_{H}\left(\bm{c}_{b},\bm{x}_{b}\right)$, where
$\bm{x}_{b}$ represents the binary $\\{0,1\\}$ representation of $\bm{x}$ and
$d_{H}$ is the Hamming distance. ∎

It is known that decoding classical error correcting codes, as specified in
eq. (27) is a computationally hard problem in general [37, 38]. Hardness of
decoding qubit-based quantum error correcting codes has previously been
investigated by reduction to the related problem on classical codes [39] to
show its NP-completeness, and by showing its relationship to computing weight
enumerators of a linear code, ref. [40] has even shown its $\\#P$-hardness in
worst case complexity.

By a similar line of argumentation, one notes that the coefficients of the
shifted lattice theta function

$\Theta_{\mathcal{L}+\bm{x}}\left(z\right)=\sum_{m\in\mathbb{Z}}N_{m}\left(\mathcal{L},\bm{x}\right)q^{m},$
(28)

with

$N_{m}\left(\mathcal{L},\bm{x}\right)=\\#\left\\{\bm{y}\in\mathcal{L}+\bm{x}:\,\|\bm{y}\|^{2}=m\right\\}$
(29)

counting the number of lattice vectors such that
$\operatorname{dist}\left(\bm{x},\mathcal{L}\right)^{2}=m$ are hard to compute
in general. While we do not attempt to complete such a proof here, we expect a
theta-function based analysis of the decoding complexity of quantum error
correcting codes using concatenation with single-mode GKP codes to yield
similar results as refs. [39, 40].

##  4 GKP codes from NTRU lattices

Random lattices and variations of lattice problems SVP and CVP play a
prominent role in classical- and post-quantum cryptography due to their
assumed hardness even for quantum computers in the worst-case, as well as due
to the feature of worst-case to average-case average case reductions for such
problems [41]. The proof of existence of what we termed good GKP codes
provided by ref. [16] can in essence be formulated using a Haar average over
the moduli space of all symplectic lattices [26]. The analogous heuristic to
lower bound the shortest vector in a general lattice is given by the Gaussian
heuristic.

######  Proposition 1 (Gaussian heuristic (GH)).

Let $L\subset\mathbb{R}^{n}$ be a sufficiently random full rank lattice with
large $n$, then we expect the smallest non-zero vector in the lattice will
satisfy

$\lambda_{1}\left(L\right)\approx\sqrt{\frac{n}{2\pi
e}}\det\left(L\right)^{\frac{1}{n}}.$ (30)

“Proof” [42, 43]: The moduli space of full rank lattices in $\mathbb{R}^{n}$
with unit covolume is given by
$\mathcal{L}_{n}=\mathrm{SL}_{2n}\left(\mathbb{Z}\right)\setminus\mathrm{SL}_{2n}\left(\mathbb{R}\right)$,
where the left333We write the left quotient because of the row-convention used
in the definition of lattice bases. In the literature one more commonly uses a
right-quotient associated to a column-convention. quotient
$\mathrm{SL}_{2n}\left(\mathbb{Z}\right)$ indicates the equivalence up to
changes of basis. There is a Haar measure $\mu_{n}$ over $\mathcal{L}_{n}$,
normalized to $\mu_{n}\left(\mathcal{L}_{n}\right)=1$, such that for Lebesque-
integrable functions $f:\,\mathbb{R}^{n}\mapsto R$, we have that [44]

$\displaystyle\int_{L\in\mathcal{L}_{n}}f\left(L\setminus\left\\{0\right\\}\right)\,d\mu_{n}$
$\displaystyle=\int_{\mathbb{R}^{n}}f\left(\bm{x}\right)\,d\bm{x},$ (31)
$\displaystyle\,\text{where}\hskip
28.45274ptf\left(L\setminus\left\\{0\right\\}\right)$
$\displaystyle=\sum_{\bm{x}\in
L\setminus\left\\{0\right\\}}f\left(\bm{x}\right).$ (32)

Let $f\left(\bm{x}\right)=\theta\left(\|\bm{x}\|\leq R\right)$, where $\theta$
is the Heaviside function. Eq. (32) yields

$\Big{\langle}\\#\left\\{\bm{x}\in L:\,\|\bm{x}\|\leq R,\;\bm{x}\neq
0\right\\}\Big{\rangle}_{L\in\mathcal{L}_{n}}=V_{n}(R),$ (33)

where

$V_{n}(R)=\frac{\pi^{\frac{n}{2}}}{\Gamma\left(\frac{n}{2}+1\right)}R^{n}$
(34)

is the volume of the centered $n-$ball $B_{n}(R)\subset\mathbb{R}^{n}$.

We hence have that if lattices $L$ are sampled from a random distribution
close $\mu_{n}$ in the moduli space of all lattices with
$\det\left(L\right)=1$, the average number of non-zero lattice points of
length at most $R$ is given by the volume of the $n$-ball, $V_{n}(R)$.
Similarly, it is reasonable to expect that the average number of non-zero
lattice points of length at most $R$, when the lattice has
$\det\left(L\right)\neq 1$ and is sampled from an approximation to the Haar
measure is given by $V_{n}\left(R\right)/\det\left({L}\right)$.

Using Stirling’s approximation, the smallest $R$ for which this number becomes
non-zero is given by $R\approx\sqrt{n/2\pi
e}\det\left(L\right)^{\frac{1}{n}}$. ∎

The Gaussian heuristic motivates that lattices with
$\lambda_{1}=O\left(\sqrt{n}\right)$ can be found amongst sufficiently random
sets of lattices. Buser and Sarnak [26] showed that there is also a Haar
measure over the moduli space of _symplectic_ lattices, using which Harrington
and Preskill identified the existence of good GKP codes by a similar
calculation as presented above [16].

The construction of random lattices is a crucial ingredient to lattice based
cryptography.

In this section we introduce the NTRU cryptosystem and show that random _NTRU
lattices_ obtained from variations of the NTRU cryptosystem are in fact
symplectic, such that they allow to construct GKP codes as scaled GKP codes.
We discuss scenarios where NTRU lattices are sufficiently random to follow the
Gaussian heuristic or, at least, can be shown to admit a lower bound
$\lambda_{1}\geq O(\sqrt{n})$ with high probability.

The so-derived GKP codes share characteristics of both scaled- and
concatenated GKP codes. These NTRU lattices have been originally formulated in
the cryptanalysis of attacks on the NTRU cryptosystem [15, 45, 46, 47] and
their symplecticity has been motivation to further the study of lattice
reduction algorithms for symplectic lattices [28]. As GKP codes, these
lattices are particularly interesting as they can be understood as certain
generalization of cyclic quantum error correcting codes such as the well known
$XZZX-\,[\\![5,1,3]\\!]$ quantum error correcting code [48] or the repetition
code and have a similar algebraic basis as the recently introduced lifted
product codes [23].

###  4.1 The NTRU cryptosystem

We describe the NTRU cryptosystem to the degree necessary to understand the
structure of the corresponding lattices and GKP codes constructed here. For
more detail we refer the reader to the cited literature. The presentation here
is largely derived from the presentations in refs. [15, 46, 47, 49, 50, 51].

The NTRU cryptosystem is most natively formulated using polynomial rings
$R=\mathbb{Z}\left[x\right]/\Phi$, where we will take the quotient
$\Phi=x^{n}+\Phi_{n-1}x^{n-1}+\ldots+\Phi_{0}$ as $\Phi=\Phi_{0}:=x^{n}-1$ in
the bulk of this paper, as used in the original description of the
(heuristically secure) NTRU cryptosystem [15]. We will keep $\Phi$ general
whenever possible to be able to discuss the provably secure version of the
NTRU cryptosystem [50] with irreducible $\Phi=x^{n}+1$ later. We denote
$R_{q}=R/qR$ with a typically large modulus parameter $q$ and $R_{p}=R/pR$
with a typically small $p$ coprime with $q$. Whenever we take the modulus,
$\mod q$ or $\mod p$, we refer to the (coefficient-wise) reduction into the
centered fundamental domains $\left[-\frac{q}{2},\frac{q}{2}\right]$ resp.
$\left[-\frac{p}{2},\frac{p}{2}\right]$.

We denote multiplication in $R$ as $fg\mod\Phi,\,f,g\in R$, where we assume
the reduction $\mod\Phi$ ($\mod q/p$) to be implicit by specifying the image
and use a bold $\bm{f}=\mathrm{coeff}(f)$ to refer to the coefficient vector
$\bm{f}=(f_{0},f_{1},\dots,f_{n-1})$ of $f\in R$ (note that any polynomial in
$R$ can be represented with $n-1$ coefficients, for that every power $x^{n}$
can be replaced by $x^{n}-\Phi$ when working over $\mod\Phi$.

Denote the uniform distribution of polynomials $p\in R_{q}$ with $d_{1}$
coefficients $+1$, $d_{2}$ coefficients $-1$ and $n-(d_{1}+d_{2})$
coefficients $0$ as $D\left(d_{1},d_{2}\right)$. Further denote the set of
invertible elements in $R_{q}$, i.e., elements $f$ for which $f^{-1}\in R_{q}$
exists, as $R_{q}^{\times}$.

The NTRU cryptosystem, specified by parameters $\left(n,\Phi,d,q,p\right)$
operates as follows:

  1. 1.

Key generation: Sample $\tilde{f}\hookleftarrow D(d,d)$ until
$f=1+p\tilde{f}\in R_{q}^{\times}$, sample $\tilde{g}\hookleftarrow D(d,d)$ to
obtain $g=p\tilde{g}$. Return the secret key pair $(f,g)$, and the public key
$h=gf^{-1}\in R_{q}$.

  2. 2.

Encryption: Given the public key $h\in R_{q}$ and a message $m\in R_{p}$,
sample a random polynomial $r\in R_{p}$ and compute the ciphertext $c=hr+m\in
R_{q}$.

  3. 3.

Decryption: Given the ciphertext $c$ and secret key $f$, compute $cf\mod q\mod
p=gr+fm\mod q\mod p=m\in R_{p}$.

The secret key polynomials $(f,g)\in R_{q}^{\times}\times R_{q}$ are by
construction such that $f\mod p=1$ and $g\mod p=0$. Decryption is guaranteed
to be successful whenever all the coefficients involved are sufficiently
small, such that $cf=gr+fm$ holds as equality in $R$, and not just merely in
$R_{q}$ [42].

###  4.2 Symplectic ideal and NTRU lattices

The security assumption underlying this cryptosystem as the in-retrievability
of the secret key is the hardness of the polynomial factorization problem in
$R_{q}$ and secret key retrieval attacks have been formulated already in early
analyses of the NTRU cryptosystem [15, 45, 47].

######  Assumption 1 (Polynomial factorization problem [47]).

Given a polynomial $h=f^{-1}g\in R_{q}$ where the coefficients are small
compared to q. For suitable parameter settings it is intractable to find to
small polynomials $f^{\prime},g^{\prime}\in R_{q}$ such that
$f^{\prime}h=g^{\prime}\in R_{q}$.

Under the premise that the coefficient vectors of the secret key $(f,g)$ are
short, a typical attack is formulated as the task of finding short polynomials
$(f^{\prime},g^{\prime})\in R_{q}^{2}$ such that $fh=g\in R_{q}$, where the
length of the polynomial pair is defined as the norm of their joined
coefficient vectors
$\|(f^{\prime},g^{\prime})\|_{l}=\|(\bm{f^{\prime}}^{T},\bm{g^{\prime}}^{T})\|_{l}$.
We will use the $l=2$ norm unless specified otherwise. The attack is carried
out by defining the NTRU lattice as an $R$-module $L_{R}\subseteq R^{2}$,
which admits a basis in its Hermite normal form

$H_{R}=\begin{pmatrix}1&h\\\ 0&q\end{pmatrix}.$ (35)

Elements of the $R$-lattice are of the form

$\displaystyle(f^{\prime}\;u)H_{R}$
$\displaystyle=(f^{\prime}\;u)\begin{pmatrix}1&h\\\ 0&q\end{pmatrix}$ (36)
$\displaystyle=(f^{\prime}\;f^{\prime}h+uq)$
$\displaystyle=(f^{\prime},f^{\prime}h+uq),\;(f^{\prime},u)\in R^{2},$

each of which represent admissible solutions to the equation
$f^{\prime}h=g^{\prime}\in R_{q}$, such that short vectors in $L_{R}$ are
expected to correspond to the NTRU secret key pair. In a more general
classification, one can view the $R$-lattice $L_{R}=L_{R}(h)$ as an rank-$2$
ideal lattice [52] , corresponding to the principal ideal $I=\langle
h\rangle\subseteq R$.

$H_{R}$ is, in fact, also a $q$-symplectic matrix in $R^{2\times 2}$, with
respect to the symplectic form

$J_{R}=\begin{pmatrix}0&1\\\ -1&0\end{pmatrix}\in R^{2\times 2},$ (37)

with

$H_{R}J_{R}H_{R}^{T}=\begin{pmatrix}h^{T}-h&q\\\ -q&0\end{pmatrix}=qJ_{R}\in
R^{2\times 2}$ (38)

because $h$ is a scalar in $R$.

Analyses of lattices and associated algorithms are typically formulated over
$\mathbb{Z}$-lattices, where linear combinations of basis vectors are taken
with integer coefficients. We map the rank-$2$ $R$-lattice $L_{R}$ to a
rank-$2n$ $\mathbb{Z}$-lattice $L\subseteq\mathbb{Z}^{2n\times 2n}$ by
defining a homomorphism onto a $\mathbb{Z}^{n\times n}$ matrix

$\displaystyle C_{\Phi}:\;R$ $\displaystyle\rightarrow\mathbb{Z}^{n\times n}$
(39) $\displaystyle f$ $\displaystyle\mapsto C_{\Phi}(f),$ (40)
$\displaystyle\left(C_{\phi}\left(f\right)\right)_{i,j}$
$\displaystyle=(T_{\Phi}^{i}\bm{f})_{j},\,i,j=0,\dots,n-1,$ (41)

where the rows are given by the vectors $T_{\Phi}\bm{f}$ and

$T_{\Phi}=\begin{pmatrix}\bm{0}^{T}&-\Phi_{0}\\\
I_{n-1}&-\bm{\Phi}_{1:n-1}\end{pmatrix}$ (42)

implements the map $f\mapsto xf\mod\Phi\in R$ on the coefficient vector
$\bm{f}$ of $f$ by left multiplication.

$C_{\Phi}$ is linear over $\mathbb{Z}$, such that we can express the
homomorphism on every polynomial $f\in R$ as

$\displaystyle C_{\Phi}\left(f\right)$
$\displaystyle=\sum_{i=0}^{n-1}f_{i}C_{\Phi}\left(x^{i}\right)$ (43)
$\displaystyle=\sum_{i=0}^{n-1}f_{i}C_{\Phi}\left(1\right)\left(T_{\Phi}^{T}\right)^{i},$
$\displaystyle=\sum_{i=0}^{n-1}f_{i}\left(T_{\Phi}^{T}\right)^{i},$

where we have used that $C_{\Phi}\left(1\right)=I_{n}\;\forall\Phi$. In this
representation, it is evident that $C_{\Phi}\left(f\right)$ acts via right
action

$\mathrm{coeff}(fg\mod\Phi)=\bm{f}^{T}C_{\Phi}\left(g\right)=\bm{g}^{T}C_{\Phi}\left(f\right)$
(44)

and that

$C_{\Phi}\left(fg\mod\Phi\right)=C_{\Phi}\left(f\right)C_{\Phi}\left(g\right)$
(45)

indeed represents a homomorphism. When $\Phi=\Phi_{0}=x^{n}-1$,
$C_{\Phi}\left(f\right)$ is simply the (row) circulant matrix of the
coefficient vector $\bm{f}$. Circulant matrices are not symmetric, but have a
mirror symmetry along the anti-diagonal,
$R_{n}C_{\Phi_{0}}^{T}\left(f\right)R_{n}=C_{\Phi_{0}}\left(f\right),$ where
$R_{n}$ is the anti-diagonal matrix
$(R_{n})_{i,j}=\delta_{i,n-1-j},\,i,j=0,\dots,n-1$. We also define a related
map

$\displaystyle A_{\Phi}:\;R$ $\displaystyle\rightarrow\mathbb{Z}^{n\times n}$
(46) $\displaystyle f$ $\displaystyle\mapsto A_{\Phi}(f),$ (47)
$\displaystyle\left(A_{\phi}\left(f\right)\right)_{i,j}$
$\displaystyle=(T_{\Phi}^{-i}\bm{f})_{j},\,i,j=0,\dots,n-1,$ (48)

where $T_{\Phi}^{-i}=\left(T_{\Phi}^{-1}\right)^{i}$ and for
$\Phi=\Phi_{0}=x^{n}-1$ this is the symmetric anti-circulant matrix of the
coefficient vector $\bm{f}$, $A_{\Phi_{0}}^{T}(f)=A_{\Phi_{0}}(f)$. Since
$A_{\Phi}$ is also $\mathbb{Z}$-linear, here we have

$\displaystyle A_{\Phi}\left(f\right)$
$\displaystyle=\sum_{i=0}^{n-1}f_{i}A_{\Phi}\left(x^{i}\right)$ (49)
$\displaystyle=A_{\Phi}\left(1\right)C_{\Phi}\left(f\right),$

where, for $\Phi=\Phi_{0}=x^{n}-1$, we have that

$A_{\Phi}\left(1\right)=\begin{pmatrix}1&0\\\
\bm{0}&I_{n-1}\end{pmatrix}=:\sigma$ (50)

is the orthogonal coefficient mirror $\sigma=\sigma^{T}$ that maps the
coefficient vector $f(x)\in R$ to that of
$f\left(x^{-1}\right)=f\left(x^{n-1}\right)\in R$ [47].

The so-defined maps allow us to define map the earlier defined $R$-lattice
$L_{R}$ onto a lattice $L=L(h)\subseteq\mathbb{Z}^{2n}$ by applying the
corresponding homomorphism on the entries of the basis

$H_{R}=\begin{pmatrix}1&h\\\ 0&q\end{pmatrix}\mapsto
H=\begin{pmatrix}I_{n}&C_{\Phi}\left(h\right)\\\ 0&qI_{n}\end{pmatrix}.$ (51)

It can be checked that the lattice spanned by the basis contains all secret
key pairs $(\bm{f^{\prime}}^{T}\;\bm{g^{\prime}}^{T})$ corresponding to
solutions $fh=g\in R_{q}$. It is however not symplectic. For $\Phi=\Phi_{0}$
we, however, have that

$H^{cs}=\begin{pmatrix}I_{n}&A_{\Phi_{0}}\left(h\right)\\\
0&qI_{n}\end{pmatrix}=\begin{pmatrix}I_{n}&\sigma
C_{\Phi_{0}}\left(h\right)\\\ 0&qI_{n}\end{pmatrix}$ (52)

is indeed symplectic and corresponds to a rotation of the lattice $L$,

$(\sigma\oplus I_{n})H^{cs}=H_{\mathbb{Z}}(\sigma^{T}\oplus I_{n}),$ (53)

since $(\sigma\oplus I_{n})$ is unimodular. This is the basis used by
Coppersmith and Shamir in their attack on the NTRU cryptosystem [45, 47]. We
generalize this observation to the following statement.

######  Lemma 3.

An NTRU lattice $L\subseteq\mathbb{Z}^{2n}\subset\mathbb{R}^{2n}$ given by
generator

$H_{\mathbb{Z}}=\begin{pmatrix}I_{n}&C_{\Phi}\left(h\right)\\\
0&qI_{n}\end{pmatrix}$ (54)

is equivalent to a $q$-symplectic lattice $L^{\prime}\subset\mathbb{R}^{2n}$
for all $h$ if there exists a signed permutation matrix
$\sigma_{\Phi}\in\mathbb{Z}^{n\times n}\cap O\left(n\right)$ such that

$\left(\sigma_{\Phi}C_{\Phi}\left(h\right)\right)^{T}=\sigma_{\Phi}C_{\Phi}\left(h\right)$
(55)

is symmetric.

###### Proof.

A lattice generated by $M$ with is equivalent to a lattice generated by
$M^{\prime}$, such that $\det M=\det M^{\prime}$ if and only if there exists a
unimodular matrix $U$ and an orthogonal matrix $O$ such that $M^{\prime}=UMO$
[30]. Take $O=\left(\sigma_{\Phi}^{T}\oplus I_{n}\right)$ and
$U=\left(\sigma_{\Phi}\oplus I_{n}\right)$. ∎

######  Corollary 1.

NTRU lattices over $\Phi=\Phi_{0}$ and $\Phi=x^{n}+1$ are equivalent to
$q$-symplectic lattices

###### Proof.

For $\Phi=\Phi_{0}$ we already saw earlier that $\sigma_{\Phi_{0}}=\sigma$
provides a symmetric matrix $\sigma C_{\Phi}\left(h\right)$ for all $h$. For
$\Phi=x^{n}+1$ this is also the case, with

$\sigma_{\Phi}=\begin{pmatrix}1&\bm{0}^{T}\\\
\bm{0}&-I_{n-1}\end{pmatrix}=A_{\Phi}\left(1\right)$ (56)

and $A_{\Phi}\left(1\right)C_{\Phi}\left(h\right)=A_{\Phi}\left(h\right)$ is
such that the first row is $\bm{h}^{T}$ and every other row is generated by
permuting the first element around the “periodic boundary” on the right to the
left while adding a $-1$ factor. This matrix is clearly symmetric and
$\sigma,\sigma_{\Phi}$ are signed permutations. ∎

Finally, the fact that these NTRU lattices $L$ corresponds to ideals
$I=\langle h\rangle\subseteq R$ equips them with the symmetry
$L=(T_{\Phi}\oplus T_{\Phi})L$. When $\Phi=\Phi_{0}$ we have that the symmetry
is $n$-fold, $T_{\Phi_{0}}^{n}=I$ and similarly for $\Phi=x^{n}+1$ we have
$T_{\Phi}^{n}=-I$.

Henceforth we will default to $\Phi=\Phi_{0}$ unless otherwise specified and
omit the corresponding $\Phi_{0}$ index from $C_{\Phi_{0}}$ and
$A_{\Phi_{0}}$. The anti-circulant matrix $A\left(h\right)=\sigma
C\left(h\right)$ implements a homorphism from $R$ w.r.t a modified matrix
multiplication

$A\left(f\right)\sigma A\left(h\right)=\sigma
C\left(f\right)C\left(f\right)=A\left(fg\right).$ (57)

We denote $A\left(f\right)\sigma=:A^{\sigma}\left(f\right)$, such that
$A^{\sigma}\left(f\right)A\left(g\right)=A\left(f\right)$.

On $\mathbb{Z}^{n}$, ciphertexts produced by the NTRU encryption with secret
key pair $(f,g)$ and public key $h$ take the form

$\displaystyle\bm{c}^{T}$ $\displaystyle=\bm{m}^{T}+\bm{r}^{T}C(h)\,\mod q$
(58) $\displaystyle=\bm{m}^{T}+\left(\sigma\bm{r}\right)^{T}\sigma C(h)\,\mod
q$

and decryption is carried out by left-multiplying with
$A^{\sigma}\left(f\right)$ and reducing $\mod q$ and $\mod p$.

The corresponding $q$-symplectic generator of the underlying lattice is given
by

$H=\begin{pmatrix}I_{n}&A\left(h\right)\\\ 0&qI_{n}\end{pmatrix},$ (59)

which is already a $q$-symplectic basis for the weakly symplectically self-
dual lattice $L$.

We use this lattice as starting point to define a scaled GKP-code by taking
$\mathcal{L}=\sqrt{({\lambda}/{q})}L$ with generator
$M=\sqrt{({\lambda}/{q})}H$. Similar to the discussion earlier, the GKP code
built this way will encode $D=\lambda^{n}$ logical dimensions with symplectic
dual

$\mathcal{L}^{\perp}=L/\sqrt{\lambda q}$ (60)

and distance

$\Delta=\lambda_{1}\left(L\right)/\sqrt{\lambda q}.$ (61)

For randomly chosen $f,g\in\mathcal{R}$, the Gaussian heuristic gives an
estimate for the shortest vector length and has been used in the original NTRU
work to argue about the security of the scheme [15]. If the Gaussian heuristic
were to hold, the so-constructed NTRU lattices would attain parameters

$\displaystyle D$ $\displaystyle=\lambda^{n},$ (62) $\displaystyle\Delta$
$\displaystyle\geq\sqrt{\frac{n}{\lambda\pi e}},$ (63)

which are good.

However, the Gaussian heuristic does not always hold for NTRU lattices with
arbitrary parameters. Due to the the sub-lattice $q\mathbb{Z}^{2n}\subset L$
there always exist trivial vectors $q\bm{e}_{i},\,i\in\left[1,2n\right]$ of
length $q$ in $L$ which yield logically non-trival vectors of length
$\sqrt{q/\lambda}$. A shortest vector length $\lambda_{1}\left(L\right)$
growing with $\sqrt{n}$ can however be maintained by choosing suitably large
$q$ scaling with $n$. Furthermore, NTRU lattices (with $\Phi_{0}$) are
constrained by 1. being cyclic lattices and 2. having an existing inverse of
$f\in R_{q}$ and 3. having a fixed number $2d$ of non-zero coefficients in the
vector corresponding to the secret key
$(\sigma\left(\bm{f}\right)^{T},\bm{g}^{T})^{T}\in L$, which on the one hand
make it not immediately clear if they would be sufficiently random for the
Gaussian heuristic to hold, and on the other already present short vectors of
length $\leq O(\sqrt{d})$. These points have been addressed in refs. [53, 54],
where the authors show the following statement.

######  Corollary 2 ([53, 54, Corollary 3]).

If $d=\lfloor n/3\rfloor$, then with probability greater than $1-2^{-0.1n}$
the shortest vector in a random NTRU lattice has length greater than
$\sqrt{0.28n}$.

This statement gives us confidence to claim that random NTRU lattice based GKP
codes as constructed above can be expected to be good when the parameters are
chosen properly, as summarized by the following.

######  Proposition 2 (Good codes from NTRU lattices).

A GKP code with $\mathcal{L}=\sqrt{({2}/{q})}L$, where $L$ is the NTRU lattice
over $\Phi_{0}$ specified in the basis eq. (59) with $d=\lfloor n/3\rfloor$
encodes

$k=n$ (64)

qubits and has with probability greater than $1-2^{-0.1n}$ a distance given by

$\Delta=\min\left\\{\sqrt{\frac{0.14n}{q}},\sqrt{\frac{q}{2}}\right\\}.$ (65)

For sufficiently large constant $q$ and $n\leq q^{2}/0.28$ this defines a
randomized family of good GKP codes.

###  4.3 Numerical results

In fig. 3, we have computed the shortest vector lengths for $N_{\rm
sample}=100$ randomly sampled NTRU lattices for varying $q$ and $n$ with
$p=3$, which are put in comparison with samples over (less constrained) random
cyclic lattices, where $h$ is sampled randomly from $R_{q}$ and (more
constrained) NTRU lattices with $f$ invertible in $R_{q}$ and bounded non-zero
entries $d=\lfloor n/3\rfloor$ (in panel $b)$) and with even more constrained
NTRU lattices where we also required the public key $h$ to be invertible in
$R_{q}$. In this case we obtain $g$ from the amended distribution $g\sim
pD(d+1,d)$ since otherwise $g$ – and thus $h$ – would have a trivial root
$g(1)=0$ rendering the polynomial non-invertible.

In our statistics we observe that random cyclic lattices appear to agree well
with the Gaussian heuristic, while the growth of the shortest vector length of
the NTRU lattices degrades with increasing $q$, but adheres well to the bound
given in Corollary 2. Based on our numerics, we also conjecture the following.

######  Conjecture 1 (Good GKP codes).

A GKP code with $\mathcal{L}=\sqrt{{\lambda}/{q}}L$, where $L$ is specified by
the basis in (59) and $h$ is selected at random from
$R_{q}=\mathbb{Z}_{q}\left[x\right]/\langle x^{n}-1\rangle$, is likely a good
code with $k=n$ and

$\Delta\geq\min\left\\{\sqrt{\frac{n}{\lambda\pi
e}},\sqrt{\frac{q}{\lambda}}\right\\}.$ (66)

######  Conjecture 2 (Good GKP codes).

A GKP code with $\mathcal{L}=\sqrt{{\lambda}/{q}}L$, where $L$ with $\det
L=q^{n}$ is equivalent to NTRU lattice specified by the basis in (59) and
$h=g/f\leftarrow f,g$ are sampled at random from a Gaussian distribution with
variance $\sigma^{2}=q$ in $R_{q}=\mathbb{Z}_{q}\left[x\right]/\langle
x^{n}+1\rangle$, $q\geq\mathtt{poly}(n)$ and $n\geq 8$ a power of $2$ is
likely a good code with $k=n$ and

$\Delta\geq\sqrt{\frac{n}{\lambda\pi e}}.$ (67)

In contrast to the previous statement, these distance bounds do not suffer
from choosing larger modulus $q$, but we can pick it arbitrarily large to
obtain high distances. In particular, conjecture 2 references the version of
the NTRU crptosystem discussed in ref. [50].

The trivial sub-lattice $L_{q}=q\mathbb{Z}^{2n}\subseteq L$ which enforces the
$q$ modularity in the cryptographic setup is analogue to the structure of
concatenated (hypercubic) GKP codes $\mathcal{L}_{\rm triv}=\sqrt{\lambda
q}\mathbb{Z}^{2n}\subseteq\mathcal{L}$, such that the lattices $\mathcal{L}$
defined above may be interpreted as a concatenated (qudit) GKP code where
$\mathcal{L}_{\rm triv}$ defines the underlying single mode qudit-code with
$D=\lambda q$. It is interesting that this class of NTRU-GKP codes thus shares
characteristics of both scaled- as well as concatenated GKP codes.

Figure 3:  Shortest vector lengths computed via full HKZ reduction of $a)$
random cyclic ($\Phi_{0}=x^{n}-1$) lattices as generated by the hard lattice
generator in sagemath, $b)$ random NTRU lattices with $p=3$ and $d=\lfloor
n/3\rfloor$ and $c)$ random NTRU lattices where $h$ is invertible in $R_{q}$
for varying $q=2,\dots,2048$. In $d)$ we sample NTRU lattices generated with
the irreducible quotient $\Phi=x^{n}+1$, where $n$ is a power of 2. For each
$n\in[2,24]$ we sample $100$ NTRU lattices and compute the shortest vector by
computing the HKZ reduced lattice basis. For reference, we plot the expected
shortest vector length from the Gaussian heuristic
$\lambda\left(n\right)=\sqrt{nq/\pi e}$ in blue and the expected lower bound
$\lambda_{0}\left(n\right)=\sqrt{0.28n}$ in red. In panel $d)$, we have also
included a green line at $\sqrt{q}$, which is the standard deviation of the
discrete Gaussian distribution $f,g$ are sampled from and is related to a
probabilistic lower bound for $n\geq 8$ a power of $2$ on the shortest
infinity norm $\lambda_{1}^{\infty}\left(L\right)$ derived in ref. [50].

##  5 Decoding GKP codes from NTRU lattices

A code state that (either through a natural error process or by deliberate
modification) undergoes a displacement by

$\bm{e}=\begin{pmatrix}\bm{x}\\\ \bm{y}\end{pmatrix}$ (68)

gives rise to trivial syndrome

$\displaystyle\bm{s}_{\rm triv}$ $\displaystyle=\sqrt{\lambda q}\bm{e}\mod 1.$
(69)

Due to the simple orthogonal structure of $\mathcal{L}_{\rm triv}$ a first
step of the correction is easily carried out by applying the correction
$\bm{\eta}=-\bm{s}_{\rm triv}/\sqrt{\lambda q}$. After correcting for the
trivial syndrome (associated to the underlying hypercubic GKP code) the
remaining error is the unknown, but likely short, vector

$\bm{e}^{\prime}=\frac{1}{\sqrt{\lambda q}}\begin{pmatrix}\bm{u}\\\
\bm{v}\end{pmatrix}\in\mathcal{L}_{\rm
triv}^{\perp},\;\bm{u},\bm{v}\in\mathbb{Z}^{n}.$ (70)

The residual error can be considered as living on the scaled $q$-ary lattice

$\mathcal{L}_{q}=\frac{1}{\sqrt{\lambda q}}\mathbb{Z}^{2n}_{q}$ (71)

dual to the trivial stabilizer lattice and has a probability distribution
induced by the trivial syndrome and correction

$P\left(\bm{e}^{\prime}\right)\propto\sum_{\bm{t}\in\mathcal{L}_{\rm
triv}}e^{-\frac{\left(\bm{e}^{\prime}+\bm{s}_{\rm
triv}+\bm{t}\right)^{2}}{2\overline{\sigma}^{2}}}.$ (72)

The remaining syndrome is

$\displaystyle\bm{s}$ $\displaystyle=MJ\bm{e}^{\prime}\mod 1$
$\displaystyle=\frac{1}{q}\begin{pmatrix}\bm{v}-A\left(h\right)\bm{u}\mod q\\\
0\mod 1\end{pmatrix}.$ (73)

In the first block of the syndrome
$q\bm{s}_{1}=\bm{v}-A\left(h\right)\bm{u}\mod q$ we recognize the structure of
the NTRU cipher-text. The position of the message is taken by $\bm{m}=\bm{v}$
and the random vector is replaced by $\bm{r}=-\sigma(\bm{u})$. Following the
standard NTRU decryption process now allows to obtain $\bm{v}\mod q\mod p$ as
well as

$\bm{u}=qA^{\sigma}\left(h^{-1}\right)(\bm{v}-q\bm{s}_{1})\mod q$ (74)

when $h$ is also chosen to by invertible in $R_{q}$ with inverse $h^{-1}$.
When $p$ is not prime, we can instead obtain $\bm{u}\mod q\mod p_{i}$ for each
prime factor $p_{i}$ of $p$ and estimate $\bm{u}\mod q$ via the Chinese
remainder theorem. We refer to this decoding routine as NTRUDecode and provide
some small scale numerical tests in appendix B.

Alternatively, we can decompose the remaining syndrome as

$q\bm{s}=\begin{pmatrix}\bm{v}\\\
-\bm{u}\end{pmatrix}+\underbrace{\begin{pmatrix}-A\left(h\right)\bm{u}\\\
\bm{u}\end{pmatrix}}_{\in\mathcal{L}_{\rm cs}^{J}},$ (75)

where the vector on the RHS is element of the flipped NTRU lattice generated
by the public basis

$H^{J}=\begin{pmatrix}qI&0\\\ -A\left(h\right)&I\end{pmatrix}.$ (76)

Equation (75) shows that a likely, i.e., small, error vector
$\begin{pmatrix}\bm{v}\\\ -\bm{u}\end{pmatrix}$ can indeed be obtained by
solving $\mathrm{CVP}\left(\mathcal{L}^{J},q\bm{s}\right)$. In appendix B, we
implement an approximation of this CVP instance using Babai’s nearest plane
algorithm with the HKZ reduced flipped public basis as BabaiDecode again only
for small parameters $n$.

We recognize that the solving CVP on the respective NTRU lattices provides a
viable route to decoding. To analyze how well decoding via CVP can be carried
out efficiently when provided only the public- vs. the secret basis, we
analyze the radius $\epsilon$, up to which $\mathtt{BDD}_{\epsilon}$ can be
implemented given the respective bases.

###  5.1 Bounding $\mathtt{BDD}_{\epsilon}$

The maximum $\mathtt{BDD}_{\epsilon}$-radius achieved by using Babai’s nearest
plane algorithm using this basis
$B=\left(\bm{b}_{1}^{T}\dots\bm{b}_{2n}^{T}\right)^{T}$ is given by

$\epsilon=\frac{1}{2}\min_{i}\|\bm{\tilde{b}}_{i}\|,$ (77)

where we write
$\tilde{B}=({\bm{\tilde{b}}_{1}^{T},\dots,\bm{\tilde{b}}_{2n}^{*T}})^{T}$ for
the Gram-Schmidt orthogonalization of $B$.

The secret key pair $(f,g)$ can be extended to a full rank secret basis [55,
56, 50]

$\displaystyle B_{R}=$ $\displaystyle\begin{pmatrix}f&g\\\ F&G\end{pmatrix}\in
R^{2\times 2}$ (78) $\displaystyle\mapsto
B_{\mathbb{Z}}=\begin{pmatrix}C_{\Phi}\left(f\right)&C_{\Phi}\left(g\right)\\\
C_{\Phi}\left(F\right)&C_{\Phi}\left(G\right)\end{pmatrix}\in\mathbb{Z}^{2n\times
2n},$ (79)

which constitutes an equivalent lattice basis in $R^{2}$ if $F,G\in R$ are
such that $fG-gF=q\in R$, that is if

$\displaystyle B_{R}JB_{R}^{T}$ $\displaystyle=\begin{pmatrix}f&g\\\
F&G\end{pmatrix}\begin{pmatrix}0&1\\\ -1&0\end{pmatrix}\begin{pmatrix}f&F\\\
g&G\end{pmatrix}$ $\displaystyle=\begin{pmatrix}0&fG-gF\\\ gF-
fG&0\end{pmatrix}=qJ$ (80)

is symplectic in $R^{2}$. The vector $(F,G)\in R^{2}$ is typically chosen to
be the minimal representative modulo multiples of $(f,g)$ in $R$ and can be
approximated efficiently using Babai’s algorithm [55, 56, 50]. By applying the
circulant homomorphism, this secret basis is mapped to a secret basis for the
lattice in $\mathbb{Z}^{2n}$ on which the GKP-NTRU lattice is defined – note
that the symplectic basis obtained from the public key, eq. (59) is obtained
from this by a rotation and change of basis using $\sigma_{\Phi}$. Due to this
simple relationship, we perform the following analysis in the non-rotated
basis w.l.o.g. .

By leveraging symplecticity, we can derive lower bounds on the BDD-radius
achieved using this secret basis. By comparing this to solving BDD when the
input public basis is $\delta$-LLL reduced, we obtain an almost exponential
separation between the BDD radius provided by the public and private basis.

######  Proposition 3.

Let $q\geq n$. Using the secret basis

$B=\begin{pmatrix}C_{\Phi}(f)&C_{\Phi}(g)\\\
C_{\Phi}(F)&C_{\Phi}(G)\end{pmatrix},$ (81)

Babai’s algorithm solves $\mathtt{BDD}_{\epsilon}$ with

$\epsilon_{B}\geq
q\left(2\max\left\\{\|\left(\bm{f},\bm{g}\right)\|,\|\left(\bm{F},\bm{G}\right)\|\right\\}\right)^{-1},$
(82)

which is on a scale of $O\left(1/\sqrt{n}\right)$, while using the
$\delta$-LLL reduced public basis obtained from

$H=\begin{pmatrix}I&C_{\Phi}(h)\\\ 0&qI\end{pmatrix},$ (83)

we have

$\epsilon_{H}\leq\frac{\lambda_{1}\left(L\right)}{2}e^{-\sqrt{n\ln{\left(q\right)}\ln{\left(1/\delta\right)}}},$
(84)

which is on a scale of $o({e^{-\sqrt{n\ln{n}\ln{\left(1/\delta\right)}}}})$.

###### Proof.

We define the conjugation of polynomials $R\mapsto
R:\;f\mapsto\overline{f}\Leftrightarrow\bm{f}\mapsto\sigma_{\Phi}\bm{f}$ such
that $C_{\Phi}(\overline{f})=C_{\Phi}(f)^{T}$. Using the homomorphism to
circulants we have that

$\displaystyle B_{\mathbb{Z}}$
$\displaystyle=\begin{pmatrix}C_{\Phi}(f)&C_{\Phi}(g)\\\
C_{\Phi}(F)&C_{\Phi}(G)\end{pmatrix},$ (85)
$\displaystyle\overline{B}_{\mathbb{Z}}$
$\displaystyle=\begin{pmatrix}C_{\Phi}(\overline{f})&C_{\Phi}(\overline{g})\\\
C_{\Phi}(\overline{F})&C_{\Phi}(\overline{G})\end{pmatrix},$ (86)
$\displaystyle
B_{\mathbb{Z}}J\left(\frac{1}{q}\overline{B}_{\mathbb{Z}}\right)^{T}$
$\displaystyle=J,$ (87)
$\displaystyle\left(\frac{1}{q}J^{T}\overline{B}_{\mathbb{Z}}\right)JB_{\mathbb{Z}}^{T}$
$\displaystyle=I,$ (88)

where the last line is obtained using the defining operation $fG-gF=q\in R$.
We will from now on omit the subscript Z. This equation identifies the
canonical symplectic dual of the basis $B_{\mathbb{Z}}$ as

$B^{\perp}=\frac{1}{q}J^{T}\overline{B},$ (89)

which is related to the canonical euclidean dual by a $J-$rotation [12]

$B^{*}=B^{\perp}J=\frac{1}{q}J^{T}\overline{B}J.$ (90)

Let $\tilde{B}=\mathtt{GS}\left(B\right)$ the Gram-Schmidt diagonalization of
$B$ and

$\hat{B^{*}}=R_{2n}^{T}\mathtt{GS}\left(R_{2n}B^{*}\right)=\frac{1}{q}R_{2n}^{T}\mathtt{GS}\left(R_{2n}J^{T}\overline{B}\right)J,$
(91)

the Gram-Schmidt diagonalization of the canonical euclidean dual $B^{*}$ in
reverse order, where $R_{i,j}=\delta_{n-i,j}$ and $R_{2n}=R\oplus R$. We have
that

$\|\bm{\tilde{b}}_{i}\|\|\bm{\hat{b^{*}}}_{i}\|=1\,\forall i,$ (92)

such that

$\min_{i}\|\bm{\tilde{b}}_{i}\|=\frac{1}{\max_{i}\|\bm{\hat{b^{*}}}_{i}\|}.$
(93)

The Gram-Schmidt norm is trivially upper bounded by

$\|\hat{B^{*}}\|_{\rm
GS}=\max_{i}\|\bm{\hat{b^{*}}}_{i}\|\leq\max\left\\{\|\left(\bm{f},\bm{g}\right)\|,\|\left(\bm{F},\bm{G}\right)\|\right\\}/q,$
(94)

such that we obtain

$\min_{i}\|\bm{\tilde{b}}_{i}\|\geq 1/\|\hat{B^{*}}\|_{\rm
GS}=q/\max\left\\{\|\left(\bm{f},\bm{g}\right)\|,\|\left(\bm{F},\bm{G}\right)\|\right\\}.$
(95)

This lower bound on the Gram-Schmidt norm of the secret basis is large, when
the secret key pairs $(f,g),(F,G)$, with length on a scale of
$O\left(\sqrt{n}\right)$ are short relative to $q\geq n$, which is expected to
be the case by construction of the cryptosystem. This bound yields a BDD
radius of $\epsilon_{B}\sim O\left(1/\sqrt{n}\right)$

We compare this to the bound obtained from the public basis, when the input
basis $H$ is $\delta$-LLL reduced [57]. Building on an argument by Eldar and
Hallgreen, Ducas and van Woerden [58, 59] have shown that for a $q$-ary
lattice (for $q=c^{n}$), Babai’s algorithm can solve BDD up to

$\epsilon_{H}=\frac{\lambda_{1}\left(L\right)}{2}e^{-\sqrt{n\ln{\left(q\right)}\ln{\left(1/\delta\right)}}},$
(96)

which has also been extended to general $q$ in ref. [60]. ∎

###  5.2 Quantum public key communication from NTRU-GKP codes

In addition to its usual use as a QECC, the fact that the NTRU-GKP codes have
the additional property that decoding for a stochastic displacement noise
model is tightly related to decrypting the NTRU cryptosystem suggests that the
NTRU-GKP codes presented here may be used for both, quantum error correction
and a new kind of quantum public key communication scheme at the same time.
One may interpret NTRU-GKP codes as trapdoor decodable quantum error
correcting codes. That is, while stabilizer measurements can be performed and
code states prepared using only access to the public key $h$, knowledge of the
corresponding secret keys $\left(f,g\right)$ of the NTRU cryptosystem is
necessary for reliable and efficient decoding. In the following we outline how
instances of the NTRU-GKP code can be used to set up a _private quantum
channel_ [61] with quantum information being sent from Bob to Alice, in that
quantum information is transmitted in a fashion that is oblivious to an
eavesdropper with limited computational power who has access to the physical
quantum channel used for transmission.

The workings of the here proposed cryptosystem is similar to that of a _one
time pad_ (OTP), where every OTP instance corresponds to a random displacement
error applied to an NTRU-GKP code instance such that the syndrome of the
random displacement error encodes a ciphertext of the NTRU scheme. The
security of this scheme under the assumption that decoding a quantum error
correcting code – i.e., finding small errors that are consistent with the
syndrome – is necessary to retrieve its logical content is then immediately
inherited from the corresponding classical NTRU cryptosystem. While we have
carried out most of our exposition with the only heuristically secure version
of the NTRU cryptosystem originally presented in ref. [15] with quotient
$\Phi_{0}=x^{n}-1$ and secret key sampling from the uniform binary
distributions $D(d_{1},d_{2})\subseteq\left\\{-1,0,+1\right\\}^{n}$, we have
also shown that NTRU-GKP codes can be constructed using irreducible quotients
$\Phi=x^{n}+1$, $n$ a power of $2$, and $q\geq\mathrm{poly}(n)$ while secret
key pairs are sampled from discrete Gaussian distributions. This is the
setting chosen for a provably secure version of the NTRU cryptosystem
discussed in ref. [50], where the public key is shown to be pseudorandom and
security is inherited from the (average case) hardness of the ring based
$\mathtt{R-SIS}$ and $\mathtt{R-LWE}$ problem.

The public key protocol, also described in fig. 4 is sketched as follows:

  1. 1.

Alice samples a secret key pair $(f,g)$ and computes the public key $h$, which
is communicated to Bob.

  2. 2.

Bob produces a code state described by the GKP code using the basis
$\sqrt{({\lambda}/{q})}H(h)$ and samples an error corresponding to a random
message $\bm{e}_{0}=(-\bm{r},\bm{m})/\sqrt{\lambda q}$, according to the
specifications of the NTRU cryptosystem, by which he displaces the state. He
transmits the state to Alice.

  3. 3.

Alice measures the stabilizers and decodes the state, e.g., via the NTRU
decryption routine or by employing Babai’s algorithm as outlined before using
the secret key pair $(f,g)$. She has hence received the to her unknown state
from Bob through the error corrected private quantum channel.

Figure 4: Outline of the private quantum channel established using the NTRU-
GKP code as described in the main text.

To our knowledge, this setup presents a new paradigm of quantum cryptographic
protocols. We summarize points in support of its security.

#### Necessity to decode.

In order to unambiguously obtain the logical code state, it is necessary to
find a correction $\bm{e^{\prime}}$ consistent with the syndrome such that
$\|\bm{e}_{0}+\bm{e^{\prime}}\|\leq\Delta/2$. Since
$\|\bm{e}_{0}\|_{\infty}\leq 1/\sqrt{\lambda q}$ and the smallest element in
$\mathcal{L}^{\perp}$ is of length $\Delta$, this amounts to decrypting the
NTRU ciphertext in the syndrome to identify $\bm{e}_{0}$. Towards a first
cryptanalysis, we examine to which degree an adversary is able to distinguish
a quantum ciphertext. Let $\ket{\overline{\psi}}$ be a logical code state
vector specified by a GKP-NTRU code with lattice $\mathcal{L}$. We examine the
eigenvalue of logical Pauli observables obtained when the initial code state
is encrypted by applying the random displacement $D\left(\bm{e}_{0}\right)$, a
syndrome $\bm{s}\left(e_{0}\right)=MJ\bm{e}_{0}\mod 1$ is obtained and a
generic correction via $\bm{\eta}=(MJ)^{-1}\bm{s}\left(\bm{e}_{0}\right)$ is
applied. With

$\displaystyle M^{-1}=\frac{1}{\sqrt{\lambda
q}}\begin{pmatrix}qI&-A_{\Phi}\left(h\right)\\\ 0&I\end{pmatrix},$ (97)

this yields a generic correction

$\displaystyle\bm{\eta}=\frac{1}{\sqrt{\lambda q}}\begin{pmatrix}0\\\
\bm{c},\end{pmatrix}$ (98)

where $\bm{c}=\bm{m}+A_{\Phi}(h)\bm{r}\mod q$ is the associated NTRU
ciphertext. The total remaining error after correction thus is

$\displaystyle\bm{e}_{0}-\bm{\eta}=\frac{-1}{\sqrt{\lambda
q}}\begin{pmatrix}\bm{r}\\\
\bm{c}-\bm{m}\end{pmatrix}=\begin{pmatrix}\bm{r}\\\ A_{\Phi}(h)\bm{r}\mod
q\end{pmatrix}.$ (99)

We compute

$M^{\perp}J\left(\bm{e}_{0}-\bm{\eta}\right)=\frac{1}{\lambda}\begin{pmatrix}0\\\
\bm{r}\end{pmatrix}\mod q/\lambda,$ (100)

which shows that for an input code state vector $\ket{\overline{\psi}}$, after
encoding and generic correction, the eigenvalues of logical Pauli operators
corresponding to rows $i=n+1,\dots,2n$ in $M^{\perp}$ obtain a random phase
$e^{i\frac{2\pi}{\lambda}r_{i-n}}$. This observation suggests that, for
$\lambda=2$, without access to the random string $\bm{r}$ embedded in the NTRU
ciphertext in every instance, the quantum state is effectively projected onto
a state that is diagonal in the logical Pauli-$Z$ basis and quantum
superpositions are washed out. This situation is similar to that of half a
quantum OTP, where only one type (either $X$ or $Z$) of Pauli operators is
used in the encryption.

#### Orthogonality.

For a fixed quantum state vector $\ket{\overline{\psi}}$, different error
realizations $D\left(\bm{e}_{0}\right)$ where $\|\bm{e}_{0}\|<\Delta/2$ map
the state to mutually orthogonal states (sectors of the QECC). This is
guaranteed by the quantum error correction conditions. Without applying
suitable corrections, separate encodings of the same logical quantum state
vector $D\left(\bm{e}_{i}\right)\ket{\overline{\psi}}$ are expected to appear
uncorrelated.

We leave a further study of the degree of quantum security of this scheme as
challenge for future work. It is important to stress that the security of this
scheme is not based on information theoretic arguments, but on computational
limitations of an eavesdropper, giving rise to a new situation in quantum
cryptography. For a practical security analysis it would be furthermore
meaningful to study how potential security claims can sustain when also
considering the finite squeezing error present in physical GKP states [7, 62].

In addition to the possibility of obtaining a classical public key private
quantum channel by this construction, this scheme is also expected to be
tolerant against additional errors imposed by the channel. Additional
displacement errors would effectively change the “quantum encoded” NTRU
ciphertext as encoded in the syndrome, but as long as the additional error
together with the initial random displacement implemented by Bob are
sufficiently smaller than the euclidean code distance, the transmitted logical
quantum state is still expected to be decoded correctly.

As computation and transmission of quantum information encoded in GKP codes
using photonics and integrated optics is becoming technologically ever more
developed, this setup is interesting for the reason that to transmit quantum
information one would potentially use a (bosonic) quantum error correcting
codes anyways. Our construction highlights that this can be done with in-built
security options without explicitly concatenating the encoded qubits into a
separate cryptographic protocol.

##  6 Conclusion and outlook

In this work, we have introduced the randomized construction of good GKP codes
using the NTRU cryptosystem and discussed how a decoder for these codes can be
obtained from variations of the NTRU decryption process.

We have discussed the use of these codes in a public key quantum communication
scheme where we expect to inherit a conditional security guarantee from the
original cryptosystem. This defines a trapdoor decodable quantum error
correcting code for which the core idea is that we can provide “bad” bases for
suitably chosen GKP codes that allow an agent to prepare code states and
measure stabilizers but –without access to a “good” secret basis – require
exponential overhead to decode the syndrome. We leave as open challenge to
either prove or disprove the quantum security of our scheme. More broadly,
this idea also opens the door to potential client-server schemes where a
client requests a server – capable of preparing GKP states and carry out
Gaussian operations – to carry out computations on client-specified GKP codes
and measure stabilizer syndromes without giving the server the power to decode
efficiently to apply logical corrections.

It is also worth mentioning that the NTRU cryptosystem has multi-key
homomorphic properties with respect to adding and multiplying the message- and
random bit-strings [63]. Beyond the scope of this work, we expect it to be
possible to leverage these homomorphic properties to design more advanced
NTRU-GKP codes for the secure and error corrected transmission of quantum
states. Effective NTRU-lattices derived from products of public/secret keys
correspond to non-principal ideals of the underlying ring, which makes for an
interesting generalization of our setting. Alternatively, it would also be
interesting to examine symplecticity for higher rank module lattices. Higher
rank module lattices over polynomial rings have previously found application
in quantum error correction, e.g., in the work of Pantaleev and Kalachev [24]
to construct high distance quantum LDPC codes, who consider binary polynomial
rings with quotient $\Phi_{0}=x^{l}-1$ and where the element-wise homomorphism
of basis elements of the $R$-module basis to circulants is termed lift.

On the _hardware level_ , we also expect that the cyclic structure of these
codes can be helpful in the design of modular stabilizer-measurement
architectures with a fixed stabilizer-measurement gadget that is coupled to
the data modes with shifted mode-index and at alternating delay. The short
length of the corresponding displacements when the stabilizers generators are
measured in the secret basis implies a reduced overhead in required
interaction time/strength when the required connectivity is present and
further highlights a physical advantage in having access to the secret basis
for several meaningful physical platforms.

For future work, it would be interesting to improve on the decoders, such as
adapting our proposition of BabaiDecode by adapting Babai’s nearest plane
algorithm to include information about the biased input error distribution eq.
(72), to design a better approximation to MLD decoding NTRU-GKP codes and
provide numerical studies for large $n$.

We have highlighted the complexity of decoding GKP codes as an interesting
subject to study and we expect that, using concatenation, computational
complexity questions on the GKP-lattice level can be put into tighter
relationships with corresponding problems in qubit-codes and equivalent
questions in classical error correction. It would further be interesting to
identify other ideal lattices that can be used to construct GKP codes.

Finally, it is worth mentioning that the relationship between GKP quantum
error correction and cryptography runs even deeper. Physical, i.e.,
normalizable, realizations of GKP states obey a phase-space probability
distribution very similar to that of a discrete lattice Gaussian distribution.
Quantum states as such, and the ability to produce and sample from them, play
a central role in the quantum reduction from SVP to the learning with errors
problem [64]. Given the ability to efficiently prepare approximate GKP-state
by measuring its stabilizers, we leave as final open question in how far it is
possible to sample from discrete lattice Gaussian distributions using
physically preparable GKP states.

## Acknowledgements

We thank Victor V. Albert, Yusuf Alnawakhtha, Francesco Arzani, Nikolas P.
Breuckmann, Steven T. Flammia, Cica Gustiani, Florian Hirsch, John Preskill,
Manasi Shingane, Vincent Ulitzsch, and Daochen Wang for many helpful and
inspiring discussions. We thank Henning Seidler for constructive feedback on
parts of an early version of the manuscript and Nathan Walk for many helpful
comments on a later version. JC thanks the Joint Center for Quantum
Information and Computer Science (QuICS) at the University of Maryland for
their kind hospitality during the final preparation stages of this project and
many stimulating discussions. During preparation of this manuscript JC was
also temporarily affiliated with the AWS CQC and Caltech, which he also thanks
for their hospitality.

We gratefully acknowledge support from the BMBF (RealistiQ, MUNIQC-Atoms,
PhoQuant, QPIC-1, and QSolid), the DFG (CRC 183, project B04, on entangled
states of matter), the Munich Quantum Valley (K-8), as well as the Einstein
Research Unit on quantum devices, for which this is an inter-node joint
project.

## References

  * [1] D. Gottesman, A. Kitaev, and J. Preskill.  “Encoding a qubit in an oscillator”.  Phys. Rev. A 64, 012310 (2001).
  * [2] J. E. Bourassa, R. N. Alexander, M. Vasmer, A. Patil, I. Tzitrin, T. Matsuura, D. Su, B. Q. Baragiola, S. Guha, G. Dauphinais, and et al.  “Blueprint for a scalable photonic fault-tolerant quantum computer”.  Quantum 5, 392 (2021).
  * [3] S. Bartolucci, P. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, F. Pastawski, T. Rudolph, and C. Sparrow.  “Fusion-based quantum computation” (2021).  arXiv:2101.09310.
  * [4] A. L. Grimsmo and S. Puri.  “Quantum error correction with the Gottesman-Kitaev-Preskill code”.  PRX Quantum 2, 020101 (2021).
  * [5] V. V. Albert, K. Noh, K. Duivenvoorden, D. J. Young, R. T. Brierley, P. Reinhold, C. Vuillot, L. Li, C. Shen, S. M. Girvin, B. M. Terhal, and L. Jiang.  “Performance and structure of single-mode bosonic codes”.  Phys. Rev. A97 (2018).
  * [6] K. Noh, V. V. Albert, and L. Jiang.  “Quantum capacity bounds of Gaussian thermal loss channels and achievable rates with Gottesman-Kitaev-Preskill codes”.  IEEE Trans. Inf. Th. 65, 2563–2582 (2019).
  * [7] B. M. Terhal, J. Conrad, and C. Vuillot.  “Towards scalable bosonic quantum error correction”.  Quant. Sc. Tech. 5, 043001 (2020).
  * [8] J. Hastrup and U. L. Andersen.  “Analysis of loss correction with the Gottesman-Kitaev-Preskill code” (2021).  arXiv:2112.01425.
  * [9] C. Vuillot, H. Asasi, Y. Wang, L. P. Pryadko, and B. M. Terhal.  “Quantum error correction with the toric Gottesman-Kitaev-Preskill code”.  Phys. Rev. A 99, 032344 (2019).
  * [10] K. Noh, S. M. Girvin, and L. Jiang.  “Encoding an oscillator into many oscillators”.  Phys. Rev. Lett. 125, 080503 (2020).
  * [11] J. W. Harrington.  “Analysis of quantum error-correcting codes: Symplectic lattice codes and toric codes”.  PhD thesis.  California Institute of Technology.  (2004).
  * [12] J. Conrad, J. Eisert, and F. Arzani.  “Gottesman-Kitaev-Preskill codes: A lattice perspective”.  Quantum 6, 648 (2022).
  * [13] B. Royer, S. Singh, and S. M. Girvin.  “Encoding qubits in multimode grid states”.  PRX Quantum 3, 010335 (2022).
  * [14] F. Schmidt and P. van Loock.  “Quantum error correction with higher Gottesman-Kitaev-Preskill codes: Minimal measurements and linear optics”.  Phys. Rev. A 105, 042427 (2022).
  * [15] J. Hoffstein, J. Pipher, and J. H. Silverman.  “NTRU: A ring-based public key cryptosystem”.  In J. P. Buhler, editor, Algorithmic Number Theory.  Page 267–288.  Lecture Notes in Computer ScienceBerlin (1998). Springer.
  * [16] J. Harrington and J. Preskill.  “Achievable rates for the Gaussian quantum channel”.  Phys. Rev. A 64, 062301 (2001).
  * [17] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill.  “Topological quantum memory”.  J. Math. Phys. 43, 4452–4505 (2002).
  * [18] L. Babai.  “On Lovász’ lattice reduction and the nearest lattice point problem”.  Combinatorica 6, 1–13 (1986).
  * [19] D. Micciancio.  “CSE 206A: Lattice algorithms and applications”.  url: http://cseweb.ucsd.edu/classes/wi10/cse206a/.
  * [20] J. Preskill.  “Lecture notes in quantum error correction”.  http://theory.caltech.edu/~preskill/ph229/notes/chap7.pdf (2009).
  * [21] A. R. Calderbank and P.W. Shor.  “Good quantum error-correcting codes exist”.  Phys. Rev. A 54, 1098–1105 (1996).
  * [22] D. Bacon, S.T. Flammia, A. W. Harrow, and J. Shi.  “Sparse quantum codes from quantum circuits”.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing.  Page 327–334.  STOC ’15New York, NY, USA (2015). Association for Computing Machinery.
  * [23] P. Panteleev and G. Kalachev.  “Asymptotically good quantum and locally testable classical ldpc codes” (2021).
  * [24] P. Panteleev and G. Kalachev.  “Quantum LDPC codes with almost linear minimum distance”.  IEEE Trans. Inf. Th. 68, 213–229 (2022).
  * [25] N. P. Breuckmann and J. N. Eberhardt.  “Balanced product quantum codes”.  IEEE Trans. Inf. Th. 67, 6653–6674 (2021).
  * [26] P. Sarnak and P. Buser.  “On the period matrix of a Riemann surface of large genus (with an Appendix by J. H. Conway and N. J. A. Sloane)”.  Invent. Math. 117, 27–56 (1994).
  * [27] S. Lang.  “Algebra”.  Graduate Texts in Mathematics. Springer New York. (2005).
  * [28] N. Gama, N. Howgrave-Graham, and P. Q. Nguyen.  “Symplectic lattice reduction and NTRU”.  In Serge Vaudenay, editor, Advances in Cryptology - Eurocrypt 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings.  Volume 4004 of Lecture Notes in Computer Science, pages 233–253.  Springer (2006).
  * [29] B. Q. Baragiola, G. Pantaleoni, R. N. Alexander, A. Karanjai, and N. C. Menicucci.  “All-Gaussian universality and fault tolerance with the Gottesman-Kitaev-Preskill code”.  Phys. Rev. Lett. 123, 200502 (2019).
  * [30] J. Conway and N. Sloane.  “Sphere packings, lattices and groups”.  Volume 290.  Springer, New York. (1988).
  * [31] J. Conway and N. Sloane.  “On the Voronoi regions of certain lattices”.  SIAM J. Alg. Dis. Meth.5 (1984).
  * [32] Y. Wang.  “Quantum error correction with the GKP code and concatenation with stabilizer codes” (2019).  arXiv:1908.00147.
  * [33] K. Fukui, A. Tomita, and A. Okamoto.  “Analog quantum error correction with encoding a qubit into an oscillator”.  Phys. Rev. Lett. 119, 180507 (2017).
  * [34] K. Noh and C. Chamberland.  “Fault-tolerant bosonic quantum error correction with the surface–Gottesman-Kitaev-Preskill code”.  Phys. Rev. A 101, 012316 (2020).
  * [35] N. Raveendran, N. Rengaswamy, F. Rozpedek, A. Raina, L. Jiang, and Vasic B.  “Finite rate QLDPC-GKP coding scheme that surpasses the CSS Hamming bound” (2021).  arXiv:2111.07029.
  * [36] O. Regev.  “Lecture Notes: Lattices in Computer Science”.  https://cims.nyu.edu/~regev/teaching/lattices_fall_2009/.  Online; accessed 05 December 2022.
  * [37] E. Berlekamp, R. McEliece, and H. van Tilborg.  “On the inherent intractability of certain coding problems (corresp.)”.  IEEE Trans. Inf. Th. 24, 384–386 (1978).
  * [38] A. Vardy.  “The intractability of computing the minimum distance of a code”.  IEEE Trans. Inf. Th. 43, 1757–1766 (1997).
  * [39] M.-H. Hsieh and F. Le Gall.  “NP-hardness of decoding quantum error-correction codes”.  Phys. Rev. A 83, 052331 (2011).
  * [40] P. Iyer and D. Poulin.  “Hardness of decoding quantum stabilizer codes”.  IEEE Trans. Inf. Theor. 61, 5209–5223 (2015).
  * [41] M. Ajtai.  “Generating hard instances of lattice problems (extended abstract)”.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing.  Page 99–108.  STOC ’96New York, NY, USA (1996). Association for Computing Machinery.
  * [42] J. Silverman.  “Lecture notes: An introduction to lattices, lattice reduction, and lattice-based cryptography”.  https://www.ias.edu/sites/default/files/Silverman_PCMI_Note_DistributionVersion_220705.pdf.  Online; accessed 05 December 2022.
  * [43] Y. Aono, Espitau T., , and Q. Ngyuen P.  “Random lattices: Theory and practice”.  https://espitau.github.io/bin/random_lattice.pdf.
  * [44] A. M. Macbeath and C. A. Rogers.  “A modified form of Siegel’s mean value theorem. II”.  Mathematical Proceedings of the Cambridge Philosophical Society 54, 322–326 (1958).
  * [45] D. Coppersmith and A. Shamir.  “Lattice attacks on NTRU”.  In Advances in Cryptology - EUROCRYPT ’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 11-15, 1997, Proceeding.  Volume 1233 of Lecture Notes in Computer Science, pages 52–61.  Springer (1997).
  * [46] A. May.  “Auf Polynomgleichungen basierende Public-Key-Kryptosysteme” (1999).
  * [47] A. May.  “Cryptanalysis of NTRU” (1999).  preprint.
  * [48] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters.  “Mixed-state entanglement and quantum error correction”.  Phys. Rev. A 54, 3824–3851 (1996).
  * [49] D. J. Bernstein, J. Buchmann, and Dahmen E.  “Post-quantum cryptography”.  Springer Berlin Heidelberg. Berlin, Heidelberg (2009).
  * [50] D. Stehlé and R. Steinfeld.  “Making ntru as secure as worst-case problems over ideal lattices”.  In K. G. Paterson, editor, Advances in Cryptology – EUROCRYPT 2011.  Pages 27–47.  Berlin, Heidelberg (2011). Springer Berlin Heidelberg.
  * [51] S. Halevi and T. Malkin.  “Lecture Notes: Lattices and homomorphic encryption, Spring 2013”.  https://www.cs.columbia.edu/~tal/6261/SP13/.  Online; accessed 04 December 2022.
  * [52] V. Lyubashevsky and D. Micciancio.  “Generalized compact knapsacks are collision resistant”.  In Proceedings of the 33rd International Conference on Automata, Languages and Programming - Volume Part II.  Page 144–155.  ICALP’06Berlin, Heidelberg (2006). Springer-Verlag.
  * [53] J. Bi and Q. Cheng.  “Lower bounds of shortest vector lengths in random knapsack lattices and random NTRU lattices”.  Cryptology ePrint Archive, Paper 2011/153 (2011).  https://eprint.iacr.org/2011/153.
  * [54] J. Bi and Q. Cheng.  “Lower bounds of shortest vector lengths in random NTRU lattices”.  Th. Comp. Sc. 560, 121–130 (2014).
  * [55] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte.  “NTRUSign: Digital signatures using the NTRU lattice”.  In M. Joye, editor, Topics in Cryptology — CT-RSA 2003.  Pages 122–140.  Berlin, Heidelberg (2003). Springer Berlin Heidelberg.
  * [56] L. Ducas, V. Lyubashevsky, and T. Prest.  “Efficient identity-based encryption over NTRU lattices”.  In P. Sarkar and T. Iwata, editors, Advances in Cryptology – ASIACRYPT 2014.  Pages 22–41.  Berlin, Heidelberg (2014). Springer Berlin Heidelberg.
  * [57] A. Lenstra, H. Lenstra, and L. Lovász.  “Factoring polynomials with rational coefficients”.  Math. Ann. 261, 515–534 (1982).
  * [58] L. Eldar and S. Hallgren.  “An efficient quantum algorithm for lattice problems achieving subexponential approximation factor” (2022).
  * [59] L. Ducas and W. van Woerden.  “A note on a claim of eldar & hallgren: Lll already solves it”.  Cryptology ePrint Archive, Paper 2021/1391 (2021).  https://eprint.iacr.org/2021/1391.
  * [60] R. Allen, R. E. Berker, S. Casacuberta, and M. Gul.  “Quantum and classical algorithms for bounded distance decoding”.  Cryptology ePrint Archive, Paper 2022/195 (2022).  https://eprint.iacr.org/2022/195.
  * [61] A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf.  “Private quantum channels”.  IEEE Symp. Found. Comp. Sc.Page 547–553 (2000).
  * [62] I. Tzitrin, J. E. Bourassa, N. C. Menicucci, and K. K. Sabapathy.  “Progress towards practical qubit computation using approximate gottesman-kitaev-preskill codes”.  Phys. Rev. A 101, 032315 (2020).
  * [63] A. López-Alt, E. Tromer, and V. Vaikuntanathan.  “On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption”.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing.  Page 1219–1234.  STOC ’12New York, NY, USA (2012). Association for Computing Machinery.
  * [64] O. Regev.  “On lattices, learning with errors, random linear codes, and cryptography”.  In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing.  Page 84–93.  STOC ’05New York, NY, USA (2005). Association for Computing Machinery.
  * [65] The Sage Developers, W. Stein, D. Joyner, D. Kohel, J. Cremona, and B. Eröcal.  “Sagemath, version 9.6”.  http://www.sagemath.org (2022).
  * [66] https://github.com/JonCYeh/NTRUGKP.git.
  * [67] D. J. Bernstein, N. Heninger, and T. Lange.  “LatticeHacks”.  https://latticehacks.cr.yp.to/ntru.html.

##  Appendix A Thresholds of GKP codes

In this section, we sketch how the existence and value of a threshold for a
GKP code family can be analyzed using the lattice theta function. For
simplicity, assume a zero syndrome $\bm{s}=0$ on a lattice $\mathcal{L}_{n}$
that is part of a family of lattices scaling with $n$. The probability for the
state to be in the $\bm{\xi}^{\perp}_{n}=0$ coset is given by
$P([\bm{\xi}^{\perp}_{n}]|0)=\Theta_{\mathcal{L}_{n}}(z)/\Theta_{\mathcal{L}^{\perp}_{n}}(z)$,
where

$\Theta_{\mathcal{L}^{\perp}_{n}}(z)=\sum_{\bm{\xi}^{\perp}_{n}\in\mathcal{L}^{\perp}_{n}/\mathcal{L}_{n}}\Theta_{\mathcal{L}_{n}+\bm{\xi}^{\perp}_{n}}(z)$
(101)

denotes the probability to be in any logical coset and
$z={i}/({2\pi\sigma^{2}})$. A necessary condition for a GKP code family to
exhibit a threshold is satisfied if there exists $z^{*}\in i\mathbb{R}$ such
that for any $|z|>|z^{*}|,\,z\in i\mathbb{R}$, it holds that

$0=\lim_{n\rightarrow\infty}\Theta_{\mathcal{L}^{\perp}_{n}}(z)-\Theta_{\mathcal{L}_{n}}(z)=\lim_{n\rightarrow\infty}\sum_{\bm{\xi}^{\perp}_{n}\in\mathcal{L}^{\perp}_{n}\setminus\mathcal{L}_{n}}\Theta_{\mathcal{L}_{n}+\bm{\xi}^{\perp}_{n}}(z).$
(102)

We write

$\displaystyle\Theta_{\mathcal{L}_{n}+\bm{\xi}^{\perp}_{n}}(z)$
$\displaystyle=\sum_{\delta\in\mathcal{D}_{n}}N_{\delta}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n})q^{\delta}$
(103)
$\displaystyle=\sum_{\delta\in\mathcal{D}_{n}}\exp{\left\\{\delta\left(\delta^{-1}\ln(N_{\delta}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n}))-|\ln(q)|\right)\right\\}},$

where we have
$\mathcal{D}_{n}:=\\{\|\bm{x}\|^{2},\;\bm{x}\in\mathcal{L}_{n}+\bm{\xi}^{\perp}_{n})\\}$
and
$N_{\delta}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n})=\\#\\{\bm{x}\in\mathcal{L}_{n}+\bm{\xi}^{\perp}_{n}:\,\|\bm{x}\|^{2}=\delta\\}$.
We have that $\lambda_{1}\left(\mathcal{L}_{n}+\bm{\xi}^{\perp}_{n}\right)$
corresponds to a shortest representative of the logical coset given by
$\xi_{n}^{\perp}$, such that the threshold condition becomes

$\displaystyle 0$
$\displaystyle=\lim_{n\rightarrow\infty}\sum_{\xi^{\perp}_{n}\in\mathcal{L}^{\perp}_{n}\setminus\mathcal{L}_{n}}\sum_{\delta\in\mathcal{D}_{n}}\exp{\left\\{\delta\left(\delta^{-1}\ln(N_{\delta}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n}))-|\ln(q)|\right)\right\\}}$
(104)
$\displaystyle=\lim_{n\rightarrow\infty}\exp{\left\\{\Delta^{2}\left(\Delta^{-2}\ln(N_{\Delta^{2}}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n}))-|\ln(q)|\right)\right\\}}+...,$

where $\Delta$ is the Euclidean code distance of the code $\mathcal{L}_{n}$ as
defined in previous sections that we assume to grow with increasing $n$. Since
each term in the sum is positive, a necessary condition for asymptotic error
suppression becomes

$\displaystyle|\ln(q)|$
$\displaystyle>\Delta^{-2}\ln(N_{\Delta^{2}}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n}))$
(105) $\displaystyle\Leftrightarrow 2\sigma^{2}$
$\displaystyle<\Delta^{2}\ln^{-1}(N_{\Delta^{2}}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n})).$

Hence, under negligence of all higher order terms we can upper bound the
threshold as

$2\sigma^{*\,2}<\min_{\bm{\xi}^{\perp}_{n}\in\mathcal{L}^{\perp}_{n}/\mathcal{L}_{n}}\frac{\Delta^{2}}{\ln\left(N_{\Delta^{2}}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n})\right)},$
(106)

which shows the impact of the entropic contribution
$N_{\Delta^{2}}(\mathcal{L}_{n},\bm{\xi}^{\perp}_{n})$ on the potential
threshold.

##  Appendix B Numerical results on decoding NTRU-HPS

In this section we report some small scale numerical experiments we have
conducted on decoding the NTRU-GKP code (with $\Phi_{0}=x^{n}-1$) in the small
$n$ regime, where numerical experiments where feasible within the scope of
this work. The following codes are obtained as the NTRU lattice with the
largest shortest vector length amongst $100$ samples of NTRU key pairs
$(f,g)$, where each instance of the SVP problem is solved by full HKZ
reduction. We aim at correcting errors up to a standard deviation
$\overline{\sigma}^{*}=\sigma^{*}/\sqrt{2\pi}$ with physical standard
deviation of $\sigma^{*}=0.1$. By solving for $n,q$ in
$\Delta/2\geq\sqrt{2n\overline{\sigma}^{2}}$ using the bound in theorem 2, we
trial $q=8$ as a reasonable parameter.

The parameters of the codes we obtained are summarized in fig. 5. For
comparison, notice that a standard square GKP code concatenated with a small
$[\\![n,1,3]\\!]$ qubit code has distance $\Delta=\sqrt{3/2}=1.22$ using
typically $n=5$ to $9$ qubits to encode a single logical qubit while here a
similar distance is achieved while encoding $k=n$ logical qubits.

$n,d,q,p$ | $\lambda_{1}\left(L_{\rm cs}\right)$ | $\Delta$
---|---|---
$7,2,8,3$ | $4$ | $1$
$11,3,8,3$ | $4.69$ | $1.17$
$17,5,8,3$ | $4.9$ | $1.23$
$23,7,8,3$ | $5.48$ | $1.37$
Figure 5: Parameters of sampled NTRU lattices.

Using these codes we simulate the error correction process on $N_{\rm
samples}=10^{5}$ Gaussian distributed errors with physical variance
$\sigma^{2}=2\pi\overline{\sigma}^{2}$. The data displayed in fig. 6 shows
$\sigma^{2}=2\pi\overline{\sigma}^{2}$ on the x-axis denoting the physical
variance of Gaussian displacements and $p_{\rm err}$ as the logical error rate
conditioned on successful decoding in the sense that the decoder successfully
undid the syndrome. We also plot $p_{\rm check}$, denoting the rate of
decoding failures, i.e., the rate by which the decoder fails to output an
error with the correct syndrome that is input to the decoder. The standard
deviation on the estimates for $p$ given by $\epsilon_{p}=\sqrt{p_{\rm
err}(1-p_{\rm err})/N_{\rm sample}}$ is included in the plots but due to the
sample number of $N_{\rm sample}=10^{5}$ is of negligible size. For
comparison, we also plot in black

$\displaystyle p(n,q,\sigma)$
$\displaystyle=1-\left[\int_{-\frac{\tilde{\Delta}}{2}}^{\frac{\tilde{\Delta}}{2}}\frac{e^{-\frac{x^{2}}{2\sigma^{2}}}}{\sqrt{2\pi\sigma^{2}}}dx\right]^{2n}$
(107)
$\displaystyle=1-\left[erf\left(\frac{\tilde{\Delta}}{2\sqrt{2}\sigma}\right)\right]^{2n},$
$\displaystyle\tilde{\Delta}$ $\displaystyle=\sqrt{\frac{2\pi}{2q}},$ (108)

which denotes the logical error probability of $n$ qudits with $d=2q$ encoded
into the trivial sub-lattice $\mathcal{L}_{\rm triv}=\sqrt{2q}\mathbb{Z}^{2n}$
corresponding to a hypercubic GKP code as well as in grey $p(n,1,\sigma)$,
corresponding to the logical error probability of $n$ square GKP codes each
encoding a single logical qubit. We further provide results for simulations of
NTRU-GKP codes separately sampled from distributions $b)$ and $c)$ as denoted
in fig. 3. The parameters listed below in fig. 7 reflect the codes simulated
in figs. 8, 9, 10.

In total, we make the following observations.

  * •

BabaiDecode has a rate of decoding failures matching $p(n,q,\sigma)$,
suggesting that decoding fails whenever the original error lies outside of the
Voronoi Cell of $\mathcal{L}_{\rm triv}^{\perp}=\mathbb{Z}/\sqrt{2q}$. When
decoding is successful, the logical error rate is negligible.

  * •

NTRUDecode consistently corrects successfully, i.e., returns the state to code
space, and has a conditional logical error rate that is smaller than
$p(n,q,\sigma)$. The logical error rate is however consistently larger than
that of $n$ square GKP codes, which is negligible in this parameter range. For
$\sigma\approx 1.13$ we observe a “threshold”-like behaviour in the transition
between the sampled $n=17$ and $n=23$ code.

  * •

There appears to be no significant difference which $p$ we choose.

The performance of these codes appears to be relatively poor when compared to
more conventional multi-mode codes, such as the _toric-GKP code_ [9], which we
expect to be mainly the case due to the extremely small $n,q$ parameter regime
we have simulated.

Further contributing factors to this observation may be that by decoding via
essentially MED decoders, we ignore a significant entropic contribution to the
optimal MLD problem. We have a number of minimal logical shifts
$N_{\Delta^{2}}\geq n$ since the lattice $\mathcal{L}$ is invariant under the
cyclic shift $T:\,T^{n}=I$, which is expected to be a relevant factor in the
full MLD decoding problem. Another factor is that the NTRU decryption process
used in NTRUDecode is in fact not tailored to a Gaussian distribution of
random bits, but rather is originally set up to decrypt a message hidden away
using random strings $\bm{r}$ sampled from an uniform distribution.
BabaiDecode improves upon this fact in spirit by employing the _nearest plane
algorithm_ in the decryption process, but ignores the biasing of the error
distribution, eq. (72), from the first step of the decoding routine which is a
necessary step in order to interpret the decryption process as a CVP.

It is interesting to observe that BabaiDecode consistently displays a
negligible logical error rate but quickly rises to high decoding failure rate,
which worsens as the code is scaled up and that for NTRUDecode we do observe a
parameter range where the decoder displays a lower logical error rate than
$p(n,q,\sigma)$. This shows that the decoder indeed non-trivially decodes
errors. Overall, it appears necessary to perform larger scale numerical
studies at large $n,q$ to examine the possibility of a threshold. The sagemath
[65] and python code as well as all numerical data presented here is publicly
available under ref. [66]. sagemath functionalities to construct NTRU lattices
are partially adapted from ref. [67].

Figure 6: Numerical results for the NTRU-GKP codes using the NTRU decryption
routine NTRUDecode (left) and BabaiDecode (right) for NTRU-GKP lattices where
$h$ is invertible. Here, the parameters $q=8$ and $p=3$ are fixed. $p_{\rm
err}$ (dots) denotes the the logical error rate conditioned on successful
decoding and $p_{\rm check}$ (stars) denotes the rate of decoding failures.

$n,d,q,p$ | $\lambda_{1}\left(L_{\rm cs}\right)$ | $\Delta$
---|---|---
$7,2,4,3$ | $2.65$ | $0.94$
$11,3,8,5$ | $3.32$ | $0.83$
$17,5,16,7$ | $4.12$ | $0.74$
$7,2,4,3$ | $2.65$ | $0.94$
$11,3,8,3$ | $3.32$ | $0.83$
$17,5,16,3$ | $4.12$ | $0.74$

$n,d,q,p$ | $\lambda_{1}\left(L_{\rm cs}\right)$ | $\Delta$
---|---|---
$7,2,4,3$ | $2.83$ | $1$
$11,3,8,5$ | $4.24$ | $1.06$
$17,5,16,7$ | $7.07$ | $1.24$
$7,2,4,3$ | $2.83$ | $1$
$11,3,8,3$ | $4.24$ | $1.06$
$17,5,16,3$ | $6.93$ | $1.23$

Figure 7: Lattice parameters for random NTRU lattices. The table on the right
summarizes the results when additionally $h$ is required to be invertible.
Figure 8: Numerical results for the NTRU-GKP codes using the NTRU decryption
routine BabaiDecode. (left) $p=3,5,7$ is running and (right) $p=3$ is fixed.
Figure 9:  Numerical results for the NTRU-GKP codes using the NTRU decryption
routine BabaiDecode for NTRU-GKP codes where $h$ is invertible. (left)
$p=3,5,7$ is running and (right) $p=3$ is fixed. Figure 10: Numerical results
for the NTRU-GKP codes using the NTRU decryption routine NTRUDecode for NTRU-
GKP lattices where $h$ is invertible. (left) $p=3,5,7$ is running and (right)
$p=3$ is fixed.