# Questions tagged [group-theory]

Groups are an abstract algebraic concept based on a set and a group law (a binary function which closes the set).

338 questions
Filter by
Sorted by
Tagged with
231 views

### Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?

Specifically, I want an algebra group $G$ (or ring $R$) features: Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy. Given an element $g \in G$ (or $R$ ), finding the ...
1 vote
71 views

### Understanding Gentry's initial FHE construction based on ideal lattices

I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
1 vote
336 views

### DHKE: Why using safe prime gives us "safe" subgroups?

I come from the question here: Safe primes subgroup in Diffie–Hellman key exchange Where the accepted answer states that there are only 4 possible outcomes for the order of a subgroup when using a ...
1 vote
81 views

### Why exclude the last group element when picking Elgamal secret key

Christof Paar explains in his lectures that Elgamal encryption scheme picks the private key from $\{2, \ldots, p-2\}$, is there a reason for excluding the last and first elements?
157 views

### Why don't secp256k1 use a prime order subgroup?

Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack. Meanwhile, secp256k1 doesn't use a ...
98 views

### Effective key length in Enigma encryption

Each Enigma machine setting induces a certain encryption in the sense of a function from the space of plain texts to the set of cipher texts. The number of different Enigma machine settings can be ...
297 views

### How does the Legendre symbol reveal if $g^a$ is odd or even for Finite Field Diffie-Hellman

According to wikipedia(markdown is striped below) for Decisional Diffie–Hellman assumption: the DDH assumption does not hold in the multiplicative group $Z(p)$, where $p$ is prime. This is because if ...
126 views

### Safe primes subgroup in Diffie–Hellman key exchange

I'm trying to understand how the safe primes numbers are used in Diffie–Hellman key exchange. According to wiki: The order of G should have a large prime factor to prevent use of the Pohlig–Hellman ...
1 vote
273 views

### PAGE 2: Can I move elements from cyclic subgroup to its cyclic parent group?

We will continue our previous topic here⬇️ for clarity... The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b. pls read carefully- I am looking for a function/...
1 vote
230 views

### Can I move elements from cyclic subgroup to its cyclic parent group?

The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b. I know that elements of a non-prime order cyclic group G can be moved to its subgroup H by a process called &...
1 vote
89 views

### Fast Algorithms for generalized Discrete Logarithm?

I know the standard algorithms for D-log. Pollard-rho, Baby-step-big-step, Pollig-Hellman, index calculus, etc. I'm looking for fast algorithms to find a relation for the generalized discrete ...
391 views

### How to check if a number is a generator of a cyclic multiplicative group

Suppose I have a 2048 bit prime number p. Now for the group $Z_p$, could someone please tell me an efficient algorithm to check whether a randomly chosen number is a generator for the group or not
28 views

### What is a efficient algorithm to compute e(u, v) in bilinear map

My problem is about this paper Efficient k-out-of-n oblivious transfer scheme with the ideal communication cost https://www.sciencedirect.com/science/article/pii/S0304397517309143 I don't know what is ...
110 views

### Parameters needed for Chaum-Pedersen Protocol

I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime ...
1 vote
69 views

### Hidden Subgroup Problem: Embedding $G$ in a complex hilbert space $H$

In general or in specific examples, how is the group used in an instance of the hidden subgroup problem embedded into a complex Hilbert space in order to apply the quantum fourier transform needed to ...
122 views

### Division of two Elliptic curve points in KZG polynomial commitment scheme!

I have some issue to understand the verify round of the KZG polynomial commitment scheme. The following diagram is associated to the scheme. I appreciate any help. To verify, the verifier should ...
### Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?
Given some group in which both discrete logarithms and the computational Diffie-Hellman problem are hard. Furthermore, two random, unrelated group generators $G_1, G_2$, and a third generator defined ...