# Tag Info

### Why are finite groups used in cryptography?

Can someone explain why is that the case? Cryptosystems based on finite sets have two very nice properties: There is an upper bound to the size of all involved mathematical objects. This also allows ...
• 46.2k
Accepted

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

Well, it doesn't have to. In short, as a consequence of the Pohlig-Hellman algorithm the ECDLP is only as hard as the largest prime order subgroup. So the requirement is that there exist a large prime ...
• 3,499
Accepted

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

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$. Since ...
• 721

### Why are finite groups used in cryptography?

Mostly, I would say that finite groups get used in crypto because they're a good way to describe things that naturally appear in many crypto schemes. For example, going way back to the early days of ...
• 46.2k
Accepted

### Why is the discrete logarithm problem hard?

Now, I wonder if there are any better arguments. Ultimately, no, not really. We don't have any proof that computing discrete logs is hard. For that matter, we don't have any proof that any problem ...
• 149k
Accepted

### 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. Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (...
• 149k
Accepted

• 46.2k
Accepted

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

The answer really depends on the Cryptographic Elliptic Curves that we know! Prime order Cryptographic EC: Since the order of the subgroup generated by an element must divide the order, then there is ...
• 49.1k

### Non-commutitive and nonassociative algebraic structures in cryptography

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity $x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these ...
• 1,235
Accepted

• 149k

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

To complete the other answer, one can note that elliptic curves over the $\mathbb{Z}/n\mathbb{Z}$ ring for non-prime $n$ are at the heart of Lenstra elliptic curve factorization, so such elliptic ...
Accepted

### Groups for which DDH is easy but CDH is hard

Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?) Yes, if $g$ is an element with ...
• 149k

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

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, ...
• 48.8k
Accepted

### Discrete logarithm weak group

Is there any better algorithm ? Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You ...
• 149k
Accepted

### Why do algebraic proofs apply to cryptography?

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results. Given the terminology in your question, ...

### VDF / RSA groups

The RSA group for modulus $N$ of secret factorization simply is the multiplicative group of integers modulo $N$, often noted $\mathbb Z_N^*$. That can be viewed or defined as the subset of integers $m$...
• 143k
Accepted

### Is ElGamal homomorphic encryption using additive groups works only for Discrete Log ElGamal? What about EC ElGamal?

The Discrete Log ElGamal forms multiplicative group, which is not suitable for homomorphic encryption with additive group. There is no inherent difference between 'multiplicative' groups versus '...
• 149k