Contracting Self-similar Groups in Group-Based Cryptography

• URL: http://arxiv.org/abs/2408.14355v1
• Date: Mon, 26 Aug 2024 15:30:11 GMT
• Title: Contracting Self-similar Groups in Group-Based Cryptography
• Authors: Delaram Kahrobaei, Arsalan Akram Malik, Dmytro Savchuk,
• Abstract summary: We propose self-similar contracting groups as a platform for cryptographic schemes based on simultaneous conjugacy search problem (SCSP) The class of these groups contains extraordinary examples like Grigorchuk group, which is known to be non-linear. We discuss benefits and drawbacks of using these groups in group-based cryptography and provide computational analysis of variants of the length-based attack on SCSP.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose self-similar contracting groups as a platform for cryptographic schemes based on simultaneous conjugacy search problem (SCSP). The class of these groups contains extraordinary examples like Grigorchuk group, which is known to be non-linear, thus making some of existing attacks against SCSP inapplicable. The groups in this class admit a natural normal form based on the notion of a nucleus portrait, that plays a key role in our approach. While for some groups in the class the conjugacy search problem has been studied, there are many groups for which no algorithms solving it are known. Moreover, there are some self-similar groups with undecidable conjugacy problem. We discuss benefits and drawbacks of using these groups in group-based cryptography and provide computational analysis of variants of the length-based attack on SCSP for some groups in the class, including Grigorchuk group, Basilica group, and others.

Related papers

• Subsets of groups in public-key cryptography [0.46960837342692324]
  We present the subset version of two protocols introduced by Shpilrain and Ushakov with some examples in ascending HNN-extensions of free-abelian groups. We also introduce several new group theoretic problems arising from this work.
  arXiv  Detail & Related papers  (2023-11-25T14:35:36Z)
• Cryptanalysis of protocols using (Simultaneous) Conjugacy Search Problem in certain Metabelian Platform Groups [0.0]
  There are many group-based cryptosystems in which the security relies on the difficulty of solving Conjugacy Search Problem (CSP) and Simultaneous Conjugacy Search Problem (SCSP) in their underlying platform groups. In this paper we give a cryptanalysis of these systems which use certain semidirect product of abelian groups.
  arXiv  Detail & Related papers  (2023-09-25T07:50:25Z)
• 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)
• Applications of Finite non-Abelian Simple Groups to Cryptography in the Quantum Era [0.0]
  We review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central. We look at constructions based on various group-theoretic factorization problems, review group theoretical hash functions, and discuss fully homomorphic encryption using simple groups.
  arXiv  Detail & Related papers  (2023-08-28T17:30:00Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Outlier-Robust Group Inference via Gradient Space Clustering [50.87474101594732]
  Existing methods can improve the worst-group performance, but they require group annotations, which are often expensive and sometimes infeasible to obtain. We address the problem of learning group annotations in the presence of outliers by clustering the data in the space of gradients of the model parameters. We show that data in the gradient space has a simpler structure while preserving information about minority groups and outliers, making it suitable for standard clustering methods like DBSCAN.
  arXiv  Detail & Related papers  (2022-10-13T06:04:43Z)
• Multiple Fairness and Cardinality constraints for Students-Topics Grouping Problem [14.051419173519308]
  Group work is a prevalent activity in educational settings, where students are often divided into topic-specific groups based on their preferences. We introduce the multi-fair capacitated (MFC) grouping problem that fairly partitions students into non-overlapping groups. We propose two approaches: a method and a knapsack-based method to obtain the grouping.
  arXiv  Detail & Related papers  (2022-06-20T17:06:10Z)
• Focus on the Common Good: Group Distributional Robustness Follows [47.62596240492509]
  This paper proposes a new and simple algorithm that explicitly encourages learning of features that are shared across various groups. While Group-DRO focuses on groups with worst regularized loss, focusing instead, on groups that enable better performance even on other groups, could lead to learning of shared/common features.
  arXiv  Detail & Related papers  (2021-10-06T09:47:41Z)
• Learning Multi-Attention Context Graph for Group-Based Re-Identification [214.84551361855443]
  Learning to re-identify or retrieve a group of people across non-overlapped camera systems has important applications in video surveillance. In this work, we consider employing context information for identifying groups of people, i.e., group re-id. We propose a novel unified framework based on graph neural networks to simultaneously address the group-based re-id tasks.
  arXiv  Detail & Related papers  (2021-04-29T09:57:47Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)
• Overcoming Data Sparsity in Group Recommendation [52.00998276970403]
  Group recommender systems should be able to accurately learn not only users' personal preferences but also preference aggregation strategy. In this paper, we take Bipartite Graphding Model (BGEM), the self-attention mechanism and Graph Convolutional Networks (GCNs) as basic building blocks to learn group and user representations in a unified way.
  arXiv  Detail & Related papers  (2020-10-02T07:11:19Z)

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.