Further author information: (Send correspondence to M.S.)
E-mail<EMAIL_ADDRESS>
# Towards the MICADO@ELT PSF-R with simulated and real data

Matteo Simioni  INAF - Osservatorio Astronomico di Padova, Vicolo
dell’Osservatorio 5, Padova, Italy, I-35122  ADONI - Laboratorio Nazionale
Carmelo Arcidiacono  INAF - Osservatorio Astronomico di Padova, Vicolo
dell’Osservatorio 5, Padova, Italy, I-35122  Andrea Grazian  INAF -
Osservatorio Astronomico di Padova, Vicolo dell’Osservatorio 5, Padova, Italy,
I-35122  Marco Gullieuszik  INAF - Osservatorio Astronomico di Padova, Vicolo
dell’Osservatorio 5, Padova, Italy, I-35122  Elisa Portaluri  INAF -
Osservatorio Astronomico d’Abruzzo, Via Mentore Maggini, Teramo, Italy,
I-64100  Benedetta Vulcani  INAF - Osservatorio Astronomico di Padova, Vicolo
dell’Osservatorio 5, Padova, Italy, I-35122  Roland Wagner  Industrial
Mathematics Institute, Johannes Kepler University Linz, Altenberger Strasse
69, Linz, Austria, 4040  Anita Zanella  INAF - Osservatorio Astronomico di
Padova, Vicolo dell’Osservatorio 5, Padova, Italy, I-35122

###### Abstract

Observations close to the diffraction limit, with high Strehl ratios from
Adaptive Optics (AO)-assisted instruments mounted on ground-based telescopes
are a reality and will become even more widespread with the next generation
instruments that equip 30 meter-class telescopes. This results in a growing
interest in tools and methods to accurately reconstruct the observed Point
Spread Function (PSF) of AO systems. We will discuss the performance of the
PSF reconstruction (PSF-R) software developed in the context of the MICADO
instrument of the Extremely Large Telescope. In particular, we have recently
implemented a novel algorithm for reconstructing off-axis PSFs. In every case,
the PSF is reconstructed from AO telemetry, without making use of science
exposures. We will present the results coming from end-to-end simulations and
real AO observations, covering a wide range of observing conditions.
Specifically, the spatial variation of the PSF has been studied with different
AO-reference star magnitudes. The reconstructed PSFs are observed to match the
reference ones with a relative error in Strehl ratio and full-width at half
maximum below $10\%$ over a field of view of the order of one arcmin, making
the proposed PSF-R method an appealing tool to assist observation analysis,
and interpretation.

###### keywords:

PSF reconstruction; off-axis; MICADO@ELT; AO post-processing

##  1 INTRODUCTION

As the first light instruments of the Extremely Large Telescope (ELT), the
Multi-AO Imaging Camera for Deep Observations (MICADO) will rely heavily on
adaptive optics (AO) to obtain almost diffraction-limited images. Still, in
the majority of the planned science cases, a detailed knowledge of the point
spread function (PSF) is required to match the scientific goals ([4];[6]). For
this reason, the PSF reconstruction (PSF-R) is a deliverable of the MICADO
consortium ([10];[8]). However, the PSF of AO-assisted instruments is an
entity that is rapidly varying both temporally and spatially in the field of
view; making its accurate characterization a challenging task.

The MICADO PSF-R core algorithm has already been presented in Ref. [13] and
tested both on end-to-end simulations ([13]) and real data ([11]). The single
conjugate AO (SCAO) case has been treated, reconstructing only on-axis PSFs.
The method is based on Ref. [12] and it relies on the computation of optical
transfer functions, which in turn, can be described by means of structure
functions ([13]). We underline that the adopted formalism, under the
assumptions of fast frame rate and the use of a least squares reconstructor,
allows a further decomposition of the structure functions into independent
components that is valid regardless of the considered wavefront sensor (WFS).
This makes the MICADO PSF-R algorithm particularly flexible, allowing the
reconstruction of the PSF of different SCAO instruments to be performed with
minimal tuning. Another distinguishing characteristic of the MICADO PSF-R is
that it does not make use of any information from the science frames. The PSF
is reconstructed taking advantage of AO telemetry saved simultaneously to the
science frames during observations ([13];[11]). This strategy is the only
viable option when no suitable point sources are present in the science frame
to properly derive a PSF estimation, e.g. in the case of observations of a
typical extragalactic target ([10];[11]). Other PSF-R methods that have been
developed include Refs. [15];[9];[1];[7]; see e.g. [2] for a review on PSF-R
flavours.

MICADO will work in SCAO mode at the beginning of its operational
life111Multi-conjugate AO observations with MICADO will be possible when the
Multiconjugate adaptive Optics Relay For ELT Observations (MORFEO [3]) will be
integrated, this means that the correction by the AO system is optimized along
the direction of the AO reference star (on-axis). The AO correction at
increasing angular distances from the AO reference source (i.e. off-axis) is
less accurate. Starting from off-axis distances of the order of an arcsecond,
the PSFs are systematically different, with lower Strehl ratio (SR), higher
full-width at half maximum (FWHM) and in general elongated in the direction of
the AO reference source. To reconstruct the off-axis PSFs, solutions have been
provided that require a model PSF to be constructed extracting information
from the science plane, making use of suitable point sources present in the
science frame (e.g. [15];[1]). Still, for MICADO, a pure-telemetry PSF-R is
being developed ([10];[11]). What has been recently implemented in the MICADO
PSF-R algorithm, is the use of tomography to infer the residual incoming
wavefront for the (off-axis) direction of interest. The method, presented in
[14], relies on the instantaneous reconstruction of the incoming wavefront in
order to create a tomographic image of the atmospheric turbulence during the
observations. This can be computed from telemetry in a similar fashion of what
is done in the on-axis case. Once the instantaneous tomographic images of the
incoming wavefront are derived, they can be sampled in the desired (off-axis)
direction and time. The off-axis PSF can be then derived as in the on-axis
case. The tomography is made possible by inferring the power, height and wind
speed and direction of a reference set of (powerful) atmospheric turbulence
layers. In this respect, the following results has been obtained sampling an
ESO standard atmosphere (9-layer) at 3 different height ($0$,$6$ and $10$km),
as an input for the tomography. It is also worth noting that the tomographic
approach is less accurate for off-axis direction perpendicular to the wind
direction of the strongest layers. Still, because of the fact that MICADO
PSF-R is a post-processing tool, the whole time-line can be used to perform
the tomography. This means that both past and future telemetry frames can be
used to reconstruct the residual incoming wavefront at a selected time and
off-axis direction. This enlarges the spatial coverage of the tomography,
enabling also the recovery of some information in these directions. In this
respect, it is important to underline that both in our on-axis and off-axis
PSF-R methods the frame-rate and completeness of the saved telemetry
(simultaneous to science observations) plays a critical role.

In this work, we will summarize the status of the MICADO PSF-R reviewing its
performance. The presented results come from tests performed both on simulated
and real data that cover a broad range of observing conditions and
instrumental set-up. The performance of our PSF-R method has been assessed
through the comparison between the observed PSF and the associated
reconstructed one, for each dataset. After a proper normalization, SR, FWHM
and encirled energy of the core of the PSF (${\rm EE_{CORE}}$) have been used
as a metric to asses the quality of the reconstruction.

##  2 DATA

As mentioned in the previous section, the dataset used is diverse and includes
both real observations of point sources and simulated ones. The full set is
characterized by different WFS, filters and brightness of the AO reference
sources.

Table 1: Compilation of real observations used for testing the MICADO PSF-R algorithm. For each instrument the information about the WFS has been included, along with the observation date, filter and the angular distance of any off-axis point source, if present.  DATASET ID | INSTRUMENT | WFS TYPE | DATE OBS. | FILTER | OFF-AXIS
---|---|---|---|---|---
|  |  |  | $[\mu{\rm m}]$ | $[{\rm arcsec}]$
Simioni+2022-Daytime | SOUL+LUCI@LBT | Pyramid | 2019/03/29 | H (1.65) | NO
Simioni+2022-Nighttime | SOUL+LUCI@LBT | Pyramid | 2019/11/09 | FeII (1.65) | NO
ERIS_20220712 | ERIS@VLT | Shack Hartmann | 2022/07/12 | Br-g (2.2) | NO
ERIS_TTR_20230425 | ERIS@VLT | Shack Hartmann | 2023/04/25 | FeII (1.65) | 7; 16

For what concerns the real observations, a list of the used data is presented
in Table 1. For each set we list the used instrument, the WFS type, the date
of observation, the filter and the radial distance of any off-axis source
analysed. In all these cases, the AO reference source used is a bright star.
Results presented in Ref. [11] have been included. They refer to observations
taken with the SOUL+LUCI instrument installed at the Large Binocular Telescope
(LBT). In the present work, the two considered sets are labelled
Simioni+2022-Daytime and Simioni+2022-Nighttime. We refer to Ref. [11] for
further details on these data.

Given its similarities with MICADO, SOUL+LUCI@LBT is a particularly
interesting instrument to test our PSF-R tool and another exciting opportunity
comes from the recent integration of the ERIS ([5]) instrument at the Very
Large Telescope (VLT). Two sets have been analysed in this work. The first one
(labelled ERIS_20220712) has been taken on July 2022 and refers to
observations of the AO reference star itself (an on-axis point source). The
source has been observed continuously for $2$ min and the associated
(simultaneous) AO telemetry has been saved (at $1{\rm KHz}$). The second set
(labelled ERIS_TTR_20230425) refers to recent observations taken in the
context of a technical time request (TTR). In this case, a bright AO reference
star has been observed for $3.5$ min and the associated AO telemetry has been
saved at $1\rm{KHz}$. Specifically, this set is particularly interesting as it
offers the opportunity to test our off-axis PSF-R method. In the science
frames, in fact, two other point sources are present along with the AO
reference star itself. The radial distance between each of these 2 stars and
the AO reference one is respectively $7$ and $16$ arcsec.

---
Figure 1:  Zoom of the science frame of the ERIS_TTR_20230425 dataset centered
on each one of the three point sources present in the scientific field of
view. From left to right, the three PSFs associated to the AO reference star,
the off-axis point source at a radial distance of $7$ arcsec, and the one at a
radial distance of $16$ arcsec. The color-scale is logarithmic and is the same
for all panels. It can be noted the increasing elongation of the PSFs at
larger values of radial distance from the AO reference star.

The PSFs associated to each of the point sources (one on-axis and two off-
axis) in the scientific field of view of the ERIS_TTR_20230425 dataset are
shown in Fig. 1. From left to right, the PSFs are ordered in increasing radial
distance, with the leftmost one being the PSF associated to the AO reference
star (on-axis). The sharpness of the on-axis PSF and the high number of the
associated Airy rings indicate the high quality of the AO correction in this
particular dataset. It can also be easily noticed the increasing elongation
associated to the off-axis PSFs going towards larger radial distances from the
AO reference star. The PSF elongation is oriented radially.

As anticipated before, in this work we make use also of simulated
observations. A list of all the simulated PSFs used, along with the AO
reference star magnitude and off-axis distance is presented in Tab. 2.

Table 2:  Compilation of simulated observations used for testing the MICADO PSF-R algorithm. All the simulated PSFs have been generated by the MICADO consortium for the Final Design Review. For both on- and off-axis cases, three brightness regimes of the AO reference star have been simulated. All the simulated PSFs have an effective wavelength of about $2.2\,\mu{\rm m}$ (e.g. a Ks band). DATASET ID | AO REF. ${\rm m}_{0.85\mu{\rm m}}$ | OFF-AXIS
---|---|---
| [mag] | [arcsec]
MICADO_bright_on-axis | 10 | 0
MICADO_intermediate_on-axis | 14 | 0
MICADO_faint_on-axis | 16 | 0
MICADO_bright_off-axis | 10 | 30
MICADO_intermediate_off-axis | 14 | 30
MICADO_faint_off-axis | 16 | 30

We analysed a total of $6$ simulated PSFs, $3$ on-axis and $3$ off-axis, all
at a distance of $30$ arcsec. Three different brightness regimes of the AO
reference source have been simulated, for both on-axis and off-axis cases.
This produced a wide variation in the shape of each simulated PSF, in
particular the SR varies from about $70\%$ for the MICADO_bright_on-axis to
about $10\%$ for the MICADO_faint_off-axis. These simulations are a product of
the MICADO final design review and have been computed by a distinct MICADO
work package ([10]).

##  3 RESULTS

An observed PSF has been obtained, for each point source in each dataset,
after proper normalization of the reduced data. When possible, observations
have been mediated toghether in order to enhance the signal to noise ratio of
the resulting observed PSF. Each observed PSF has been then compared with the
associated reconstructed one. It is worth stressing again that all the
reconstructed PSFs have been obtained without using information coming from
the science plane. The comparison has thus been performed a posteriori in
order to asses the reliability of the PSF-R method, without any adjustment of
the resulting reconstructed PSF. On the other hand, we make use of the full AO
telemetry stream, simultaneous with the science observations, and saved at the
original sampling-rate.

---
Figure 2:  Results of the comparison between observed and reconstructed PSFs
for 3 different dataset. The upper row refers to Simioni+2022-Nighttime, the
middle one to MICADO_faint_off-axis and the bottom row to the 16 arcsec off-
axis star in ERIS_TTR_20230425. In each row, the observed PSF is shown on the
left (O), then the reconstructed PSF (R) and the absolute residuals between O
and R. The color-scale used in these plots is logarithmic and it is the same
for all of them. In the leftmost panels, the radial profiles (mean over all
angles) of observed (black) and reconstructed (red) PSF are shown. The shaded
areas represents one standard deviation.

As an example, in the leftmost panels of Fig. 2, we show the observed PSF of
$3$ representative datasets. The upper panels refers to
Simioni+2022-Nighttime, observations of a bright on-axis star. The middle
panel refers to MICADO_faint_off-axis, a simulated observation of a star, $30$
arcsec from the AO reference one. Finally, the bottom row refers to the off-
axis star in ERIS_TTR_20230425 $16$ arcsec from the AO reference one. It is
worth noting that these last two sets are the worst case of all the simulated
PSFs and the most challenging one for what concerns the off-axis PSF-R of real
data, respectively. In Fig. 2, we report also the residual images for each
observed and its associated reconstructed PSF. The radial profiles of all the
PSFs are also shown in the rightmost panels. It can be noted that: i)
residuals are small especially in the central region, ii) no evident
structures are present in the residuals, iii) the radial profiles of observed
and reconstructed PSFs overlap in each case.

---
Figure 3:  MICADO PSF-R performance. SR (upper row), FWHM (middle row) and
${\rm EE_{CORE}}$ (bottom row) values are shown. Both observed (in black) and
reconstructed (in red) values are shown together for each considered dataset.
In detail, the leftmost column refers only to real observations of on-axis
point sources; the second column refers to simulated observations of on-axis
point sources; the measured values for real observations of off-axis point
sources are shown in the third column; finally, in the rightmost column we
report the values in the case of simulated observations of off-axis point
sources.

In order to quantify the performance of the MICADO PSF-R, we use a metric
defined by SR, FWHM and ${\rm EE_{CORE}}$. All the results are shown in Fig. 3
where, for each set we list the SR values in the upper row, FWHM values (in
pixels) in the middle one and ${\rm EE_{CORE}}$ in the bottom row. The values
associated to the observed PSFs are shown in black (dots or circles depending
on the effective wavelength of the observations), while red crosses mark the
values associated to the reconstructed PSFs. The plot is further subdivided
(columns) in order to group on-axis and off-axis PSFs and differentiate,
within each group, real and simulated observations. In each case and for each
parameter, a precision within $10\%$ is reached; regardless of the type of WFS
or the filter considered. While the results obtained for the off-axis PSF-R
method are consistent, in general, with what is obtained on-axis, in these
last cases the method performs even better.

##  4 SUMMARY AND FUTURE DEVELOPMENTS

The MICADO PSF-R algorithm has been recently upgraded by implementing a
tomographic method to produce reconstructed PSFs for any off-axis direction in
SCAO observations with a field of view of the order of $1$ arcmin wide. The
method is described in detail in Ref. [14] and in this work we presented the
preliminary result of the reconstruction of off-axis PSFs in the case of real
ERIS@VLT SCAO observations. In particular, $2$ off-axis stars have been
observed with ERIS in the same field of view along with the AO reference one.
For both the off-axis sources the reconstruction is encouraging, reaching a
precision at the level of $10\%$ in SR, FWHM and ${\rm EE_{CORE}}$. To
quantify the performance of the MICADO PSF-R, we include these new results in
a compilation of both real and simulated observation. In this way the
parameter space has been enlarged by including e.g. different WFS types,
filters, brightness regimes of the AO reference star and off-axis distances.
Our PSF-R algorithm is performing consistently in the whole range of the
parameter space covered by the present dataset, demonstrating its reliability
and versatility especially in the on-axis case. Moreover, the reconstruction
of real observations confirms what results from the simulations.

While ERIS@VLT data are still being analysed, the present results motivate an
effort in collecting more data. Especially with respect to the off-axis case
and, in perspective, to the multi-conjugate AO case. This will also be
fundamental in expanding the parameter space regarding e.g. seeing regimes,
different filters, brightness regimes of the AO reference star. We make a
final remark noting that the goal of ERIS@VLT technical time request was
specifically to collect data useful for testing PSF-R techniques. Furthermore
they will be made public, providing the opportunity to test different PSF-R
methods consistently.

###### Acknowledgements.

The authors are thankful to E. Valenti, M. LeLouarn, J. Vernet, M. Cirasuolo
of the European Southern Observatory for their effort in preparing and
coordinating the ERIS technical time request.

## References

  * [1] O. Beltramo-Martin et al.  “PRIME: PSF Reconstruction and Identification for Multiple-source characterization Enhancement - application to Keck NIRC2 imager”  In _Monthly Notices of the Royal Astronomical Society_ 487.4, 2019, pp. 5450–5462  DOI: 10.1093/mnras/stz1667
  * [2] O. Beltramo-Martin et al.  “Review of PSF reconstruction methods and application to post-processing”  In _Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series_ 11448, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2020, pp. 114480A  DOI: 10.1117/12.2560805
  * [3] Paolo Ciliegi et al.  “MAORY/MORFEO at ELT: general overview up to the preliminary design and a look towards the final design”  In _Adaptive Optics Systems VIII_ 12185, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2022, pp. 1218514  DOI: 10.1117/12.2628969
  * [4] R. Davies et al.  “MICADO: first light imager for the E-ELT”  In _Ground-based and Airborne Instrumentation for Astronomy VI_ 9908, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2016, pp. 99081Z  DOI: 10.1117/12.2233047
  * [5] R. Davies et al.  “The Enhanced Resolution Imager and Spectrograph for the VLT”  In _Astronomy & Astrophysics_ 674, 2023, pp. A207  DOI: 10.1051/0004-6361/202346559
  * [6] Richard Davies and Markus Kasper  “Adaptive Optics for Astronomy”  In _Annual Review of Astron and Astrophys_ 50, 2012, pp. 305–351  DOI: 10.1146/annurev-astro-081811-125447
  * [7] T. Fusco et al.  “Reconstruction of the ground-layer adaptive-optics point spread function for MUSE wide field mode observations”  In _Astronomy & Astrophysics_ 635, 2020, pp. A208  DOI: 10.1051/0004-6361/202037595
  * [8] Andrea Grazian et al.  “Status of the PSF reconstruction work package for MICADO at ELT”  In _Adaptive Optics Systems VIII_ 12185, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2022, pp. 1218541  DOI: 10.1117/12.2627715
  * [9] S. Ragland et al.  “Status of point spread function determination for Keck adaptive optics”  In _Adaptive Optics Systems VI_ 10703, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2018, pp. 107031J  DOI: 10.1117/12.2312975
  * [10] Matteo Simioni et al.  “MICADO PSF-reconstruction work package description”  In _Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series_ 11448, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2020, pp. 1144837  DOI: 10.1117/12.2561251
  * [11] Matteo Simioni et al.  “Point spread function reconstruction for SOUL + LUCI LBT data”  In _Journal of Astronomical Telescopes, Instruments, and Systems_ 8, 2022, pp. 038003  DOI: 10.1117/1.JATIS.8.3.038003
  * [12] J.-P. Veran, F. Rigaut, H. Maitre and D. Rouan  “Estimation of the adaptive optics long-exposure point-spread function using control loop data.”  In _Journal of the Optical Society of America A_ 14.11, 1997, pp. 3057–3069  DOI: 10.1364/JOSAA.14.003057
  * [13] Roland Wagner, Christoph Hofer and Ronny Ramlau  “Point spread function reconstruction for single-conjugate adaptive optics on extremely large telescopes”  In _Journal of Astronomical Telescopes, Instruments, and Systems_ 4, 2018, pp. 049003  DOI: 10.1117/1.JATIS.4.4.049003
  * [14] Roland Wagner, Jenny Niebsch and Ronny Ramlau  “Off-axis point spread function reconstruction for single conjugate adaptive optics”  In _Journal of the Optical Society of America A_ 40.7, 2023, pp. 1382  DOI: 10.1364/JOSAA.488843
  * [15] Gunther Witzel et al.  “The AIROPA software package: milestones for testing general relativity in the strong gravity regime with AO”  In _Adaptive Optics Systems V_ 9909, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2016, pp. 99091O  DOI: 10.1117/12.2233872


11institutetext: Key Laboratory of Mathematics Mechanization, Academy of
Mathematics and Systems Science, Chinese Academy of Sciences 22institutetext:
School of Mathematical Sciences, University of Chinese Academy of Sciences,
Beijing, China.
22email<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
# A Coefficient-Embedding Ideal Lattice can be Embedded into Infinitely Many
Polynomial Rings

Yihang Cheng 1122 Yanbin Pan 1122 0000-0002-5591-0234

###### Abstract

Many lattice-based crypstosystems employ ideal lattices for high efficiency.
However, the additional algebraic structure of ideal lattices usually makes us
worry about the security, and it is widely believed that the algebraic
structure will help us solve the hard problems in ideal lattices more
efficiently. In this paper, we study the additional algebraic structure of
ideal lattices further and find that a given ideal lattice in some fixed
polynomial ring can be embedded as an ideal in infinitely many different
polynomial rings. We explicitly present all these polynomial rings for any
given ideal lattice. The interesting phenomenon tells us that a single ideal
lattice may have more abundant algebraic structures than we imagine, which
will impact the security of corresponding crypstosystems. For example, it
increases the difficulties to evaluate the security of crypstosystems based on
ideal lattices, since it seems that we need consider all the polynomial rings
that the given ideal lattices can be embedded into if we believe that the
algebraic structure will contribute to solve the corresponding hard problem.
It also inspires us a new method to solve the ideal lattice problems by
embedding the given ideal lattice into another well-studied polynomial ring.
As a by-product, we also introduce an efficient algorithm to identify if a
given lattice is an ideal lattice or not.

###### Keywords:

ideal lattice coefficient embedding complexity.

##  1 Introduction

The research on lattice-based cryptography was pioneered by Ajtai [1] in 1996.
He presented a family of one-way function based on the Short Integer Solution
(SIS) problem, which has the average-case hardness under the worst-case
assumptions for some lattice problems. In 1997, Ajtai and Dwork [3] introduced
a public-key cryptosystem, whose average-case security can be based on the
worst-case hardness of the unique-Shortest Vector Problem. In 2005, Regev [24]
proposed another problem with average-case hardness, the Learning with Errors
problem (LWE), and also a public-key encryption scheme based on LWE. Because
of the average-case security, lattice-based cryptography has drawn
considerable attentions from then on.

Although there have been many cryptographic schemes based on LWE and SIS, the
main drawback of such schemes is their limited efficiency, due to its large
key size and slow computations. Especially, as the development of quantum
computers, it becomes more urgent to design more practical lattice-based
cryptosystems, since lattice-based cryptosystems are widely believed to be
quantum-resistant. To improve the efficiency, additional algebraic structure
is involved in the lattice to construct more practical schemes. Among them,
ideal lattice plays an important role.

In fact, as early as in 1998, Hoffstein, Pipher, and Silverman [15] introduced
a lattice-based public-key encryption scheme known as NTRU, whose security is
related to the ideal in the ring $\mathbb{Z}[x]/(x^{n}-1)$. Due to the cyclic
structure of the ideal lattice, the efficiency of NTRU is very high. Later, in
2010, Lyubashevsky, Peikert and Regev [19] presented a ring-based variant of
LWE, called Ring-LWE, whose average-case hardness is based on worst-case
assumptions on ideal lattices. In 2017, Peikert, Regev and Stephens-Davidowitz
[22] refined the proof of the security of Ring-LWE for more algebraic number
field. After the introduction of Ring-LWE, more and more practical
cryptosystems based on ideal lattices have be constructed.

There are two different ways to define ideal lattices.

One is induced by the coefficient embedding from ring $\mathbb{Z}[x]/f(x)$
into $\mathbb{Z}^{n}$. NTRU uses coefficient embedding to define its lattice.
It is very convenient to implement cryptosystems based on Ring-LWE with the
coefficient embedding. In fact, almost all the ideal lattice-based
cryptosystems are implemented via the coefficient embedding. However, it seems
not easy to clarify the hardness of problems for the coefficient-embedding
ideal lattice in general.

The other one is defined by the canonical embedding from the algebraic integer
ring of some number field $K$ into $\mathbb{C}^{n}$. This type of ideal
lattice is usually employed in the security proof or hardness reduction in
Ring-LWE based cryptography.

It is widely believed that the additional algebraic structure of ideal lattice
will help us solve its hard problems more efficiently.

In 2016, Cramer, Ducas, Peikert and Regev [11] introduced a polynomial-time
quantum algorithm to solve $2^{\sqrt{n\text{log}n}}$-SVP in principal ideal
lattices in the algebraic integer ring of $\mathbb{Q}(\zeta_{m})$, where $m$
is a power of some prime. In 2017, Cramer, Ducas and Wesolowski [12] extended
the result to general ideals. In the same year, Holzer, Wunderer and Buchmann
[16] extended the field to be $\mathbb{Q}(\zeta_{m})$, where $m=p^{a}q^{b}$
and $p$, $q$ are different primes.

In 2019, Pellet-Mary, Hanrot and Stehlé [23] introduced a pre-processing
method (PHS algorithm) to solve $\gamma$-SVP for ideal lattices in any number
field. The pre-processing phasing takes exponential time. Let $n$ be the
dimension of the number field $K$ viewed as a $\mathbb{Q}$-vector space.
Pellet-Mary et al. showed that by performing pre-processing on $K$ in
exponential time, their algorithm can, given any ideal lattice $I$ of $O_{K}$,
for any $\alpha\in[0,1/2]$ output a $\exp(\widetilde{O}((n\log
n)^{\alpha+1}/n))$ approximation of a shortest none-zero vector of $I$ in time
$\exp(\widetilde{O}((n\log n)^{1-2\alpha}/n))+T$. For the classical method,
$T=\exp(\widetilde{O}((n\log n)^{1/2})$ if $K$ is a cyclotomic field or
$T=\exp(\widetilde{O}((n\log n)^{2/3})$ for an arbitrary number field $K$.

In 2020, Bernard and Roux-Langlois [5] proposed a new “twisted” version of the
PHS algorithm. They proved that Twisted-PHS algorithm performs at least as
well as the original PHS algorithm and their algorithm suggested that much
better approximation factors were achieved. In 2022, Bernard, Lesavourey,
Nguyen and Roux-Langlois [6] extended the experiments of [5] to cyclotomic
fields of degree up to 210 for most conductors $m$.

In 2021, Pan, Xu, Wadleigh and Cheng [21] found the connection between the
complexity of the shortest vector problem (SVP) of prime ideals in number
fields and their decomposition groups, and revealed lots of weak instances of
ideal lattices in which SVP can be solved efficiently. In 2022, Boudgoust,
Gachon and Pellet-Mary [8] generalized the work of Pan et al. [21] and
provided a simple condition under which an ideal lattice defines an easy
instance of the shortest vector problem. Namely, they showed that the more
automorphisms stabilize the ideal, the easier it was to find a short vector in
it.

As mentioned above, almost all the research on SVP is in the canonical-
embedding ideal lattices and the research on SVP in the coefficient-embedding
ideal lattices is few. In some rings, such as the algebraic integer rings of
cyclotomic fields, the SVPs induced by the two different embeddings are
connected with each other.

In 2017, Baston [4] discussed the norm connection between the coefficient
embedding and the canonical embedding in the cyclotomic fields. Let
$K=Q(\zeta_{m})$ and for any ideal $I\in O_{K}$, let $T$ be the transformation
matrix from the coefficient-embedding lattice $\mathcal{L}(B)$ to the
canonical-embedding lattice $\mathcal{L}(B^{\prime})$, which means
$TB=B^{\prime}$. Consider the singular value decomposition (SVD) of $T$ and

$T=U\begin{pmatrix}s_{1}&0&\cdots&0\\\ 0&s_{2}&\cdots&0\\\
0&\vdots&\ddots&0\\\ 0&0&\cdots&s_{n}\end{pmatrix}V$

$s_{1}\geq s_{2}\geq\cdots\geq s_{n}>0$, $V$ and $M$ unitary matrices. Define
$k_{2}=\frac{s_{1}}{s_{n}}$ and he showed that the less $k_{2}$ is the more
relevant of the SVPs are in the ideal lattices induced by two different
embeddings of a fixed ideal.

More specifically, according to lemma 3.5 of [4], given
$T\in\mathbb{C}^{n\times n}$ and $x\in\mathbb{C}^{n}$,
$s_{1},s_{2},\cdots,s_{n}$ is the singular value of $T$, then
$s_{n}(T)\cdot\|x\|_{2}\leq\|Tx\|_{2}\leq s_{1}(T)\cdot\|x\|_{2}$. This
conclusion shows a direct reduction between the SVPs in two ideal lattices
induced by different embeddings of a fixed ideal. Using the notion above, if
there is an oracle to solve $\gamma$-SVP in $\mathcal{L}(B)$, then using lemma
3.5 of [4] and the relation $TB=B^{\prime}$ we can solve $k_{2}\gamma$-SVP in
$\mathcal{L}(B^{\prime})$ in polynomial time.

We recall that a number field $K$ is called monogenic if
$O_{K}=\mathbb{Z}[\alpha]$ for some $\alpha\in K$. All the cyclotomic and
quadratic fields are monogenic. Only in monogenic fields, $O_{K}$ is
isomorphic to a polynomial ring $\mathbb{Z}[x]/f(x)$ for some monic
irreducible integer polynomial $f(x)$ and only in this case the ideal lattices
induced by the coefficient embedding have the same algebraic structure with
the one induced by canonical embedding of the same ideal in the sense of ring
isomorphism.

In theorem 3.1 of [4], Baston showed that $k_{2}$ is only related to the
monogenic number field $K$ and has nothing to do with the chosen ideal or
fractional ideal. Though the research on $k_{2}$ in general monogenic number
field is little, when $K=Q(\zeta_{m})$ is a cyclotomic field,
$k_{2}=(\text{rad}(m))^{1/2}$ for $m$ is odd and
$k_{2}=(\text{rad}(m)/2)^{1/2}$ for $m$ is even, where rad(m) means the
different prime multiple of m (see lemma 3.4 of [4]). Therefore when $m=a^{l}$
with $l$ large enough, the SVPs in ideal lattices induced by two embeddings of
the same ideal are connected closely. When $m=2^{l}$ for any $l\geq 2$,
$k_{2}=1$ and the SVPs in two embedding ideal lattices are essentially the
same.

With the discussion of the Baston’s results above, in some monogenic number
fields especially some cyclotomic fields, we can use the result of the
canonical-embedding ideal lattices to handle the coefficient-embedding ideal
lattices.

####  1.0.1 Our contribution

In this paper, we focus on the coefficient embedding. Our main contribution is
to show that an ideal lattice in the ring $\mathbb{Z}[x]/f(x)$, where $f(x)$
is monic and $f(x)\in\mathbb{Z}[x]$, can be embedded into infinitely many
rings $\mathbb{Z}[x]/g(x)$, where $g(x)$ is monic and $g(x)\in\mathbb{Z}[x]$
(Theorem 1). Besides, we show an efficient algorithm for computing all the
rings that an ideal lattice can be embedded into and also judging whether a
given integer lattice can be embedded into a polynomial ring (Algorithm 1).

As we all know, a lattice is actually a discrete additive subgroup of
$\mathbb{R}^{m}$. The only difference between the general integer lattice and
the ideal lattice is the multiplication structure of the ideal lattice. In
fact, an integer lattice may be embedded into a polynomial ring
$\mathbb{Z}[x]/f(x)$, and it can be viewed as an ideal of
$\mathbb{Z}[x]/f(x)$. Hence, with this embedding, the integer lattice as an
ideal of $\mathbb{Z}[x]/f(x)$ is equipped with the multiplication of the ring
$\mathbb{Z}[x]/f(x)$. A natural question is that what will happen if we equip
the same lattice with different "multiplication" or is the ”multiplication”
unique ? Obviously if this can be done, the lattice will not change, but the
ring changes, which means that a fixed integer lattice may be viewed as
different ideals in different rings.

We show that it is possible to embed a given ideal lattice as another ideal
into infinitely many different polynomial rings by the coefficient embedding.
We explicitly present all the polynomial rings for any given ideal lattice.

It is widely believed that additional algebraic structure may lead a more
efficient algorithm to solve the hard problems in ideal lattice than general
lattices, such as the method of recovering a short generator proposed by
Cramer et al. [11] and the method of pre-processing any number field $K$
proposed by Pellet-Mary et al. [23]. The researches above are all in the
canonical-embedding ideal lattices.

The results of the SVP in canonical-embeddinng ideal lattices can also fit the
case in coefficient-embedding ideal lattices in lots of rings. Though in a
general monogenic number field the relation betweem SVPs in ideal lattices
induced by two different embeddings of a fixed ideal is unclear, by the
discussion of Baston’s [4] above in lots of special cyclotomic fields the
connection between the SVPs in ideal lattices induced by two different
embeddings of the same ideal is very close and solving the $\gamma$-SVP in one
embedding means solving the $\beta$-SVP in another embedding, where $\gamma$
and $\beta$ are close.

If we happen to find that the algebraic structure for polynomial ring $R$ that
can help us solve the ideal lattice problems in $R$ more efficiently, then our
results shows that it’s possible to solve the problem for other ideal lattices
not in $R$ as long as the ideal lattices can be embedded as ideals into $R$.
Similarly, when using the method in [23], the pre-processing of $R$ can also
be used to solve the problems for some ideal lattices not in $R$, which
implies that we may not need pre-process the new polynomial ring for every new
ideal lattices.

Moreover, once we find a weak ideal lattice in which the lattice problem can
be solved more efficiently, we can solve the problems for infinite ideal
lattices in different polynomial rings. Though the integer lattice is fixed,
they are different as ideals in different polynomial rings. It seems that a
weak ideal will spread as infinite weak ideals.

On the other hand, the abundant embedding relations will impact the security
of the crypstosystems based on ideal lattices. When considering the security,
it’s necessary to evaluate all the corresponding ideals in the polynomial
rings that the given ideal lattices can be embedded into instead of just one
single ideal lattice.

We have to point out that all of the observations above shed a shadow on the
security of ideal lattice-based cryptosystems.

As a by-product, an efficient algorithm to identify an ideal lattice is
introduced. We first show an equivalent condition between the integer lattice
and the coefficient-embedding ideal lattice. According to this condition, we
introduce a polynomial-time algorithm that is more efficient than the
algorithm proposed by Ding and Lindner [13]. Moreover, we present an explicit
form for all possible polynomial rings that the ideal lattice can be embedded
into in theory instead of the implicit form obtained in the experiment as in
[13]. The explicit form can help us theoretically analyze the algebraic
properties of there ideals directly.

####  1.0.2 Roadmap

The paper is organized as follows. In Section 2, some preliminaries are
presented. In Section 3, we reveal the embedding relation in details and give
some application scenes. In Section 4, an algorithm for identifying a
coefficient-embedding ideal lattice is introduced together with the complexity
analysis. In the final section, we give a brief conclusion.

##  2 Preliminaries

In this paper we denote by $\mathbb{C}$, $\mathbb{R}$, $\mathbb{Q}$ and
$\mathbb{Z}$ the complex number field, the real number field, the rational
number field and the integer ring respectively.

We denote a matrix by a capital letter in bold and denote a vector by a lower-
case letter in bold. To represent the element of a matrix, we use the lower-
case letter. For example, the element of matrix $\mathbf{A}$ at the $i$-th row
and $j$-th column is denoted by $a_{ij}$, while its $i$-th row is denoted by
$\mathbf{a}_{i}$. Since we have the inner products in $\mathbb{R}^{n}$ and
$\mathbb{C}^{n}$ respectively, we can define the norm of vectors, that is,
$\|\mathbf{v}\|:=<\mathbf{v},\mathbf{v}>$ in $\mathbb{R}^{n}$ and
$\|\mathbf{v}\|:=<\mathbf{v},\overline{\mathbf{v}}>$ in $\mathbb{C}^{n}$.

For two integers $a$ and $b$, $a|b$ means that $b$ is divisible by $a$.
Otherwise, we write $a\not|\ b$. For integer $a$ and a matrix $\mathbf{A}$,
$a|\mathbf{A}$ means that every entry of $\mathbf{A}$ can be divisible by $a$.

For a polynomial $f(x)\in\mathbb{Z}[x]$, denote by $\mathbb{Z}[x]/f(x)$ for
simplicity the quotient ring $\mathbb{Z}[x]/(f(x)\mathbb{Z}[x])$.

For a map $\sigma$, and a set $S$, denote by $\sigma(S)$ the set
$\\{\sigma(x):x\in S\\}$.

###  2.1 Lattice

Lattices are discrete subgroups of $\mathbb{R}^{m}$, or equivalently,

###### Definition 1

(Lattice) Given n linearly independent vectors
$\mathbf{B}=\begin{pmatrix}\mathbf{b}_{1}\\\ \mathbf{b}_{2}\\\ \vdots\\\
\mathbf{b}_{n}\end{pmatrix}$, where $\mathbf{b}_{i}\in\mathbb{R}^{m}$, the
lattice $\mathcal{L}(\mathbf{B})$ generated by $\mathbf{B}$ is defined as
follows:

$\mathcal{L}(\mathbf{B})=\\{\sum_{i=1}^{n}x_{i}\mathbf{b}_{i}:x_{i}\in\mathbb{Z}\\}=\\{\mathbf{xB}:\mathbf{x}\in\mathbb{Z}^{n}\\}.$

We call $\mathbf{B}$ a basis of $\mathcal{L}(\mathbf{B})$, m and n the
dimension and rank of $\mathcal{L}(\mathbf{B})$ respectively. When $m=n$, we
say $\mathcal{L}(\mathbf{B})$ is full-rank.

When $n\textgreater 1$, there are infinitely many bases for a lattice
$\mathbf{\mathcal{L}}$, and any two bases are related to each other by a
unimodular matrix, which is an invertible integer matrix. More precisely,
given a lattice $\mathcal{L}(\mathbf{B}_{1})$, $\mathbf{B}_{2}$ is also a
basis of the lattice if and only if there exists a unimodular matrix
$\mathbf{U}$ s.t. $\mathbf{B}_{1}=\mathbf{U}\mathbf{B}_{2}$.

##### Hard problems in lattices

The shortest vector problem (SVP) is one of the most famous hard problems in
lattices.

SVP is the question of finding a nonzero shortest vector in a given lattice
$\mathcal{L}$, whose length is denoted by $\lambda_{1}(\mathcal{L})$. The
approximating-SVP with factor $\gamma$, denoted by $\gamma$-SVP, asks to find
a short nonzero lattice vector $\mathbf{v}$ such that

$\|\mathbf{v}\|\leq\gamma\cdot\lambda_{1}(\mathcal{L}).$

In fact, The hardness of $\gamma$-SVP depends on $\gamma$. When $\gamma=1$,
$\gamma$-SVP is exactly the original SVP, and for constant $\gamma$, this
problem is known to be NP-hard under randomized reduction [2]. Many
cryptosystems are based on the hardness of (decision) $\gamma$-SVP when
$\gamma$ is in polynomial size. By now we have not found any polynomial-time
classical algorithm to deal with such cases. The existing polynomial
algorithms such as LLL [17], BKZ [26] can find the situation when
$\gamma=\text{exp}(n)$.

###  2.2 Hermite Normal Form

For the integer matrix, there is a very important standard form known as the
Hermite Normal Form (HNF). For simplicity, we just present the definition of
HNF for the non-singular integer matrix.

###### Definition 2

(Hermite Normal Form) A non-singular matrix $\mathbf{H}\in\mathbb{Z}^{n\times
n}$ is said to be in HNF, if

  * •

$h_{i,i}\textgreater 0$ for $1\leq i\leq n.$

  * •

$h_{j,i}=0$ for $1\leq j\textless i\leq n.$

  * •

$0\leq h_{j,i}\textless h_{i,i}$ for $1\leq i\textless j\leq n.$

The Hermite Normal Form has some important properties. See [14, 20, 18] for
more details.

###### Lemma 1

For any integer matrix $\mathbf{A}$, there exists a unimodular matrix
$\mathbf{U}$ such that $\mathbf{H}$=$\mathbf{U}\mathbf{A}$ is in HNF.
Moreover, HNF can be computed in polynomial time.

For integer lattices, we have

###### Lemma 2

For any lattice $\mathcal{L}\subset\mathbb{Z}^{n}$, there exists a unique
basis $\mathbf{H}$ in HNF. We call $\mathbf{H}$ the HNF basis of
$\mathcal{L}$.

Sometimes we do not need the whole HNF of an integer matrix. So we introduce
the Incomplete Hermite Normal Form of an integer matrix, which is also a
special basis of the integer lattice.

###### Definition 3

(Incomplete Hermite Normal Form) A non-singular matrix
$\mathbf{B}\in\mathbb{Z}^{n\times n}$ is said to be in Incomplete Hermite
Normal Form, if

  * •

$b_{n,n}>0$;

  * •

$b_{i,n}=0\mbox{ for }1\leq i\leq n-1.$

Given a full-rank integer matrix $\mathbf{B}$,

$\mathbf{B}=\begin{pmatrix}b_{1,1}&b_{1,2}&\cdots&b_{1,n}\\\
b_{2,1}&b_{2,2}&\cdots&b_{2,n}\\\ \vdots&\vdots&\ddots&\vdots\\\
b_{n,1}&b_{n,2}&\cdots&b_{n,n}\end{pmatrix},$

it is well known that by the Extended Euclidean Algorithm we can find a
unimodular matrix $\mathbf{U}$, such that

$U\begin{pmatrix}b_{1,n}\\\ b_{2,n}\\\ \vdots\\\
b_{n,n}\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ \vdots\\\ d\end{pmatrix},$

where $d=\gcd(b_{1,n},b_{2,n},...,b_{n,n})$. Then we have

$\mathbf{B}^{\prime}=U\mathbf{B}=\begin{pmatrix}\mathbf{D}&\mathbf{0}\\\
\mathbf{b^{\prime}}&d\end{pmatrix}$

is in Incomplete Hermite Normal Form, where
$\mathbf{D}\in\mathbb{Z}^{(n-1)\times(n-1)}$,
$\mathbf{b}^{\prime}\in\mathbb{Z}^{n-1}$.

About the Incomplete Hermite Normal Form, it is easy to conclude the following
lemma. So we omit the proof.

###### Lemma 3

For any non-singular matrix $\mathbf{B}\in\mathbb{Z}^{n\times n}$,
$\mathbf{B}$ is said to be in Incomplete Hermite Normal Form, if

  * •

we can find a unimodular matrix $\mathbf{U}$ in polynomial time, such that
$\mathbf{B}^{\prime}=\mathbf{U}\mathbf{B}$ is in Incomplete Hermite Normal
Form.

  * •

For any unimodular matrix $\mathbf{U}$ and $\mathbf{V}$ such that
$\mathbf{B}^{\prime}=\mathbf{U}\mathbf{B}$ and
$\mathbf{B}^{\prime\prime}=\mathbf{V}\mathbf{B}$ are in Incomplete Hermite
Normal Form, $\mathbf{B}^{\prime}$ and $\mathbf{B}^{\prime\prime}$ are not
necessarily equal, but

$b^{\prime}_{n,n}=b^{\prime\prime}_{n,n}=\gcd(b_{1,n},b_{2,n},...,b_{n,n}).$

Specially, notice that the HNF $\mathbf{H}$ of $\mathbf{B}$ is also in
Incomplete Hermite Normal Form. We immediately have

$h_{n,n}=\gcd(b_{1,n},b_{2,n},...,b_{n,n}).$

###  2.3 Ideal lattices

An algebraic number field $K$ is an extension field of the rationals
$\mathbb{Q}$ such that its dimension $[K:\mathbb{Q}]$ as a $\mathbb{Q}$-vector
space (i.e., its degree) is finite.

An element $x$ in the algebraic number field $K$ is said to be integral over
$\mathbb{Z}$ if the coefficients of the minimal polynomial of $x$ over
$\mathbb{Q}$ are all integers. All the elements which are integral over
$\mathbb{Z}$ in $K$ make up a set $O_{K}$. $O_{K}$ is actually a ring called
the algebraic integer ring of $K$ over $\mathbb{Z}$.

$O_{K}$ is a finitely generated free $\mathbb{Z}$-module of dimension
$[K:\mathbb{Q}]$. The basis of $O_{K}$ as a free $\mathbb{Z}$-module is called
the integer basis, which is also a basis of $K$ as a $\mathbb{Q}$-vector
space.

##### Canonical-embedding ideal lattice

If $\Omega\supset K$ is an extension field such that $\Omega$ is algebraically
closed over $\mathbb{Q}$, then there are exactly $[K:\mathbb{Q}]$ field
embeddings of $K$ into $\Omega$. For convenience, we regard $\Omega$ as the
complex field $\mathbb{C}$.

Any ideal of $O_{K}$ is a full-rank submodule of $O_{K}$. Let
$[K:\mathbb{Q}]=n$. This structure induces a canonical embedding:

$\displaystyle\Sigma:O_{K}$ $\displaystyle\rightarrow\mathbb{C}^{n}$
$\displaystyle a$ $\displaystyle\mapsto(\Sigma_{i}(a))_{i=1,...,n},$

where $\Sigma_{i}$’s are the $n$ different embeddings from $K$ into
$\mathbb{C}$.

###### Definition 4

(Canonical-embedding Ideal Lattice) Given a number field $K$ and any ideal I
of $O_{K}$, $\Sigma$(I) is called the canonical-embedding ideal lattice.

##### Coefficient-embedding ideal lattice

Denote by $\mathbb{Z}^{(n)}[x]$ the set of all the polynomials in
$\mathbb{Z}[x]$ with degree $\leq$$n-1$. We use the symbol $\sigma$ to
represent the following linear map:

$\displaystyle\sigma:\mathbb{Z}^{(n)}[x]$
$\displaystyle\rightarrow\mathbb{Z}^{n}$
$\displaystyle\sum_{i=1}^{n}a_{i}x^{i-1}$
$\displaystyle\mapsto(a_{1},a_{1},...,a_{n}),$

where linear map means that

  * •

For any $f(x)$, $g(x)\in\mathbb{Z}^{(n)}[x]$,
$\sigma(f(x)+g(x))=\sigma(f(x))+\sigma(g(x));$

  * •

For any $f(x)\in\mathbb{Z}^{(n)}[x]$ and $z\in\mathbb{Z}$,
$\sigma(zf(x))=z\sigma(f(x)).$

We can also define its inverse, which is linear too:

$\displaystyle\sigma^{-1}:\mathbb{Z}^{n}$
$\displaystyle\rightarrow\mathbb{Z}^{(n)}[x]$
$\displaystyle(a_{1},a_{1},\cdots,a_{n})$
$\displaystyle\mapsto\sum_{i=1}^{n}a_{i}x^{i-1}.$

In what follows, we focus on ideal lattices induced by ideals of the ring
$\mathbb{Z}[x]/f(x)$, where $f(x)$ is a monic polynomial of degree $n$.
Obviously, any element in $\mathbb{Z}^{(n)}[x]$ can be viewed as a
representative in the ring $\mathbb{Z}[x]/f(x)$. So we abuse the symbol
$\sigma$ to represent the the following coefficient embedding.

$\displaystyle\sigma:\mathbb{Z}[x]/f(x)$
$\displaystyle\rightarrow\mathbb{Z}^{n}$
$\displaystyle\sum_{i=1}^{n}a_{i}x^{i-1}$
$\displaystyle\mapsto(a_{1},a_{1},...,a_{n}).$

Therefore, under the coefficient embedding, any ideal of $\mathbb{Z}[x]/f(x)$
can be viewed as an integer lattice.

###### Definition 5

(Coefficient-embedding Ideal Lattice) Given $\mathbb{Z}[x]/f(x)$, where $f(x)$
is a monic polynomial of degree n, and any ideal $I$ of $\mathbb{Z}[x]/f(x)$,
$\sigma$(I) is called the coefficient-embedding ideal lattice, which is of
course an integer lattice.

Roughly speaking, the canonical-embedding ideal lattice are usually used in
the theoretical analysis of lattice-related hard problems and lattice-based
cryptosystems whereas the coefficient-embedding ideal lattices are usually
used in the implementation of lattice-based cryptosystems. Most of the
practical lattice-based cryptosystems are employing the coefficient-embedding
ideal lattices.

In some cases, the SVP problem in canonical-embedding ideal lattices and
coefficient-embedding ideal lattices are equivalent or very closely connected
with each other as we’ve mentioned in the latter of the introduction.

In the third section, we first show and prove a naturally equivalent condition
(Lemma 4) that whether an integer lattice can be embedded into a given
polynomial ring. It’s not complicated and it’s a direct application of the
Definition 5. Though the result of Lemma 4 may have been used in the early
research, we haven’t found a detailed description. Hence, we rewrite and prove
the Lemma 4 formally.

Our main theorem (Theorem 1) is motivated by Lemma 5 proposed by Zhang, Liu
and Lin [29]. They show that the coefficients of HNF of a coefficient-
embedding ideal lattice satisfy some special condition. Using the result of
Lemma 5 ($h_{n,n}|h_{i,j}$) together with the equivalent condition of Lemma 4,
we prove the Theorem 1.

Next, we show some potential application of our main theorem, and give some
examples. Though the examples may not be practical in the reality for now, it
do supply us a new angle to deal with the SVP in ideal lattices or integer
lattices.

In the fourth section, we propose Algorithm 1 to judge whether an integer
lattice can be embedded into a polynomial ring as an ideal and compute all the
rings that the lattice can be embedded into as an ideal if it’s an ideal
lattice. We originally want to make use of the property of Lemma 5, but we
find the property of Lemma 5 is too weak to judge whether an integer lattice
is an ideal lattice. Hence, based on this ideal we introduce Definition 3 the
Incomplete Hermite Normal Form and propose another equivalent condition
(Theorem 2 ) to judge an ideal lattice. Based on Theorem 2, we propose
Algorithm 1, and give a simple analysis of the complexity.

##  3 An ideal lattice can be embedded into different rings

We stress that in the following, we focus on the coefficient-embedding ideal
lattice, and in this section, we’ll show how an coefficient-embedding ideal
lattice can be embedded into different rings.

The idea behind is much simple. It is well known that a lattice is just an
additive group. However, when it is also equipped with some "multiplication",
then it becomes an ideal lattice. A natural question is that what will happen
if we equip the same lattice with different "multiplication"? Obviously if
this can be done, the lattice will not change, but the ideal changes, which
means that an ideal lattice can be viewed as different ideals in different
rings.

###  3.1 Two Properties of ideal lattices

Before stating our main theorem, we present two crucial properties of
coefficient-embedding ideal lattices.

####  3.1.1 Deciding an ideal lattice

We next present an easy way to tell if a given lattice is a coefficient-
embedding ideal lattice in $\mathbb{Z}[x]/f(x)$ or not.

###### Lemma 4

For any monic polynomial $f(x)\in\mathbb{Z}[x]$ with degree $n$, a lattice
$\mathcal{L}(\mathbf{B})$ with any basis $\mathbf{B}$ is a coefficient-
embedding ideal lattice in $\mathbb{Z}[x]/f(x)$ if and only if
$\sigma(x\sigma^{-1}(\mathbf{b}_{i})\mod f(x))\in\mathcal{L}(\mathbf{B})$ for
$i=1,\cdots,n$, where $\mathbf{b}_{i}$ is the $i$-th row vector of
$\mathbf{B}$, and $\sigma$ is the map defined in Section 2.3.

###### Proof

If $\mathcal{L}(\mathbf{B})$ is a coefficient-embedding ideal lattice in
$\mathbb{Z}[x]/f(x)$, then $\sigma^{-1}(\mathbf{b}_{i})$’s are in the
corresponding ideal. It is obvious that $x\sigma^{-1}(\mathbf{b}_{i})\mod
f(x)$ must be in the ideal too, which means that
$\sigma(x\sigma^{-1}(\mathbf{b}_{i})\mod f(x))\in\mathcal{L}(\mathbf{B})$.

If there exists a monic polynomial $f(x)\in\mathbb{Z}[x]$ with degree $n$,
such that $\sigma(x\sigma^{-1}(\mathbf{b}_{i})\mod
f(x))\in\mathcal{L}(\mathbf{B})$ for $i=1,\cdots,n$, we show that
$\sigma^{-1}(\mathcal{L}(\mathbf{B}))$ must be an ideal in
$\mathbb{Z}[x]/f(x)$. It is easy to check that
$\sigma^{-1}(\mathcal{L}(\mathbf{B}))$ is an additive group, due to the fact
that $\sigma$ is an additive homomorphism. Since
$\sigma(x\sigma^{-1}(\mathbf{b}_{i})\mod f(x))\in\mathcal{L}(\mathbf{B})$,
then for any lattice vector $\mathbf{v}=\sum_{i=1}^{n}z_{i}\mathbf{b}_{i}$,
$z_{i}\in\mathbb{Z}$, we have

$\sigma(x\sigma^{-1}(\mathbf{v})\mod
f(x))=\sum_{i=1}^{n}z_{i}\sigma(x\sigma^{-1}(\mathbf{b}_{i})\mod
f(x))\in\mathcal{L}(\mathbf{B}).$

Applying the result on the lattice vector $\sigma(x\sigma^{-1}(\mathbf{v})\mod
f(x))$, we will have

$\sigma(x^{2}\sigma^{-1}(\mathbf{v}))=\sigma(x\sigma^{-1}(\sigma(x\mathbf{v}\mod
f(x))))\in\mathcal{L}(\mathbf{B}).$

Hence, for any positive integer $k$, we know that

$\sigma(x^{k}\sigma^{-1}(\mathbf{v}))\in\mathcal{L}(\mathbf{B}).$

Then for any $g(x)=\sum_{i=1}^{n}g_{i}x^{i-1}\in\mathbb{Z}[x]/f(x)$ and any
lattice vector $\mathbf{v}$,

$\sigma(g(x)\sigma^{-1}(\mathbf{v})\mod
f(x))=\sum_{i=1}^{n}g_{i}\sigma(x^{i-1}\sigma^{-1}(\mathbf{v})\mod
f(x))\in\mathcal{L}(\mathbf{B}).$

The lemma follows.

####  3.1.2 HNF of ideal lattices

The following lemma tells us some divisibility relation among the elements in
the HNF basis of a coefficient-embedding ideal lattice, which has been proved
in [29]. For completeness, we present the whole proof simply.

######  Lemma 5 ([29])

Let $\mathbf{H}$ be the HNF basis of the full-rank coefficient-embedding ideal
lattice $\mathcal{L}(\mathbf{B})$ in the ring $\mathbb{Z}[x]/f(x)$.

$\mathbf{H}=\begin{pmatrix}h_{1,1}&0&\cdots&0\\\ h_{2,1}&h_{2,2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ h_{n,1}&\cdots&\cdots&h_{n,n}\end{pmatrix}.$

Then $h_{i,i}|h_{j,l}$, for ${1\leq l\leq j\leq i\leq n}$. Specially,
$h_{n,n}|h_{i,j}$, ${i,j\leq n}$.

###### Proof

By induction on $i$, it’s trivial for $i=1$.

Assume the result holds for $i\leq k\leq n-1$. It remains to show that for
$i=k+1$, $h_{k+1,k+1}|h_{j,l}$ where ${1\leq l\leq j\leq k+1\leq n}$.

Let $\mathbf{h}_{i}$ be the $i$-th row of $\mathbf{H}$. Note that for any
ideal $I$ of $\mathbb{Z}[x]/f(x)$ and for all $g(x)\in I$, $xg(x)\in I$.
Specially $x\sigma^{-1}(\mathbf{h}_{k})\in I$, where $\sigma$ is the
coefficient-embedding. Since $\mathbf{H}$ is a basis of the ideal lattice, it
is very simple to imply that there must exist $y_{i}\in\mathbb{Z}$, for
$i=1,2,\cdots,k+1$ such that:

$\begin{pmatrix}0&h_{k,1}&\cdots&h_{k,k}&0&\cdots&0\end{pmatrix}=\sum_{i=1}^{k+1}y_{i}\mathbf{h}_{i}.$

Hence,

$\displaystyle h_{k,k}$ $\displaystyle=y_{k+1}h_{k+1,k+1}$ $\displaystyle
h_{k,k-1}$ $\displaystyle=y_{k}h_{k,k}+y_{k+1}h_{k+1,k}$ $\displaystyle\vdots$
$\displaystyle h_{k,1}$ $\displaystyle=\sum_{i=2}^{k+1}y_{i}h_{i,2}$
$\displaystyle 0$ $\displaystyle=\sum_{i=1}^{k+1}y_{i}h_{i,1}$

From the first equation, we get
$y_{k+1}=\frac{h_{k,k}}{h_{k+1,k+1}}\in\mathbb{Z}$, and

$\displaystyle h_{k+1,k}$
$\displaystyle=\frac{h_{k,k-1}-y_{k}h_{k,k}}{h_{k,k}}h_{k+1,k+1}$
$\displaystyle h_{k+1,k-1}$
$\displaystyle=\frac{h_{k,k-2}-y_{k-1}h_{k-1,k-1}-y_{k}h_{k,k-1}}{h_{k,k}}h_{k+1,k+1}$
$\displaystyle\vdots$ $\displaystyle h_{k+1,2}$
$\displaystyle=\frac{h_{k,1}-\sum_{i=2}^{k}y_{i}h_{i,2}}{h_{k,k}}h_{k+1,k+1}$
$\displaystyle h_{k+1,1}$
$\displaystyle=\frac{-\sum_{i=1}^{k}y_{i}h_{i,1}}{h_{k,k}}h_{k+1,k+1}$

From the induction hypothesis, we have $h_{k,k}|h_{j,l}$ for $1\leq l\leq
j\leq k\leq n$. So the coefficient of $h_{k+1,k+1}$ in each equation is in
fact an integer. Therefore, $h_{k+1,k+1}|h_{k+1,l},1\leq l\leq k+1$. Since
$h_{k+1,k+1}|h_{k,k}$, we know $h_{k+1,k+1}|h_{j,l}$, where $1\leq l\leq j\leq
k+1\leq n$. Thus, the result holds for $i=k+1$.

By induction, $h_{i,i}|h_{j,l}$, ${1\leq l\leq j\leq i\leq n}$. So
$h_{n,n}|h_{i,j}$, ${1\leq i\leq j\leq n}$. Lemma 5 follows.

###### Remark 1

Note that in the proof of Lemma 5, to conclude that $h_{n,n}|h_{i,j}$,
${i,j\leq n}$, what we need is
$\sigma(x\sigma^{-1}(\mathbf{h}_{k}))\in\mathcal{L}(\mathbf{B})$ for
$k=1,\cdots,n-1$. We do not care about if
$\sigma(x\sigma^{-1}(\mathbf{h}_{n}))$ is in $\mathcal{L}(\mathbf{B})$ or not.

Lemma 5 presents us the divisibility relation among the elements in the HNF
basis of a coefficient-embedding ideal lattice. Actually, not only it’s
crucial to our main theorem, but also we can regard it as a tool to quickly
rule out some integer lattices not being an ideal lattice in any polynomial
ring. See Section 4 for more details.

###  3.2 Main theorem

We next present our main theorem.

###### Theorem 3.1

For any full-rank coefficient-embedding ideal lattice
$\mathcal{L}(\mathbf{B})$ in the ring $\mathbb{Z}[x]/f(x)$, where $f(x)$ is
monic and $\text{deg}(f(x))=n$, there exists infinitely many monic
$g(x)\in\mathbb{Z}[x]$ with degree $n$, s.t. $\mathcal{L}(\mathbf{B})$ is also
a coefficient-embedding ideal lattice in $\mathbb{Z}[x]/g(x)$.

More precisely, let $d=\gcd(b_{1,n},b_{2,n},...,b_{n,n})$. Then
$\mathcal{L}(\mathbf{B})$ is also a coefficient-embedding ideal lattice in
$\mathbb{Z}[x]/g(x)$, where $g(x)\in\mathbb{Z}[x]$ is a monic polynomial with
degree $n$, if and only if

$\sigma(f(x)-g(x))\in\mathcal{L}(\frac{\mathbf{B}}{d}),$

or equivalently,

$g(x)\in f(x)+\sigma^{-1}(\mathcal{L}(\frac{\mathbf{B}}{d})).$

###### Proof

Consider the HNF basis of $\mathcal{L}(\mathbf{B})$,

$\mathbf{H}=\begin{pmatrix}h_{1,1}&0&\cdots&0\\\ h_{2,1}&h_{2,2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ h_{n,1}&\cdots&\cdots&h_{n,n}\end{pmatrix}.$

For convenience, we denote by $\mathbf{h}_{i}$ the $i$-th row of $\mathbf{H}$,
and then $\mathbf{h}_{i}$ is a vector in $\mathbb{Z}^{n}$.

(i) If there is a monic $g(x)\in\mathbb{Z}[x]$ with degree $n$, s.t.
$\mathcal{L}(\mathbf{B})$ is also a coefficient-embedding ideal lattice in
$\mathbb{Z}[x]/g(x)$, we next prove that
$\sigma(f(x)-g(x))\in\mathcal{L}(\frac{\mathbf{B}}{d})$.

By Lemma 4, $\mathcal{L}(\mathbf{H})=\mathcal{L}(\mathbf{B})$ is a
coefficient-embedding ideal lattice in $\mathbb{Z}[x]/f(x)$, then we have

$\sigma(x\sigma^{-1}(\mathbf{h}_{n})\mod f(x))\in\mathcal{L}(\mathbf{B}).$

Note that

$x\sigma^{-1}(\mathbf{h}_{n})\mod
f(x)=\sum_{i=1}^{n-1}h_{n,i}x^{i}-h_{n,n}(f(x)-x^{n}).$

We have

$\begin{pmatrix}0&h_{n,1}&...&h_{n,n-1}\end{pmatrix}-h_{n,n}\sigma(f(x)-x^{n})\in\mathcal{L}(\mathbf{B}).$
(1)

Similarly, since $\mathcal{L}(\mathbf{B})$ is also a coefficient-embedding
ideal lattice in $\mathbb{Z}[x]/g(x)$, we have

$\begin{pmatrix}0&h_{n,1}&...&h_{n,n-1}\end{pmatrix}-h_{n,n}\sigma(g(x)-x^{n})\in\mathcal{L}(\mathbf{B}).$
(2)

Subtracting the left side of (1) from the left side of (2), we immediately
have

$h_{n,n}\sigma(f(x)-g(x))\in\mathcal{L}(\mathbf{B}).$

By Lemma 3, $h_{n,n}=d$, we have

$\sigma(f(x)-g(x))\in\mathcal{L}(\frac{\mathbf{B}}{d}).$

(ii) We next prove that for any polynomial $g(x)$, such that
$\sigma(f(x)-g(x))\in\mathcal{L}(\frac{\mathbf{B}}{d})$, any full-rank
coefficient-embedding ideal lattice $\mathcal{L}(\mathbf{B})$ in the ring
$\mathbb{Z}[x]/f(x)$ can also be viewed as a coefficient-embedding ideal
lattice in $\mathbb{Z}[x]/g(x)$.

First, $g(x)$ is obviously a monic polynomial with degree $n$. Note that by
Lemma 5, $h_{n,n}|h_{i,j}$, then $d=h_{n,n}$ divide all the components of
every lattice vector in $\mathcal{L}(\mathbf{B})$, which means that
$\mathcal{L}(\frac{\mathbf{B}}{d})$ is an integer lattice and once
$\sigma(f(x)-g(x))\in\mathcal{L}(\frac{\mathbf{B}}{d})$,
$g(x)\in\mathbb{Z}[x]$.

By Lemma 4 again, $\mathcal{L}(\mathbf{H})=\mathcal{L}(\mathbf{B})$ is a
coefficient-embedding ideal lattice in $\mathbb{Z}[x]/f(x)$, then we have

$\sigma(x\sigma^{-1}(\mathbf{h}_{i})\mod f(x))\in\mathcal{L}(\mathbf{B}),$

for $i=1,\cdots,n$.

To prove that $\mathcal{L}(\mathbf{B})$ is also a coefficient-embedding ideal
lattice in $\mathbb{Z}[x]/g(x)$, by Lemma 4 it is enough to show that
$\sigma(x\sigma^{-1}(\mathbf{h}_{i})\mod g(x))\in\mathcal{L}(\mathbf{B}),$ for
$i=1,\cdots,n$.

Note that for $i=1,\cdots,n-1$,

$\sigma(x\sigma^{-1}(\mathbf{h}_{i})\mod
g(x))=\sigma(x\sigma^{-1}(\mathbf{h}_{i})\mod
f(x))\in\mathcal{L}(\mathbf{B}).$

Since$\sigma(f(x)-g(x))\in\mathcal{L}(\frac{\mathbf{B}}{d})$, there exists a
lattice vector $\mathbf{v}\in\mathcal{L}(\mathbf{B})$ such that
$d(f(x)-g(x))=h_{n,n}(f(x)-g(x))=\sigma^{-1}(\mathbf{v})$. Then for $i=n$,

$\displaystyle\sigma(x\sigma^{-1}(\mathbf{h}_{n})\mod g(x))$
$\displaystyle=\sigma(\sum_{i=1}^{n-1}h_{n,i}x^{i}-h_{n,n}(g(x)-x^{n}))$
$\displaystyle=\sigma(\sum_{i=1}^{n-1}h_{n,i}x^{i}-h_{n,n}(f(x)-x^{n})+\sigma^{-1}(\mathbf{v}))$
$\displaystyle=\sigma(x\sigma^{-1}(\mathbf{h}_{n})\mod
f(x))+\mathbf{v}\in\mathcal{L}(\mathbf{B}).$

The theorem follows.

###### Remark 2

The HNF $\mathbf{H}$ in the proof can be replaced by any Incomplete Hermite
Normal Form.

###  3.3 Applications

For most lattice-based cryptosystems, their security is guaranteed by the
hardness of lattice problems such as $\gamma$-SVP. Hence, the hardness of
lattice problem in ideal lattice is widely considered as the security
foundation of Ring-LWE based cryptosystems.

Due to the additional algebraic structure, the problem for the ideal lattice
is usually conjectured to be easier than that for the general integer lattice.
Some recent progress supports the argument well. Obviously, the algebraic
structure depends on the polynomial ring that the ideal belongs to.

However, Theorem 3.1 shows us that an ideal lattice can be embedded as some
ideals into different polynomial rings, which means that an ideal lattice may
have different "algebraic structure" in different rings although the lattice
stays the same.

This phenomenon inspires us to consider the following method to solve the hard
problems for a given ideal lattice. By changing the polynomial ring, is it
possible to transform the given ideal lattice as another ideal in which the
lattice problems can be solved more efficiently by using the new algebraic
structure? It seems hard to present a negative answer if the algebraic
structure can indeed help solve the hard problems, since we have to consider
infinite ideals and hence infinite algebraic structures. This no doubt
increases the difficulty to show that the lattice problem for some fixed ideal
lattice is hard.

On the other hand, if we can utilize the algebraic structure to solve the
lattice problems in some ideal lattice, then we can solve the problems for
infinite ideal lattice in different rings. We would like to stress that as a
lattice, these ideal lattices are same. However, as ideals, they are
different. It seems that a weak ideal will spread as infinite weak ideals.

Next we present some concrete examples to show the potential risk inspired by
Theorem 4.1.

####  3.3.1 Pre-processing a fixed ring brings more.

In [23], Pellet-Mary et al. showed pre-processing the number field can help
solve $\gamma$-SVP in canonical-embedding ideal lattices more efficiently.
However, pre-processing usually costs too much time. One may think for
different number fields, we have to do different pre-processing. By Theorem
4.1, we know that pre-processing a fixed number field will also help us solve
$\gamma$-SVP more efficiently in ideals that is not in the algebraic integer
ring of the fixed number field.

Consider the ring $\mathbb{Z}[x]/(x^{n}+1)$, where $n=2^{k}$, which is one of
the most used rings in cryptosystems. It is well known that the lengths of
vectors induced by the same element under the coefficient embedding and the
canonical embedding are the same up to a fixed factor, which means the
hardness of SVP in such two embedding ideal lattices are equivalent. Hence, by
the method in [23], we can pre-process the ring $\mathbb{Z}[x]/(x^{n}+1)$, and
then can solve $\gamma$-SVP in its any coefficient-embedding ideal lattice
more efficiently.

Below we give a simple example to show how to apply the pre-processing on the
ideal in other polynomial ring.

###### Example 1

Given a coefficient-embedding ideal lattice in the ring
$\mathbb{Z}[x]/(x^{n}+x^{n-1}+2x^{n-2}+1)$ induced by the ideal $<x+2>$, where
$n=2^{k}$, the basis has the form

$\mathbf{B}=\begin{pmatrix}2&1&0&\cdots&\cdots&0\\\ 0&2&1&\cdots&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&\cdots&0&2&1\\\
-1&0&\cdots&0&-2&1\end{pmatrix}.$

Note that the greatest common divisor $d$ of the entries in the last column is
$1$. To verify that $\mathcal{L}(\mathbf{B})$ can be embedded as an ideal into
the ring $\mathbb{Z}[x]/(x^{n}+1)$, according to Theorem 3.1, it’s sufficient
to verify the following relation:

$\sigma((x^{n}+x^{n-1}+2x^{n-2}+1)-(x^{n}+1))=\begin{pmatrix}0&0&\cdots&0&2&1\end{pmatrix}\in\mathcal{L}(\mathbf{B}),$

which is obvious.

Therefore, by pre-processing the field $\mathbb{Q}[x]/(x^{n}+1)$, we can also
handle the hard problems on the ideal lattice $\mathcal{L}(\mathbf{B})$ in
$\mathbb{Z}[x]/(x^{n}+x^{n-1}+2x^{n-2}+1)$.

By the discussion above, our theorem has a good chance to amplify the results
of the research on the ideal lattice of certain rings.

####  3.3.2 Changing the ring may be not enough for the security.

Sometimes, we want to choose a special ring for the cryptosystems to resist
some potential attacks. This may work in general. However, for some fixed
ideal lattices, this may be not enough to obtain the desired security.

For example, NTRUPrime [7] uses the ring $\mathbb{Z}[x]/(x^{p}-x-1)$ to resist
the potential subfield attacks against NTRU, where $p$ is an odd prime. We
next present a simple example to show that some ideals generated by
polynomials with small coefficients in the ring $\mathbb{Z}[x]/(x^{p}-x-1)$
can also be embedded as an ideal into some $\mathbb{Z}[x]/f(x)$, where $f(x)$
is reducible. However, a reducible $f(x)$ may cause some potential security
risk.

###### Example 2

For convenience, we assume that $p$ is large enough. Consider the coefficient-
embedding ideal lattice induced by the principal ideal $<x^{p-1}-x^{2}-x>$ in
the ring $\mathbb{Z}[x]/(x^{p}-x-1)$. We show that such ideal lattice can be
embedded as an ideal into the ring $\mathbb{Z}[x]/f(x)$, where
$f(x)=(x+1)(x^{p-1}-x-1)$ is reducible.

The lattice basis of is

$\mathbf{B}=\begin{pmatrix}0&-1&-1&0&0&\cdots&1\\\ 1&1&-1&-1&0&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\end{pmatrix}.$

Note that the greatest common divisor $d$ of the entries in the last column is
$1$. According to Theorem 3.1, it’s sufficient to verify the following
relation:

$\sigma((x+1)(x^{p-1}-x-1)-(x^{p}-x-1))=(0,-1,-1,0,\cdots,1)\in\mathcal{L}(\mathbf{B}),$

and $(0,-1,-1,0,\cdots,1)$ is exactly the first row of $\mathbf{B}$.

##  4 Identifying an Ideal Lattice

We also present an algorithm to identify the ideal lattice, which is faster
than that in [13].

###  4.1 Main theorem

Inspired by Theorem 3.1, we find a new equivalent condition between integer
lattices and coefficient-embedding ideal lattices, which is described as
below.

###### Theorem 4.1

Given a full-rank integer lattice $\mathcal{L}(\mathbf{B})$, let
$\mathbf{B}^{\prime}=\begin{pmatrix}\mathbf{D}&\mathbf{0}\\\
\mathbf{b^{\prime}}&b_{n,n}^{\prime}\end{pmatrix}$ be any Incomplete Hermit
Normal Form of $\mathbf{B}$. Then $\mathcal{L}(\mathbf{B})$ is an ideal
lattice if and only if there exists a $\mathbf{T}\in\mathbb{Z}^{(n-1)\times
n}$,
s.t.$\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}=\mathbf{T}\mathbf{B}$.

###### Proof

It can be easily check the “only if” part by Lemma 4, since for an ideal
lattice $\mathcal{L}(\mathbf{B})$ in $\mathbb{Z}[x]/g(x)$, there exists a
$\mathbf{T}\in\mathbb{Z}^{(n-1)\times n}$, s.t.
$\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}=\mathbf{T}\mathbf{B}$ if
and only if $\sigma(x\sigma^{-1}(\mathbf{b}^{\prime}_{i})\mod
g(x))\in\mathcal{L}(\mathbf{B})$ for $i=1,\cdots,n-1$.

For “if” part, to indicate that $\mathcal{L}(\mathbf{B})$ is an ideal lattice,
we need to find a monic polynomial $g(x)$ of degree $n$, s.t.
$\mathcal{L}(\mathbf{B})$ can be embedded as an ideal into
$\mathbb{Z}[x]/g(x)$, or $\sigma(x\sigma^{-1}(\mathbf{b}^{\prime}_{i})\mod
g(x))\in\mathcal{L}(\mathbf{B})$ for $i=1,\cdots,n$ by Lemma 4.

Note that for any polynomial $g(x)$ with degree $n$,
$\sigma(x\sigma^{-1}(\mathbf{b}^{\prime}_{i})\mod
g(x))\in\mathcal{L}(\mathbf{B})$ for $i=1,\cdots,n-1$ since there exists a
$\mathbf{T}\in\mathbb{Z}^{(n-1)\times n}$, s.t.
$\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}=\mathbf{T}\mathbf{B}$.

It remains to show that there exists a monic polynomial $g(x)$ of degree $n$,
such that $\sigma(x\sigma^{-1}(\mathbf{b}^{\prime}_{n})\mod
g(x))\in\mathcal{L}(\mathbf{B})$.

We first present a lemma, which will be proven later.

###### Lemma 6

If $\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}=\mathbf{T}\mathbf{B}$,
then $\mathbf{B}^{\prime}/b_{n,n}^{\prime}\in\mathbb{Z}^{(n-1)\times(n-1)}$

By Lemma 6,
$\frac{1}{b_{n,n}^{\prime}}(\begin{pmatrix}0&\mathbf{b}^{\prime}\end{pmatrix}+\mathcal{L}(\mathbf{B}))\subset\mathbb{Z}^{n}$.
Taking any

$\mathbf{g}=\begin{pmatrix}g_{1}&g_{2}&\cdots&g_{n}\end{pmatrix}\in\frac{1}{b_{n,n}^{\prime}}(\begin{pmatrix}0&\mathbf{b}^{\prime}\end{pmatrix}+\mathcal{L}(\mathbf{B})),$
(3)

the integer polynomial $g(x)=x^{n}+g_{n}x^{n-1}+\cdots+g_{1}$ is what we want,
since

$\sigma(x\sigma^{-1}(\mathbf{b}^{\prime}_{n})\mod
g(x))=\begin{pmatrix}0&\mathbf{b}^{\prime}\end{pmatrix}-{b_{n,n}^{\prime}}\begin{pmatrix}g_{1}&g_{2}&\cdots&g_{n}\end{pmatrix}\in\mathcal{L}(\mathbf{B}).$

It remains to prove Lemma 6.

###### Proof

(Lemma 6) According to Lemma 2, $\mathcal{L}(\mathbf{B}^{\prime})$ has a
unique HNF basis, denoted by $\mathbf{H}=(h_{i,j})_{1\leq i\leq n,1\leq j\leq
n}$. By Lemma 3, we know that $b_{n,n}^{\prime}=h_{n,n}$.

It can be easily concluded that the lattice $\mathcal{L}(\mathbf{D})$ has a
unique HNF basis, $\mathbf{H}^{\prime}=(h_{i,j})_{1\leq i\leq n-1,1\leq j\leq
n-1}$, which implies that there exists a unimodular matrix
$\mathbf{U}\in\mathbb{Z}^{(n-1)\times(n-1)}$ such that
$\mathbf{H}^{\prime}=\mathbf{U}\mathbf{D}$.

Since
$\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}=\mathbf{T}\mathbf{B}$, we
have
$\mathbf{U}\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}=\mathbf{U}\mathbf{T}\mathbf{B}$,
which is exactly

$\begin{pmatrix}0&h_{1,1}&0&...&0\\\ 0&h_{2,1}&h_{2,2}&...&0\\\ .&.&.&.&.\\\
0&h_{n-1,1}&h_{n-1,2}&...&h_{n-1,n-1}\end{pmatrix}=\mathbf{U}\mathbf{T}\mathbf{B}.$
(4)

Note that
$\mathcal{L}(\mathbf{U}\mathbf{T}\mathbf{B})\subset\mathcal{L}(\mathbf{B})$.
What Equation (4) tells us is

$\sigma(x\sigma^{-1}(\mathbf{h}_{k}))\in\mathcal{L}(\mathbf{B}),\mbox{ for
}k=1,\cdots,n-1.$

By the discussion in Remark 1, we have $b_{n,n}^{\prime}=h_{n,n}|\mathbf{B}$.

###  4.2 Algorithm and analysis

According to Theorem 4.1, there is a very simple algorithm to identify if a
given integer lattice is an ideal lattice or not.

Algorithm 4.2 Identifying an ideal lattice

1:$\mathbf{B}\in\mathbb{Z}^{n\times n}$, $\text{rank}(\mathbf{B})=n$.

2:False if $\mathcal{L}(\mathbf{B})$ is not a coefficient-embedding ideal
lattice; Otherwise output a set $S\subset\mathbb{Z}^{n}$ s.t. for any
$(g_{1},g_{2},...,g_{n})\in S$, $\mathcal{L}(\mathbf{B})$ can be embedded as
an ideal into $\mathbb{Z}[x]/(g_{1}x+g_{2}x^{2}+...+g_{n}x^{n-1}+x^{n})$.

3:Compute any Incomplete Hermit Normal Form
$\mathbf{B}^{\prime}=\begin{pmatrix}\mathbf{D}&\mathbf{0}\\\
\mathbf{b^{\prime}}&b_{n,n}^{\prime}\end{pmatrix}$ of $\mathbf{B}$ by
unimodular transformation;

4:if $b_{n,n}^{\prime}\not|\ \mathbf{B}$ then return False;

5:end if

6:if
$\begin{pmatrix}\mathbf{0}&\mathbf{D}\end{pmatrix}\mathbf{B}^{-1}\notin\mathbb{Z}^{(n-1)\times
n}$ then return False;

7:end if

8:Output
$S=\frac{1}{b^{\prime}_{n,n}}(\begin{pmatrix}0&\mathbf{b}^{\prime}\end{pmatrix}+\mathcal{L}(\mathbf{B}))$.

###### Remark 3

In Step 1, we can also compute the HNF of $\mathcal{L}(\mathbf{B})$, and then
use the divisibility relation described in Lemma 5 to rule out some integer
lattices that can’t be embedded as an ideal into any polynomial ring. This may
speedup the algorithm in practice, since many "random" integer lattices can
not pass such check.

##### Correctness

The correctness of our algorithm is guaranteed by Theorem 4.1.

##### Complexity

We next analyze the time complexity.

For Step 1, we can use the following algorithm to compute an Incomplete
Hermite Normal Form for $\mathbf{B}\in\mathbb{Z}^{n\times n}$ with a
unimodular transformation, whose idea has already been described in Section
2.2.

Algorithm 4.3 Computing an Incomplete Hermite Normal Form

1:$\mathbf{B}\in\mathbb{Z}^{n\times n}$, $\text{rank}(\mathbf{B})=n$.

2:An Incomplete Hermit Normal Form of $\mathbf{B}$ by unimodular
transformation.

3:for $i$ from 1 to $n-1$ do

4: Use Extended Euclidean Algorithm with input $(b_{i,n},b_{i+1,n})$ to find
$x$, $y$, $d$ s.t. $xb_{i,n}+yb_{i+1,n}=\gcd(b_{i,n},b_{i+1,n})=d$;

5: Update $\begin{pmatrix}\mathbf{b_{i}}\\\ \mathbf{b_{i+1}}\end{pmatrix}$:=
$\begin{pmatrix}-b_{i+1,n}/d&b_{i,n}/d\\\
x&y\end{pmatrix}\begin{pmatrix}\mathbf{b_{i}}\\\
\mathbf{b_{i+1}}\end{pmatrix}$;

6:end for

7:Output $\mathbf{B}$.

It is easy to check that the integer matrix
$\begin{pmatrix}-b_{i+1,n}/d&b_{i,n}/d\\\ x&y\end{pmatrix}$ is unimodular
since its determinant is $-1$. Hence, the transformation in Step 3 will not
change the lattice $\mathcal{L}(\mathbf{B})$. After Step 3 for each $i$, we
have $b_{i,n}=0$ and $b_{i+1,n}=d$ computed by Step 2, which means that the
output is in Incomplete Hermite Normal Form.

For the time complexity, we assume that for the input $\mathbf{B}$, the
absolute value of its every entry is bounded by $2^{B}$.

It is easy to conclude that for the $i$-th loop, at the beginning, we have

  * •

$|b_{i,j}|<2^{i*B+1}$, $|b_{i+1,j}|<2^{B}$ for $j=1,\cdots,n$, especially we
have $|b_{i,n}|<2^{B}$;

  * •

$|x|<2^{B}$, $|y|<2^{B}$, $d<2^{B}$.

Note that the Extended Euclidean Algorithm takes
$O(\text{log}|a|\text{log}|b|)$ bit operations on input $(a,b)$. Then for the
$i$-th loop, with the plain integer multiplication we have:

  * •

Step 2 costs $O(B^{2})$ bit operations;

  * •

Step 3 costs $O(i*nB^{2})$ bit operations;

Hence, for the total $n$ loops, Algorithm 4.3 needs $O(n^{3}B^{2})$ bit
operations, and we have the following result.

###### Lemma 7

For a non-singular matrix $\mathbf{B}\in\mathbb{Z}^{n\times n}$, the absolute
value of whose entries is bounded by $2^{B}$, Algorithm 4.3 takes
$O(n^{3}B^{2})$ bit operations to compute an Incomplete Hermite Normal Form of
$\mathbf{B}$ by a unimodular transformation.

For Step 4, we refer to Theorem 37 of [27] for more details.

######  Theorem 4.4 (Theorem 37 in [27])

There exists a Las Vegas algorithm that takes as input a non-singular
$\mathbf{A}\in\mathbb{Z}^{n\times n}$ and $\mathbf{b}\in\mathbb{Z}^{n}$, and
returns as output the vector $\mathbf{b}\mathbf{A}^{-1}\in\mathbb{Q}^{n}$. If
the absolute value of the entries of $\mathbf{A}$ is bounded by $2^{B}$, and
the absolute value of the entries of $\mathbf{b}$ is bounded by $2^{nB}$, then
the expected cost of the algorithm is $O((\log
n)\mathbf{MM}(n)\mathbf{MZ}(B+\log n))$ bit operations, where $\mathbf{MM}(n$)
means two $n\times n$ matrices can be multiplied using at most
$\mathbf{MM}(n)$ integer multiplications and $\mathbf{MZ}(B$) means two
$B$-bits integer can be multiplied using at most $\mathbf{MZ}(B)$ bit
operations. This result assumes that $\mathbf{MZ}(t)=O(\mathbf{MM}(t)/t)$.

It is It is well known that the classical plain multiplication method allows
$\mathbf{MZ}(B)=O(B^{2})$, and the Schönhage-Strassen algorithm [25] allows
$\mathbf{MZ}(B)=O(B(\text{log}B$)((log $\text{log}B$).

For $\mathbf{MM}(n)$, the classical plain multiplication method allows
$\mathbf{MM}(n)=2n^{3}-n^{2}$, and the asymptotically faster method allows
$\mathbf{MM}(n)=O(n^{2.376})$. We refer to [28] and [10] for more details and
further discussion.

For simplicity, we adopt the classical plain method for both integer
multiplication and matrix multiplication, that is $\mathbf{MZ}(B)=O(B^{2})$
and $\mathbf{MM}(n)=O(n^{3})$. Then by Theorem 4.4 a simple analysis shows
that Step 4 in Algorithm 4.2 costs $O(n^{4}\log n(B+\log n)^{2})$ bit
operations

Together with Lemma 7, we have

###### Theorem 4.5

Given $\mathbf{B}\in\mathbb{Z}^{n\times n}$, $\text{rank}(\mathbf{B})=n$, and
the absolute value of the entries of $\mathbf{B}$ is bounded by $2^{B}$, then
there is a Las Vegas algorithm with expected complexity $O(n^{4}\log n(B+\log
n)^{2})$ to identify whether $\mathcal{L}(\mathbf{B})$ is an ideal lattice or
not.

###### Remark 4

It is claimed in [13] that the algorithm presented by Ding and Lindner to
identify an ideal lattice costs $O(n^{4}B^{2})$ bit operations. However, we
have to point out that there is some flaw in the complexity analysis in
$O(n^{4}B^{2})$. The algorithm in [13] needs to compute $n-2$ powers of
$\mathbf{B}$, that is, $\mathbf{B}^{k}$ for $k=2,\cdots,n-1$. It is claimed
this can be done within $O(n^{4}B^{2})$ bit operations. However, when $k$
grows bigger, the bit size of the entries in $\mathbf{B}^{k}$ will be $O(kB)$
instead of $B$. Hence the correct time complexity should be

$\sum_{k=2}^{n-1}O(n^{3}*k*B^{2})=O(n^{5}B^{2}).$

So our algorithm is faster than the algorithm in [13], due to the fact that
our algorithm just checks if the systems of equations have integer solutions
or not.

##  5 Conclusion

In this paper, we reveal the embedding relation between the coefficient-
embedding ideal lattice and the integer lattice, which gives us a new method
to solve the ideal lattice problems by embedding the given ideal lattice into
the well-studied polynomial ring.

Hence, it’s not proper anymore to judge the security of a crypstosystem based
on ideal lattice by just considering a single ring. The embedding relation no
doubt increases the difficulties of evaluating the security for any
crypstosystem based on ideal lattices.

Since the ideal lattice is a special case of the module lattice, it’s possible
that there is a similar embedding relation between integer lattices and module
lattices. Therefore, it’s worth researching that how to generalize our theory
to module lattice.

## References

  * [1] Ajtai, M. Generating Hard Instances of Lattice Problems. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 99–108. CiteSeerX 10.1.1.40.2489. doi:10.1145/237814.237838. ISBN 978-0-89791-785-8. S2CID 6864824.(1996)
  * [2] Ajtai, M. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. pp. 10–19. STOC ’98, ACM, New York, NY, USA (1998)
  * [3] Ajtai, M.; Dwork, C. A Public-Key Crypstosystem with Worst-Case/ Average-Case Equivalence. Electronic Colloquium on Computational Complexity-Report Series 1996.-available via: http://www.eccc.uni-trier.de/eccc/(1997)
  * [4] Batson, S.C. The linear transformation that relates the canonical and coefficient embeddings of ideal in cyclotomic integer rings.International Journal of Number Theory. Vol.13, No.09, pp. 2277-2297.https://www.worldscientific.com/doi/abs/10.1142/S1793042117501251(2017)
  * [5] Bernard, O.; Roux-Langlois, A. Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices. International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT 2020: Advances in Cryptology – ASIACRYPT 2020 pp 349–380. https://doi.org/10.1007/978-3-030-64834-3_12. (2020)
  * [6] Bernard, O.; Lesavourey, A.; Nguyen T.; Roux-Langlois, A. Log-S-unit Lattices Using Explicit Stickelberger Generators to Solve Approx Ideal-SVP. International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT 2022: Advances in Cryptology – ASIACRYPT 2022 pp 677–708.https://doi.org/10.1007/978-3-031-22969-5_23 (2022)
  * [7] Bernstein, D.; Brumley, B.; Chen, M.; Chuengsatiansup, C.; Lange, T.; Marotzke, A.; Peng, B.; Tuveri, N.; Vredendaal, C.; Yang, B. NTRU Prime: round 3(20201007). https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf (2020)
  * [8] Boudgoust, K.; Gachon, E.; Pellet-Mary, A. Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem. Annual International Cryptology Conference. CRYPTO 2022: Advances in Cryptology – CRYPTO 2022 pp 480–509.https://doi.org/10.1007/978-3-031-15979-4_17 (2022)
  * [9] Buchmann, J.; Lindner, R. Density of Ideal Lattices. Algorithms and Number Theory 2009 Mathematics, Computer Science.(2009)
  * [10] Buergisser, P.; Clausen, M.; Shokrollahi, M. A. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag.(1996)
  * [11] Cramer, R.; Ducas, L.; Peikert, C.; Regev, O. Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.)EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg. doi:10.1007/978-3-662-49896-520(2016)
  * [12] Cramer, R.; Ducas, L.; Wesolowski, B. Short Stickelberger class relations and application to ideal-SVP. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 324–348. Springer, Cham. https://doi.org/10.1007/978-3-319-56620-7 12(2017)
  * [13] Ding, J.; Lindner, R. Identifying Ideal Lattices. https://eprint.iacr.org/2007/322.pdf(2007)
  * [14] Domich, P.D., Kannan, R., Trotter, L.E.: Hermite Normal Form Computation Using Modulo Determinant Arithmetic. Mathematics of Operations Research 12(1), 50-59 (1987).
  * [15] Hoffstein, J.; Pipher, J.; Silverman, J. H. NTRU: A ring-based public key cryptosystem. Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1423. pp. 267–288. CiteSeerX 10.1.1.25.8422. doi:10.1007/bfb0054868. ISBN 978-3-540-64657-0.(1998)
  * [16] Holzer, P.; Wunderer, T.; Buchmann, J.A.: Recovering short generators of principal fractional ideals in cyclotomic fields of conductor $p^{\alpha}q^{\beta}$. In: Patra, A., Smart, N.P. (eds.) INDOCRYPT 2017. LNCS, vol. 10698, pp. 346–368. Springer, Cham. https://doi.org/10.1007/978-3-319-71667-1 18(2017)
  * [17] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. hdl:1887/3810. MR 0682664. S2CID 5701340.(1982)
  * [18] Liu, R., Pan, Y.: Computing Hermite Normal Form Faster via Solving System of Linear Equations. In: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation. pp. 283-290. ACM (2019).
  * [19] Lyubashevsky, V.; Peikert, C.; Regev, O. On Ideal Lattices and Learning with Errors over Rings. Advances in Cryptology – Eurocrypt 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. CiteSeerX 10.1.1.352.8218. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.(2010-05-30)
  * [20] Micciancio, D., Warinschi, B.: A Linear Space Algorithm for Computing the Hermite Normal Form. In: Proceedings of the 2001 International Symposium on Symbolic and Algebraic Com- putation. pp. 231-236. ACM (2001).
  * [21] Pan, Y.; Xu, J.; Wadleigh, N.; Cheng, Q. On the Ideal Shortest Vector Problem over Random Rational Primes. Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT 2021: Advances in Cryptology – EUROCRYPT 2021 pp 559–583. https://doi.org/10.1007/978-3-030-77870-5_20 (2021)
  * [22] Peikert, C., Regev, O., Stephens-Davidowitz, N. Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 461–473. https://doi.org/10.1145/3055399.3055489(2017)
  * [23] Pellet-Mary, A.; Hanrot, G.; Stehlé, D. Approx-svp in ideal lattices with preprocessing. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 685–716. Springer(2019)
  * [24] Regev, O. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC ’05. ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776. doi:10.1145/1060590.1060603. ISBN 978-1581139600. S2CID 53223958.(2005-01-01)
  * [25] Schönhage, A.; Strassen, V. Schnelle Multiplikation grosser. Zahlen Computing, 7:281-292 (1971)
  * [26] Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science (1987)
  * [27] Storjohann, A. The shifted number system for fast linear algebra on integer matrices. In Journal of Complexity, Pages 609-650.https://www.sciencedirect.com/science/article/pii/S0885064X05000312(2005)
  * [28] von zur Gathen, J.; Gerhard, J. Mordern Computer Algebra. Cambridge University Press, 2 edition. (2003)
  * [29] Zhang, Y.; Liu, R.; Lin, D. Improved Key Generation Algorithm for Gentry’s Fully Homomorphic Ecryption Scheme. In Computer Science , Cryptography and Security.arXiv:1709.06724.(2017)