Embedding Integer Lattices as Ideals into Polynomial Rings

• URL: http://arxiv.org/abs/2307.12497v2
• Date: Tue, 20 Feb 2024 07:08:05 GMT
• Title: Embedding Integer Lattices as Ideals into Polynomial Rings
• Authors: Yihang Cheng, Yansong Feng, Yanbin Pan,
• Abstract summary: We study the additional structure of ideal lattices further and find that a given ideal lattice in a ring can be embedded as an ideal into infinitely many different rings by embedding the coefficient. We find a flaw in Ding and Lindner's algorithm that causes some ideal lattices can't be identified by their algorithm.
• Score: 29.240943119083678
• License: http://creativecommons.org/licenses/by/4.0/
• 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 a polynomial ring can be embedded as an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given full-rank lattice in $\mathbb{Z}^n$ is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with time complexity $\mathcal{O}(n^3B(B+\log n)$, where $n$ is the dimension of the lattice and $B$ is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring that the input lattice can be embedded into with time complexity $\mathcal{O}(n^5B^2)$ in 2007. However, we find a flaw in Ding and Lindner's algorithm that causes some ideal lattices can't be identified by their algorithm.

Related papers

• Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited [4.843809993270313]
  Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional lattices holds practical significance in cryptography and computational geometry. We develop an efficient adaptive lattice reduction algorithm textbfCrossEuc that strategically applies the Euclidean algorithm across dimensions. By iteratively invoking textbfHVec, our optimized algorithm textbfHVecSBP achieves a reduced basis in $O(log n M(n) )$ time for arbitrary input bases with bit-length $n$.
  arXiv  Detail & Related papers  (2025-04-17T13:50:51Z)
• Compact Circuits for Constrained Quantum Evolutions of Sparse Operators [0.0]
  We introduce a general framework for constructing compact quantum circuits that implement the real-time evolution of Hamiltonians of the form $H = sigma P_B$. Such Hamiltonians frequently arise in quantum algorithms, including constrained mixers in QAOA, fermionic and excitation operators in VQE, and lattice gauge theory applications.
  arXiv  Detail & Related papers  (2025-04-12T08:47:59Z)
• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems. We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
  We introduce a modular arithmetic approach to the Subset Sum problem. We show that density guarantees can be improved by analysing the lengths of the LLL reduced basis vectors.
  arXiv  Detail & Related papers  (2024-08-28T19:32:14Z)
• Post-quantum encryption algorithms of high-degree 3-variable polynomial congruences: BS cryptosystems and BS key generation [0.0]
  We will construct post-quantum encryption algorithms based on three-variable Beal-Schur congruence. We will apply this result to generate simple and secure post-quantum encryption algorithms.
  arXiv  Detail & Related papers  (2024-08-14T14:19:46Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Conditional Gradients for the Approximately Vanishing Ideal [0.0]
  Conditional Conditional Gradients Approximately Vanishing Ideal algorithm (CGAVI) We introduce the Conditional Conditional Gradients Approximately Vanishing Ideal algorithm (CGAVI) for the construction of the set of generators of the approximately ideal. The constructed set of generators captures structures in data and gives rise to a feature map that can be used in combination with a linear classifier for supervised learning.
  arXiv  Detail & Related papers  (2022-02-07T16:48:49Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Efficient quantum processing of ideals in finite rings [1.1724565818034947]
  We show how to find an additive basis representation for I in poly(log |R|) time. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings.
  arXiv  Detail & Related papers  (2009-07-31T23:00:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.