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

Filter by
Sorted by
Tagged with
30 votes
2 answers
14k 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 ...
user110219's user avatar
21 votes
3 answers
9k 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 ...
Ethan Heilman's user avatar
19 votes
2 answers
5k 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 Carmichael ...
user avatar
18 votes
3 answers
3k 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 ...
user avatar
18 votes
0 answers
453 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 ...
fgrieu's user avatar
  • 140k
15 votes
2 answers
8k 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 ...
Emilio Ferrucci's user avatar
14 votes
2 answers
3k 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 ...
dave's user avatar
  • 149
12 votes
2 answers
3k 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 ...
Subhayan's user avatar
  • 428
11 votes
2 answers
6k 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?
MichaelW's user avatar
  • 1,497
11 votes
1 answer
3k 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 ...
Rashmi's user avatar
  • 121
10 votes
1 answer
1k 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 ...
Conrado's user avatar
  • 6,414
10 votes
1 answer
1k views

When using Ristretto or Decaf with Ed25519 and Ed448, do scalars still need pruning/trimming/clamping?

Decaf is a point compression method that builds a prime-order group for (twisted) Edwards curves and Montgomery curves with cofactor $h = 4$ based on the Jacobi quartic [H2015]. The promise is to ...
xorhash's user avatar
  • 231
9 votes
2 answers
4k 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. ...
Bush's user avatar
  • 2,130
9 votes
2 answers
3k 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 ...
Venkatesh's user avatar
  • 472
9 votes
1 answer
1k 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: ...
Mike Ounsworth's user avatar
9 votes
3 answers
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 ...
curious's user avatar
  • 6,150
9 votes
1 answer
6k 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 ...
Venkatesh's user avatar
  • 472
9 votes
1 answer
1k 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}...
fgrieu's user avatar
  • 140k
8 votes
3 answers
9k 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 ...
user1868607's user avatar
  • 1,243
8 votes
1 answer
458 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'...
TrinityTonic's user avatar
8 votes
1 answer
2k 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,...
user32609's user avatar
  • 113
8 votes
0 answers
339 views

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

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 ...
Vitalik Buterin's user avatar
7 votes
3 answers
1k views

How to decide if a point on a elliptic curve belongs to a group generated by a generator $g$?

In the elliptic curve encryption scheme, there is a cyclic group generated by a base point $G$ on the elliptic curve. Given a random point on the elliptic curve, is there a way to decide if the random ...
mactep Cheng's user avatar
7 votes
2 answers
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 ...
Jeff Burdges's user avatar
  • 1,116
7 votes
1 answer
796 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....
JohnGalt's user avatar
  • 546
7 votes
2 answers
193 views

Does pairings based cryptography inherently require a CRS/trusted setup?

In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always ...
bekah's user avatar
  • 365
6 votes
3 answers
2k 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 ...
user avatar
6 votes
2 answers
375 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_(...
TheRookierLearner's user avatar
6 votes
1 answer
2k views

Why is the discrete logarithm problem hard?

Why is the discrete logarithm problem assumed to be hard? Someone else asked the same question but the answers only explain that exponentiation is in $O(\log(n))$ while the fastest known algorithms to ...
LinusK's user avatar
  • 217
6 votes
1 answer
1k 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 ...
mikeazo's user avatar
  • 38.5k
6 votes
1 answer
3k 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 ...
Howard's user avatar
  • 63
6 votes
1 answer
3k views

Why Abstract Algebra in Cryptography?

I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, ...
user93353's user avatar
  • 2,181
6 votes
2 answers
774 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 ...
Ofey's user avatar
  • 81
6 votes
1 answer
1k 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 ...
user4811's user avatar
  • 579
6 votes
2 answers
199 views

Does Poly1305 have weak keys like GCM/GHASH?

Some block cipher keys are weak when used with GCM; see this question. This happens when the multiplier $H$ decided by the key ends up in a small-order subgroup of $\mathbb{F}_{2^{128}}$. Poly1305 ...
Myria's user avatar
  • 2,575
6 votes
1 answer
734 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 ...
Anthony Kraft's user avatar
6 votes
1 answer
2k 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[] ...
samoz's user avatar
  • 3,236
6 votes
1 answer
224 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
user11174700's user avatar
5 votes
2 answers
573 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$ ...
lxgr's user avatar
  • 1,788
5 votes
3 answers
621 views

Non-commutitive and nonassociative algebraic structures in cryptography

Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or ...
dezakin's user avatar
  • 296
5 votes
2 answers
939 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 ...
Vale132's user avatar
  • 153
5 votes
2 answers
432 views

Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
Amirhnr's user avatar
  • 87
5 votes
2 answers
653 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$?
Aria's user avatar
  • 711
5 votes
1 answer
4k 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?) ...
Mariam's user avatar
  • 69
5 votes
3 answers
709 views

When working in a subgroup of EC in EdDSA (especially Ed255190), how is it OK to use operations different from that of the main group?

Ed25519 uses a composite order Elliptic Curve but works in the prime order subgroup of the main group. As per group theory, the subgroups use the group operation. However, as per this, Ed25519 ...
user93353's user avatar
  • 2,181
5 votes
2 answers
299 views

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $p$ be a prime. (say 256 bit) Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such ...
MeV's user avatar
  • 149
5 votes
1 answer
1k 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 ...
satya's user avatar
  • 1,404
5 votes
1 answer
583 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? ...
user4811's user avatar
  • 579
5 votes
1 answer
320 views

Why such a complicated way of cofactor clearing?

I thought I understood cofactor clearing before I read this write-up which generally seems quite popular (lot of other sites link to it) - Cofactor Explained: Clearing Elliptic Curves' dirty little ...
user93353's user avatar
  • 2,181
5 votes
1 answer
1k views

Can there be identical elliptic curve groups of points from different irreducible polynomials in binary extension fields?

Let $E$ be an elliptic curve over a binary extension field $GF(2^m)$, with constructing polynomial $f(z)$ be an irreducible, primitive polynomial over $GF(2)$, and let $G(x_g,y_g)$ be a generator ...
G. Stergiopoulos's user avatar

1
2 3 4 5
7