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

38 questions
Filter by
Sorted by
Tagged with
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

### 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 ...
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 ...
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 ...
4k 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 ...
909 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 ...
336 views

1k views

### Elliptic curve and embedding degree

I am new to ECC. I am confused about what the embedding degree in an elliptic curve group represents and what is the impact of its values on the curve and security (small values or large values?) ...
3k 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 ...
243 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 ...
722 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 ...
255 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 ...
339 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_(...
1k views

### Discrete logarithm problem is easy in a cyclic group of order a power of two

Let $G=\langle g\rangle$ be a cyclic group of order $2^{k}$ and let $h\in G$. I have read that it is easy to find $\log _{g} h$, but I haven't been able to figure out how. Do you know why this can be ...
899 views

### What does the linear assumption over bilinear groups mean?

In the abstract of "Cryptography with Tamperable and Leaky Memory", at the end of the 3rd paragraph, the authors say: In both schemes we rely on the linear assumption over bilinear groups. What ...
2k views

### How to find the order of a generator on an elliptic curve?

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm: Choose random point $P$ on the curve. Find the order of a ...
701 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 ...
161 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 ...
475 views

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 ...
Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\... 3answers 2k views ### Generation of a cyclic group of prime order I am trying to implement a cyclic group generator in Java, but I am running into some issues. In many cryptosystems, the following phrase is expressed during the key generation stage. Let G be ... 1answer 866 views ### How can I find the order of the group that an elliptic curve is defined over? I have a Weierstrass elliptic curve ($y^2=x^3+a \times x+b \mod p $) How can I find the order of the group itself? I have seen Mathematica has a GroupOrder[] ... 3answers 447 views ### How is it decided if$G_1$and$G_2$are two “additive” or “multiplicative” cyclic groups? According to wiki's definition of Bilinear pairing… Let$G_1$and$G_2$be two additive cyclic groups of prime order$q$, and$G_T$another cyclic group of order$q$written multiplicatively. A ... 2answers 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 ... 1answer 172 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 ... 1answer 721 views ### ElGamal and Schnorr groups 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$. ... 1answer 240 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 ... 1answer 144 views ### What type of groups does Microsoft's U-Prove use (Schnorr… etc?) I'm trying to learn more about the Subgroups implementation of Microsoft UProve. I'm unsure if they are Schnorr Groups or use a different foundation? Can anyone point me to the technical reading ... 1answer 701 views ### What is Group in Diffie-Hellman? I understand how Diffie-Hellman key-exchange works. Mainly, two parties agrees in a prime$p$and a generator$g$. Then one party selects its private exponenet$x$, computes its public value$g^x \...
A few days ago, I designed and s-box then derived the following Cayley table of all possible XOR outputs of hex digits in the range of ${2^4}$ and was curious how many such "valid" possible ...