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

199 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
2k views

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 ... 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 ... 2answers 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 ... 0answers 273 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 ... 1answer 1k 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 ... 1answer 898 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: ... 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. ... 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 ... 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 ... 1answer 346 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}... 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 ... 1answer 778 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 ... 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 ... 1answer 615 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.... 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 ... 1answer 983 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,... 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 ... 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? 1answer 259 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'... 1answer 245 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 ... 1answer 108 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 2answers 508 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$... 2answers 343 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_(... 1answer 923 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 ... 2answers 887 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 ... 2answers 438 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$? 1answer 391 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? ... 1answer 878 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[] ... 1answer 127 views ### Is this an error in the Pinocchio Protocol paper I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ... 1answer 725 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 ... 1answer 270 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 ... 1answer 82 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 ... 1answer 93 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 ... 0answers 92 views ### Variant of Pollard rho using small factors of p - 1 Given an integer$N$to factor which is divisible by some prime$p$, suppose you know (or guess) that$p - 1$has a few small factors, e.g.$3, 2^2, 5$. Define$B$as a product of small prime powers ... 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 ... 2answers 618 views ### Diffie-Hellman insecure on addition modulo$n$Assume that the group$G$is the set$\mathbb{Z}_{n} = \{0,\ldots, n-1\}$for a 1024 bit integer and$+$is addition modulo$n$. Then why would Diffie-Hellman key exchange in this group be insecure? 2answers 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 ... 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 ... 1answer 2k 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?) ... 1answer 324 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 ... 3answers 90 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 ... 1answer 740 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 ... 1answer 658 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 ... 1answer 152 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, ... 2answers 744 views ### How can I find the generator of a composite group and$Z_p*$? I was doing some research on elliptic curves. I know how to find the generator of$Z_p$(this is a prime group). But I came across the term$Z_p*$(group containing elements that relatively prime to$...
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 ...
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}...