Implementation of Learning with Errors in Non-Commuting Multiplicative Groups

• URL: http://arxiv.org/abs/2509.11237v1
• Date: Sun, 14 Sep 2025 12:28:24 GMT
• Title: Implementation of Learning with Errors in Non-Commuting Multiplicative Groups
• Authors: Aleksejus Mihalkovič, Lina Dindiene, Eligijus Sakalauskas,
• Abstract summary: We show a way to generalize learning with errors to non-commuting groups.<n>We implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of M2t.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this paper, we demonstrate a way to generalize learning with errors (LWE) to the family of so-called modular-maximal cyclic groups which are non-commuting. Since the group M2t has two cycles of maximal multiplicative order, we use this fact to construct an accurate criterion for restoring the message bit with overwhelming probability. Furthermore, we implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of M2t . Also we prove that using this approach we can achieve a level of security comparable to the original idea.

Related papers

• Learning Subgroups with Maximum Treatment Effects without Causal Heuristics [16.087398572596587]
  We show that optimal subgroup discovery reduces to recovering the data-generating models and hence a standard supervised learning problem.<n>We instantiate the approach with CART, arguably one of the most widely used tree-based methods, to learn the subgroup with maximum treatment effect.
  arXiv  Detail & Related papers  (2025-11-25T11:13:05Z)
• A Unified Matrix Factorization Framework for Classical and Robust Clustering [11.62669179647184]
  This paper presents a unified matrix factorization framework for classical and robust clustering.<n>We derive an analogous matrix factorization interpretation for fuzzy c-means clustering, which to the best of our knowledge has not been previously formalized.<n>To address sensitivity to outliers, we propose robust formulations for both crisp and fuzzy clustering by replacing the Frobenius norm with the l1,2-norm.
  arXiv  Detail & Related papers  (2025-10-24T05:51:48Z)
• Safe Screening Rules for Group SLOPE [10.831609326463756]
  Group SLOPE performs well for the adaptive selection of groups of predictors.<n>However, the block non-separable group effects in Group SLOPE make existing methods either invalid or inefficient.<n>We introduce a safe screening rule tailored for the Group SLOPE model, which efficiently identifies inactive groups with zero coefficients.
  arXiv  Detail & Related papers  (2025-06-11T06:56:08Z)
• Cycles of Thought: Measuring LLM Confidence through Stable Explanations [53.15438489398938]
  Large language models (LLMs) can reach and even surpass human-level accuracy on a variety of benchmarks, but their overconfidence in incorrect responses is still a well-documented failure mode. We propose a framework for measuring an LLM's uncertainty with respect to the distribution of generated explanations for an answer.
  arXiv  Detail & Related papers  (2024-06-05T16:35:30Z)
• Learning with Errors over Group Rings Constructed by Semi-direct Product [26.148950348885972]
  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.
  arXiv  Detail & Related papers  (2023-11-27T14:38:36Z)
• Accelerated Discovery of Machine-Learned Symmetries: Deriving the Exceptional Lie Groups G2, F4 and E6 [55.41644538483948]
  This letter introduces two improved algorithms that significantly speed up the discovery of symmetry transformations. Given the significant complexity of the exceptional Lie groups, our results demonstrate that this machine-learning method for discovering symmetries is completely general and can be applied to a wide variety of labeled datasets.
  arXiv  Detail & Related papers  (2023-07-10T20:25:44Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• The non-overlapping statistical approximation to overlapping group lasso [4.197110761923662]
  We propose a separable penalty as an approximation of the overlapping group lasso penalty. Thanks to the separability, the computation of regularization based on our penalty is substantially faster than that of the overlapping group lasso. We show that the estimator based on the proposed separable penalty is statistically equivalent to the one based on the overlapping group lasso penalty.
  arXiv  Detail & Related papers  (2022-11-16T21:21:41Z)
• Log-based Sparse Nonnegative Matrix Factorization for Data Representation [55.72494900138061]
  Nonnegative matrix factorization (NMF) has been widely studied in recent years due to its effectiveness in representing nonnegative data with parts-based representations. We propose a new NMF method with log-norm imposed on the factor matrices to enhance the sparseness. A novel column-wisely sparse norm, named $ell_2,log$-(pseudo) norm, is proposed to enhance the robustness of the proposed method.
  arXiv  Detail & Related papers  (2022-04-22T11:38:10Z)
• Self-Supervised Learning Disentangled Group Representation as Feature [82.07737719232972]
  We show that existing Self-Supervised Learning (SSL) only disentangles simple augmentation features such as rotation and colorization. We propose an iterative SSL algorithm: Iterative Partition-based Invariant Risk Minimization (IP-IRM) We prove that IP-IRM converges to a fully disentangled representation and show its effectiveness on various benchmarks.
  arXiv  Detail & Related papers  (2021-10-28T16:12:33Z)
• 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.