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

31 questions
2k views

### lcm versus phi in RSA

In textbook RSA, the Euler $\varphi$ function $$\varphi(pq) := (p-1)(q-1)$$ is used to define the private exponent $d$. On the other hand, real-world cryptographic specifications require the ...
5k views

### How to determine the order of an elliptic curve group from its parameters?

Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the ...
4k views

### Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective. RSA labs makes a similar statement: The discrete logarithm problem bears the same ...
1k views

### Block cipher fixed points (plaintext equal to ciphertext)

A block cipher is a bijective map from the set of possible plaintexts to the set of ciphertexts, which are the same size and might as well be considered the same thing: $\theta: S\to S$. In this there ...
2k views

### When do we need composite order groups for bilinear maps and when prime order?

Why we need bilinear groups of composite order? What's the special security property of the composite order group in comparison with one of prime order? To put it in another way when do we need ...
3k views

### Cycle attack on RSA

I originally posted this question in the mathematics section, you can see it here. Let $p$ and $q$ be large primes, $n=pq$ and $e : 0<e<\phi(n), \space gcd(e, \phi(n))=1$ the public encyption ...
312 views

792 views

### What is a cyclic group of prime order q such that the DLP is hard?

On the original paper on Linked Ring Signatures, in order to construct its scheme, the author relies on this: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the ...
2k views

### Find the generators of multiplicative group of units efficiently?

Say you're give some prime numbers $p_{1},p_{2},p_{3}, p = 2p_{1}p_{2}p_{3} + 1$ (which is assumed to be also prime) and a list of numbers $L$ and you're asked to find the generators of the ...
231 views

### Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?

I know that there are elliptic curve groups, used in pairing-based cryptography, where the decisional Diffie Hellman problem (ie. given $g$, $g^a$, $g^b$ and $c$, determine if $c = g^{ab}$ is easy but ...
3k views

### What are Cryptographic Multi-linear Maps?

I've encountered this term many times in the fields of Fully-Homomorphic Encryption and Obfuscation. I want to learn those subjects and Cryptographic Linear Maps seems to be an obstacle in the way. ...
1k views

### How does the wider cryptographic community view non-abelian group based cryptography?

Is there perhaps some neural expository article on crypto systems based on non-abelian groups? I've gleaned that Anshel–Anshel–Goldfeld key exchange is the most well-known cryptographic algorithm ...
661 views

### How to find an element of high-order in an RSA group?

Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements. What happens if you use the RSA group in a scenario where you want that ...
597 views

### Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step. For example, Alice and Bob’s public keys appear to only use the closure property of a group and maybe identity (e....
160 views

### Why do elliptic curves require fewer bits for the same security level?

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
626 views

### How is the order of a point calculated for elliptic curves over GF(p)

My question is about elliptic curves over $GF(p)$: How is the order of a generating element $G$ (which is to my knowledge also the order of the cyclic subgroup $G^n$) calculated? Taking P-256 as an ...
335 views

### Can anyone give an example where (asymmetric) crypto can go wrong due to selection of wrong groups?

Basically the title says it all. It would be great if someone could tell give an example using provable security. More information about groups can be found at: https://en.wikipedia.org/wiki/Group_(...
154 views

### $L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
409 views

1k 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 ...
72 views

165 views

### Hash “Preimage by product” resistance

Let H() be a hash function that achieves collision resistance as well as first and second preimage resistance. Let's equip the output set of H of a multiplicative group structure, more precisely a ...
215 views

### Discrete logarithm problem in subgroup of index 2. ElGamal

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 ...
As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime $p$ and use a multiplicative cyclic group with modulus $p$ and order $q = (p-1)/2$. ...