# Tag Info

23

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 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 \... 16 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, ... 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; ... 15 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 ... 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}. ... 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 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 ... 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 dth power.) However, the mathematically right modulus for computing d is \lambda(pq): it is precisely the ... 9 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 cryptosystems should be thought of as non-associative versions of the more well-known non-abelian group based cryptosystems (such as the Anshel-Anshel-Goldfeld and Ko-... 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 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 ...

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

8

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 $p$ is a prime, $p-1$ is composite (as long as $p > 3$). Group theory tells us that there is a subgroup of size $d$ for every $d$ that divides $p-1$.$^{1}$ ...

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

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 $q$, you pick a random value $h$, compute $g = h^{(p-1)/q}$, and if that is not 1, then $g$ is a generator of your group. Obvious questions: How do you find a ...

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

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