# 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).

229 questions
Filter by
Sorted by
Tagged with
174 views

### RSA and the strong RSA assumptions

The RSA assumption: Given a randomly generated RSA modulus $n$, exponent $r$ and a random $z \in \mathbb{Z}_n^{*}$, find $y$ such that $y^r=z$. The strong RSA assumption: Given a randomly chosen ...
2k views

### Factoring large $N$ given oracle to find square roots modulo $N$

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ...
2k views

### Simple example to describe Bilinear mapping

Notation : $\mathbb{G}$ is an additive group and $\mathbb{G}_T$ is multiplicative group of prime order $q$. Bilinear mapping $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ has to satisfy ...
995 views

Given the finite cyclic, additive group (G, +), with |G| = n and generator = g, what are the computations and exchanged messages for Diffie-Hellman? What I tried myself: Alice chooses a private $a$ ...
83 views

### Calculating G for a give cyclic group mod P

For DH key agreement, one must begin with a generator of a cyclic group g. However, intuitively to me at least, it seems that g ...
89 views

334 views

### What does the number 256 in pairing curve BN256 indicate?

There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required ...
86 views

### Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem. I did understand how from invertible finite groups I ...
99 views

### How to compare the order of elements in cyclic groups?

In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $P_1$ and $P_2$ and find out ...
138 views

### In a additive group is it hard to calculate $bg$ given $ag, g, abg$

The ECDH problem defined that given $g,ag,bg$ it is difficult to calculate $abg$. But it is also difficult to calculate $bg$ given $ag,g,abg$. where $g$ is generator and a,b are elements of group.
40 views

### Is the CONF key sharing Problem equivalent to discrete log problem?

If there a proof in the literature which says the CONF Problem is equivalent to solving the discrete log ? Let $g$ be a generator of a cyclic group $\mathbb{G}$ of prime order $q$ CONF problem: ...
81 views

220 views

### bilinear maps rules

A bilinear map has to satisfy this property: $e(aP,bQ) = e(P,Q)^{ab}$ for all $P,Q \in \mathbb{G} , a,b \in \mathbb{Z}_q$ so far so good. My question now is related to this paper: https://eprint....
141 views

### Sum probability

if $a,b,c$ are selected at random from a large cyclic group, then what could be the probability that $g^{a+b}$=$g^c$? it simply corresponds to the probability that multiplication of two random ...
395 views

### Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a ...
I need some insight for the following problem in ElGamal encryption procedure. It is stated that ElGamal problem in a group $\mathbb{Z}_p^*$ becomes easier in subgroups. Assume I have a subgroup of ...
Frequently I have seen people use the term order in cryptography (the group theoretic one). I have a mathematical background and order (say for prime modulus $p$) is defined as the smallest integer ...