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

19
votes
2answers
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 ...
18
votes
3answers
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 ...
17
votes
2answers
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 ...
17
votes
3answers
2k views

What exactly is the impact of the hidden subgroup problem on cryptography?

I understand my group theory (allegedly), so I can make partial sense of The Hidden Subgroup problem: Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow ...
14
votes
2answers
2k views

Why are finite groups used in cryptography?

Most of the cryptographic schemes I know are all based on group theory, e.g. they use finite groups. Can someone explain why is that the case? And why not base the schemes on elements and operations ...
13
votes
2answers
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 ...
11
votes
1answer
989 views

Is every point on an elliptic curve of a prime order group a generator?

If the order of elliptic group is prime then every point is a generator of that group. I tested the above statement on some elliptic curves and found it true. Does that really work on all curves? Is ...
11
votes
0answers
257 views

Finding $x$ such that $g^x\bmod p<p/k$?

In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for ...
9
votes
1answer
821 views

Logjam: “composite order subgroups” explained for TLS developers and system admins?

I have read the recent logjam paper Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. On page 11 in the Recommendations section, they state: ...
9
votes
2answers
1k views

Why are elliptic curves constructed using prime fields and not composite fields?

I come across this: Numbers mod composite number does not form a field rather it forms a ring and every number has a multiplicative inverse under integer mod prime Maybe these are the reasons ...
9
votes
1answer
328 views

How hard is the DLP in that simple group?

Let $p=4q-1$ be a prime with $q$ an odd prime. Let $G=\{0,1,\dots,p-1,\infty\}$. The following law $*$ makes $(G,*)$ a commutative group of order $4q$ with neutral element $\infty$: $$a*b=\begin{cases}...
8
votes
2answers
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. ...
7
votes
1answer
598 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....
7
votes
3answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
680 views

When to use safe prime or Schnorr group

Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that ...
6
votes
3answers
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 ...
6
votes
2answers
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 ...
6
votes
2answers
1k views

in Bilinear pairings, what is the difference between Type 2 and Type 3?

in Bilinear pairings, what is the difference between Type 2 and Type 3? I understand in Type 2, there exists an efficiently computable homomorphic function $\phi : G_2 \rightarrow G_1$ , which is not ...
6
votes
1answer
240 views

Elliptic Curve Cryptography - When to use p and when to use n

Im currently playing around with ECC, in particular the ECDSA scheme on a brainpool P256R1 curve. While implementing the signature verification function, I've stumbled upon a few problems. So far I'...
6
votes
1answer
919 views

Groups for which DDH is easy but CDH is hard

For prime p, is $\mathbb{Z}^{*}_{p}$ a group for which the Decision Diffie-Hellman problem is easy (because one can compute the Legendre symbol of ($g^{ab}$) while CDH is thought to be hard? Of course,...
6
votes
1answer
232 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 ...
6
votes
1answer
85 views

why a group used in cipher based on DLP must be Abelian group?

I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too. thank you very much for read my question
5
votes
2answers
487 views

Why is “multiplying” $g^x$ and $g^y$ not possible?

The computational Diffie-Hellman problem states that for a cyclic group $G$ of order $p$ and a generator $g$, it is hard to find the value $g^{xy}$ given only $g^x$ and $g^y$ (but easy if either $x$ ...
5
votes
2answers
2k views

Why must an elliptic curve group for ECC have prime order?

What is the deeper reason, a group must have prime order for usage in cryptography?
5
votes
1answer
850 views

Must the order of the groups in a bilinear map be the same?

I've been reading up on bilinear maps and their application to cryptography and one thing I keep seeing hasn't yet clicked. If $e:G_1\times G_2\to G_n$ is a bilinear map, $G_1,G_2,G_n$ are always ...
5
votes
2answers
882 views

Why do algebraic proofs apply to cryptography?

How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection ...
5
votes
2answers
391 views

In a group, is it hard to calculate the base $g$ given $g^a$ and $a$?

Discrete logarithm, that is: calculate $a$ given $g$ and $g^a$, is assumed to be a hard problem in some groups. Is it also hard to calculate $g$ given $g^a$ and $a$?
5
votes
1answer
362 views

Why work in a subgroup QR(n) of an RSA group $Z^*_n$?

I sometimes read in papers that a (sub-)group generator $g$ is taken from $\mathrm{QR}(n)$ instead of $\mathbb{Z}^*_n$, where $n = p \cdot q$ and $p$ and $q$ are prime. Is there a reason for this? ...
5
votes
1answer
810 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[] ...
5
votes
1answer
631 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 ...
5
votes
1answer
261 views

Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?

I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer ...
5
votes
1answer
80 views

Cyclic Groups Other than $\mathbb{Z}^*_n$ or Elliptic Curves

I see two types of cyclic groups are most commonly used in cryptography: modulo multiplicative group of integers with prime order elliptic curves Are there any other cyclic groups used in ...
5
votes
1answer
90 views

Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$. Is it possible to determine in polynomial time ...
4
votes
2answers
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_(...
4
votes
1answer
75 views

Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

Please consider we have finite field $\mathbb{F}_p$ for large prime number $p$. We have a fixed field element $\alpha$. By $r_i\leftarrow \mathbb{F}_p$ we mean we pick $r_i$ uniformly random from the ...
4
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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?) ...
4
votes
1answer
298 views

Understanding the Hidden Subgroup Problem specific to Integer Factorization

I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden ...
4
votes
3answers
82 views

What are possible caveats when generating a group for use as parameters for Diffie-Hellman key exchange?

As reusing a widely used group for Diffie-Hellman key exchanges might lead to far easier third-party key discovery through precomputation for that specific group, I would like to know what can ...
4
votes
1answer
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 ...
4
votes
1answer
520 views

Solving the discrete logarithm problem for a weak group

I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always ...
4
votes
1answer
133 views

Using multiple permutations to strengthen the security of a cipher

In one book it says a set of permutations with the composition operation is a group. This implies that using two permutations one after another cannot strengthen the security of a cipher, ...
4
votes
1answer
475 views

Finding a solution to a (sort of) discrete logarithm by asking questions

Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded by $log$ $n$. Let $g$ be a generator of the unique ...
4
votes
1answer
203 views

Hardness of CDH in different groups

What is the difference of the CDH problem in different groups? In particular, given a group $\mathbb{G}_1$ of order $q$ that is a subgroup of $\mathbb{Z}_q^*$, $q$ prime, and another group $\mathbb{G}...
4
votes
1answer
375 views

Do Gap-CDH groups exist?

A Gap-CDH group is such that, given group elements $g, a = g^x, b = g^y$, it is hard to compute $g^{xy}$, but, given a group element $c$, easy to verify if $c = g^{xy}$. While such groups have been ...
4
votes
1answer
164 views

Does Linear Cramer-Shoup have pseudo-random ciphertexts?

"Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ eprint.iacr.org/2007/074.pdf . Are the ciphertexts in Linear Cramer-Shoup computationally indistinguishable from uniform under a chosen-...
4
votes
1answer
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 ...
3
votes
2answers
433 views

Subgroups generators with respect to group generators of composite order

If I have a group $\mathcal{G}$ of order $N=npq$ and subgroups $\mathcal{G_n,G_p,G_q}$ of order $n$, $p$, $g$ respectively and if $g$ is a generator of $\mathcal{G}$ why then $g^{nq}$ is a generator ...