22

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. O. L. Atkin). It is based on two core ideas: The number of points is closely linked to a functional equation $$ \varphi^2-t\varphi+q = 0 \qquad\in\...


19

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 one to predict things like memory usage rather well. This also means that the precision / memory you need can't grow arbitrarily / infinitely. You can actually ...


17

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 orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, ...


16

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\equiv b\pmod{c}$ and $0\le a<c$ $a=b^{-1}\bmod c$ means that $a\equiv b^{-1}\pmod c$ and $0\le a<c$ $\varphi$ is the Euler totient function (also noted $\...


15

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 that $g^n\equiv 1\pmod{p}$; this is always a factor of $p-1$. The orders of the subgroups of the group generated by $g$ are the factors of the order of $g$; ...


14

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 components, i.e., it holds that for all $g\in G_1$ and $h\in G_2$ and all $a,b\in Z_p$ (where $p$ is the order of all groups) we have that $e(g^a,h^b)=e(g,h)^{ab}$. ...


14

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 cryptography, consider the simple Caesar cipher, where you replace every letter with the one $n$ positions after it in the alphabet, wrapping around from Z back ...


13

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 have one. But what I don't understand is what is the use of the homomorphism in cryptography? Well, if you have a tuple $(aP',bP',cP')\in G_2^3$ with $P'$ ...


12

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 m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$. However, there are cases for which ...


11

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 (so $A^3 = A\times A \times A = (A \times A) \times A = A \times (A \times A)$ is well defined), but other than that, you really don't need anything. You don't ...


10

The question makes a number of statements that are incorrect. It is not correct that a fixed point is guaranteed to exist. It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist. Moreover, the existence of fixed points has only an extremely tenuous connection to security. Assume $E$ is a ...


10

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 random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about $\alpha$ (other than whether or not it's 0). We can see ...


10

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)^\times$ is exactly the same operation as the $d$th power.) However, the mathematically right modulus for computing $d$ is $\lambda(pq)$: it is precisely the ...


10

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 order subgroup. In (a little) more detail: Elliptic-curve cryptography is mostly based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). That means ...


9

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 due to overhead added by the upper layer, reducing its maximum packet payload compared that of the lower layer). We use limit $p$ or $n$ depending on if we deal ...


8

Basically, every time you choose a group where the required hard problem is not hard, then you will run into a problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography. Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a ...


8

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 $G_1,\ldots,G_n$ and $G_T$ a map: $$e:G_1\times\cdots\times G_n\to G_T$$ that satisfies the linearity property in DrLecter's answer. It's worth nothing here, ...


8

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{GF}(p^n)$, but they are constructed differently. For $n\ge2$, they are commonly called extension fields (as opposed to prime fields for $n=1$), as they can be ...


8

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 out that the group structure on those curves is isomorphic to the multiplicative group of a (quadratic extension of) a field. Therefore the discrete logarithm ...


7

DrLecter gave a good answer, I just wanted to include another well-known example. The Pohlig-Hellman algorithm can be used to compute discrete logs in groups whose order is a smooth integer. If two parties executing a textbook Diffie-Hellman key exchange use as their modulus a prime $p$ such that $p-1$ has only small factors (is 'smooth') an eavesdropping ...


7

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can ...


7

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$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three ...


7

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$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. Then $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence ...


7

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 $x$. In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so: Interpret $x$ as a $k$ bit number, i.e. $x = ...


7

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: Multiplicative notation for arbitrary groups Additive notation for commutative groups This can be found here: math-SE, wolfram Wikipedia also states, that additive ...


7

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 $F_g$, starting from $1$, $p-1$ times, cycles back to $1$. By definition, $g$ is a generator of $\mathbb Z_p^*$ if and only if that cycling does not occur ...


7

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $\ell$ of the group order $n$. In particular, one typically works in a subgroup of order $\ell$ of the curve group, since the additional factors $h$ in a generator's order would not significantly contribute to security. In that, note that $\ell$ ...


7

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, is the general number field sieve, or GNFS for short. The GNFS costs $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ bit operations, where $L = e^{n^{1/...


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