Lattice attack on group ring NTRU: The case of the dihedral group

• URL: http://arxiv.org/abs/2309.08304v1
• Date: Fri, 15 Sep 2023 10:50:46 GMT
• Title: Lattice attack on group ring NTRU: The case of the dihedral group
• Authors: Vikas Kumar, Ali Raya, Sugata Gangopadhyay, Aditi Kar Gangopadhyay,
• Abstract summary: 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.
• Score: 2.106410091047004
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Group ring NTRU (GR-NTRU) provides a general structure to design different variants of NTRU-like schemes by employing different groups. Although, most of the schemes in literature are built over cyclic groups, nonabelian groups can also be used. Coppersmith and Shamir in 1997 have suggested that noncommutativity may result in better security against some lattice attacks for some groups. Lattice attacks on the public key of NTRU-like cryptosystems try to retrieve the private key by solving the shortest vector problem (SVP) or its approximation in a lattice of a certain dimension, assuming the knowledge of the public key only. This paper shows that dihedral groups do not guarantee better security against this class of attacks. 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. The possibility of such an attack was mentioned by Yasuda et al.(IACR/2015/1170). In contrast to their proposed approach, we explicitly provide the lattice reduction without any structure theorem from the representation theory for finite groups. Furthermore, we demonstrate the effectiveness of our technique with experimental results.

Related papers

• Contracting Self-similar Groups in Group-Based Cryptography [0.0]
  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.
  arXiv  Detail & Related papers  (2024-08-26T15:30:11Z)
• Symmetric Encryption Scheme Based on Quasigroup Using Chained Mode of Operation [1.4249472316161877]
  We propose a novel construction for a symmetric encryption scheme, referred as SEBQ. We utilize concepts of chaining like mode of operation and present a block cipher with in-built properties.
  arXiv  Detail & Related papers  (2024-08-08T14:39:51Z)
• 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)
• Uncovering Prototypical Knowledge for Weakly Open-Vocabulary Semantic Segmentation [59.37587762543934]
  This paper studies the problem of weakly open-vocabulary semantic segmentation (WOVSS) Existing methods suffer from a granularity inconsistency regarding the usage of group tokens. We propose the prototypical guidance network (PGSeg) that incorporates multi-modal regularization.
  arXiv  Detail & Related papers  (2023-10-29T13:18:00Z)
• PRAT: PRofiling Adversarial aTtacks [52.693011665938734]
  We introduce a novel problem of PRofiling Adversarial aTtacks (PRAT) Given an adversarial example, the objective of PRAT is to identify the attack used to generate it. We use AID to devise a novel framework for the PRAT objective.
  arXiv  Detail & Related papers  (2023-09-20T07:42:51Z)
• 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)
• Equivariant Transduction through Invariant Alignment [71.45263447328374]
  We introduce a novel group-equivariant architecture that incorporates a group-in hard alignment mechanism. We find that our network's structure allows it to develop stronger equivariant properties than existing group-equivariant approaches. We additionally find that it outperforms previous group-equivariant networks empirically on the SCAN task.
  arXiv  Detail & Related papers  (2022-09-22T11:19:45Z)
• 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)
• A Group Key Establishment Scheme [1.4091801425319967]
  Group authentication is a method of confirming that a set of users belong to a group. Unlike the standard authentication schemes where one central authority authenticates users one by one, group authentication can handle the authentication process at once for all members of the group.
  arXiv  Detail & Related papers  (2021-09-30T12:04:55Z)
• 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)
• AN-GCN: An Anonymous Graph Convolutional Network Defense Against Edge-Perturbing Attack [53.06334363586119]
  Recent studies have revealed the vulnerability of graph convolutional networks (GCNs) to edge-perturbing attacks. We first generalize the formulation of edge-perturbing attacks and strictly prove the vulnerability of GCNs to such attacks in node classification tasks. Following this, an anonymous graph convolutional network, named AN-GCN, is proposed to counter edge-perturbing attacks.
  arXiv  Detail & Related papers  (2020-05-06T08:15:24Z)

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.