Learning with Errors over Group Rings Constructed by Semi-direct Product

• URL: http://arxiv.org/abs/2311.15868v2
• Date: Fri, 1 Dec 2023 15:33:09 GMT
• Title: Learning with Errors over Group Rings Constructed by Semi-direct Product
• Authors: Jiaqi Liu, Fang-Wei Fu,
• Abstract summary: Group ring LWE (GR-LWE) is an extension of the Learning with Errors (LWE) problem. As an extension of Ring-LWE, GR-LWE maintains computational hardness and can be potentially applied in many scenarios. GR-LWE samples can be leveraged to construct semantically secure public-keysystems.
• Score: 26.148950348885972
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Learning with Errors (LWE) problem has been widely utilized as a foundation for numerous cryptographic tools over the years. In this study, we focus on an algebraic variant of the LWE problem called Group ring LWE (GR-LWE). We select group rings (or their direct summands) that underlie specific families of finite groups constructed by taking the semi-direct product of two cyclic groups. Unlike the Ring-LWE problem described in \cite{lyubashevsky2010ideal}, the multiplication operation in the group rings considered here is non-commutative. As an extension of Ring-LWE, it maintains computational hardness and can be potentially applied in many cryptographic scenarios. In this paper, we present two polynomial-time quantum reductions. Firstly, we provide a quantum reduction from the worst-case shortest independent vectors problem (SIVP) in ideal lattices with polynomial approximate factor to the search version of GR-LWE. This reduction requires that the underlying group ring possesses certain mild properties; Secondly, we present another quantum reduction for two types of group rings, where the worst-case SIVP problem is directly reduced to the (average-case) decision GR-LWE problem. The pseudorandomness of GR-LWE samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems.

Related papers

• VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
  Lattice-based cryptography is a foundation for post-quantum security. This work introduces Variety-LWE (VLWE), a new structured lattice problem based on algebraic geometry. We prove VLWE's security by reducing it to multiple independent instances, demonstrating resilience against classical and quantum attacks.
  arXiv  Detail & Related papers  (2025-02-11T06:04:24Z)
• A parameter study for LLL and BKZ with application to shortest vector problems [0.20971479389679337]
  Two well-known algorithms that can be used to simplify a given SVP are the Lenstra-Lenstra-Lov'asz (LLL) algorithm and the Block Korkine-Zolotarev (BKZ) algorithm. We study the performance of both algorithms for SVPs with different sizes and modular rings.
  arXiv  Detail & Related papers  (2025-02-07T18:41:44Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Lattice attack on group ring NTRU: The case of the dihedral group [2.106410091047004]
  This paper shows that dihedral groups do not guarantee better security against lattice attacks on the public key of NTRU-like cryptosystems. We prove that retrieving the private key is possible by solving the SVP in two lattices with half the dimension of the original lattice generated for GR-NTRU based on dihedral groups.
  arXiv  Detail & Related papers  (2023-09-15T10:50:46Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability. IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• The dihedral hidden subgroup problem [0.0]
  We give an exposition of the hidden problem for dihedral groups from the point of view of the standard subgroup quantum algorithm for finite groups. We explain a new connection between the dihedral coset problem and cloning of quantum states.
  arXiv  Detail & Related papers  (2021-06-18T04:19:10Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Robust subgroup discovery [0.2578242050187029]
  We formalize the problem of optimal robust subgroup discovery using the Minimum Description Length principle. We propose RSD, a greedy greedy that finds good subgroup lists and guarantees that the most significant subgroup is added in each iteration. We empirically show on 54 datasets that RSD outperforms previous subgroup set discovery methods in terms of quality and subgroup list size.
  arXiv  Detail & Related papers  (2021-03-25T09:04:13Z)
• GroupifyVAE: from Group-based Definition to VAE-based Unsupervised Representation Disentanglement [91.9003001845855]
  VAE-based unsupervised disentanglement can not be achieved without introducing other inductive bias. We address VAE-based unsupervised disentanglement by leveraging the constraints derived from the Group Theory based definition as the non-probabilistic inductive bias. We train 1800 models covering the most prominent VAE-based models on five datasets to verify the effectiveness of our method.
  arXiv  Detail & Related papers  (2021-02-20T09:49:51Z)

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.