26 votes
Accepted

How to determine the order of an elliptic curve group from its parameters?

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A....
user avatar
  • 11.1k
19 votes

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 ...
user avatar
  • 44.6k
17 votes
Accepted

lcm versus phi in RSA

I'll use these common definitions and notations: $a\equiv b\pmod c$ means that $c>0$ and $c$ divides $b-a$ $a\equiv b^{-1}\pmod{c}$ means that $a\cdot b\equiv 1\pmod{c}$ $a=b\bmod c$ means that $a\...
user avatar
  • 124k
16 votes
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 ...
user avatar
  • 721
15 votes
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 ...
user avatar
15 votes

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 ...
user avatar
15 votes
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 ...
user avatar
  • 132k
14 votes
Accepted

What are Cryptographic Multi-linear Maps?

Ok, I will start with a cryptographic bilinear map. Cryptographic Bilinear Map A cryptographic bilinear map $e: G_1\times G_2 \rightarrow G_T$ as the name says is a map that is linear in both ...
user avatar
  • 12.1k
14 votes
Accepted

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

Note that you do not have an efficiently computable homomorphism from $G_1$ to $G_2$, but in Type-2 you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$ and in Type-3 you do not ...
user avatar
  • 12.1k
14 votes
Accepted

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

A safe prime is a prime number $p$ for which $(p-1)/2$ is also prime. The order of an element $g$ of the group $\mathbf{Z}^*_p$ (the integers modulo $p$, excluding 0) is the smallest integer $n$ such ...
user avatar
  • 3,547
12 votes

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

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod ...
user avatar
  • 11.1k
11 votes
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 (...
user avatar
  • 132k
10 votes
Accepted

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

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$? Answer: assuming that the $r_i$ values are ...
user avatar
  • 132k
10 votes

lcm versus phi in RSA

The security of $\varphi$ and $\lambda$ should be equivalent since they are mathematically equivalent in the context in which they are used. (That is: the $d´$th power in $(\mathbb Z/pq \mathbb Z)^\...
user avatar
  • 11.1k
9 votes

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 ...
user avatar
9 votes
Accepted

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

A possible analogy is two layers in a communication protocol, with $p$ and $n$ the maximum packet payload for the lower and upper layer. They need not be equal (in communication protocols, typically ...
user avatar
  • 124k
8 votes

What are Cryptographic Multi-linear Maps?

I'll add something to the previous answer. The first way to construct multilinear maps is pretty recent and was introduced by Sanjam Garg, Craig Gentry and Shai Halevi. What we want is given groups $...
user avatar
8 votes
Accepted

Generation of a cyclic group of prime order

One way to do this, if you're working with a multiplicative group $Z^*_p$, is to pick a prime $p$ so that $p-1$ has a large prime factor $q$; once you have this, then to generate a generator of order $...
user avatar
  • 132k
8 votes

Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction. Let $A$ be an adversary that given $g^a$ ...
user avatar
8 votes

How to determine the order of an elliptic curve group from its parameters?

As yyyyyyy mentioned for counting number of points on elliptic curve over $\mathbb F_p$ we can use Elkies method. But for extension of fields use of this theorem make it so easy: Theorem : Let $E$ ...
user avatar
8 votes
Accepted

Find the generators of multiplicative group of units efficiently?

For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating $...
user avatar
  • 124k
8 votes
Accepted

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

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{...
user avatar
8 votes

why are non singular curves used in elliptic curve cryptography?

Not-so-useful answer: An elliptic curve is by definition a non-singular curve. Therefore by definition we use non-singular curves in elliptic-curve cryptography. Why not use singular curves? It turns ...
user avatar
8 votes
Accepted

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

The group you're working with does not have order $p$. In discrete log schemes, you're not working in a finite field, $F_p$, but rather a multiplicative group $1,...,p-1$, which has order $p-1$. Since ...
user avatar
  • 1,336
8 votes
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 ...
user avatar
  • 43.4k
7 votes
Accepted

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

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$. Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $...
user avatar
  • 4,335
7 votes
Accepted

How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups?

Notation is basically a free choice of the author, as they describe functionally the same. And there is no fixed definition for this. However, common practice in mathematical publications is: ...
user avatar
  • 12.3k
7 votes
Accepted

What is a cyclic group of prime order q such that the DLP is hard?

Cyclic group of prime order q such that the DLP is hard A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) ...
user avatar
  • 124k
7 votes
Accepted

How to construct a hash function into a cyclic group such that its discrete log is intractable?

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(...
user avatar
  • 132k

Only top scored, non community-wiki answers of a minimum length are eligible