# Tag Info

17

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others. For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line ...

8

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor. Not all binary fields are affected equally, however. Both Göloğlu et al and ...

7

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$ $= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] ...

6

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..." Actually, that's not true, and the information theoretically hiding" bullet point does not state that. What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value. ...

6

Here's the deal. The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large). Suppose we are given $y=g^m$, and we want to find $m$. Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say. Then it turns out it is easy to recover $m$, ...

5

Göloğlu, Granger, McGuire, and Zumbrägel broke the DLP in the Galois finite field with $2^n$ elements for $n=6120$, and Antoine Joux did it for $n=6168$, with modest computing power. These recent announcements directly imply that cryptosystems (if any) based on the DLP in a field with $2^n$ elements are no longer secure, including for $n$ big enough that ...

5

Why does finding a collision mean that we have solved the problem? If we find a collision: $\alpha^{i1} \cdot \beta^{j1} = \alpha^{i2} \cdot \beta^{j2}$ then we know that: $\alpha^{i1-i2} = \beta^{j2-j1}$ And so, if we know the order of the group (which we generally do), then we can compute $({i1-i2})^{-1}$, and so, we have: $\alpha = ... 4 Let$\#G$denote the number of elements in the group. In your particular case,$\#G = \varphi{}(n)$(and even$\#G = n-1$if$n$is prime). Let$\xleftarrow{\$}$ denote a uniformly random sampling from a finite set of elements. Furthermore, $\mathbb{Z}_m$ denotes the set of non-negative integers smaller than $m$ and $\stackrel{?}{=}$ denotes a equality test ...

4

For all $m$, if $m$ is a positive integer then $g$ is a primitive root mod $m$ $\;$ if and only if $0\leq g< m$ $\:$ and $\:$ $\operatorname{gcd}(\hspace{.015 in}g,\hspace{-0.01 in}m) = 1$ $\:$ and $\;\;$ for all prime factors $q$ of $\phi$$(m), \: g^{(\phi(m))/q} \not\equiv 1 \;\;\;. 4 Elliptic curves have a number of nice features that make them good for cryptography. One could write a whole book on the topic (as some have), so I'll highlight a few points. The points on an elliptic curve over a finite field forms a group. The same is not true for the ideas you mentioned. Discrete log on many of these EC groups is hard. In fact, there ... 4 While O(n) is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in O(n) but instead in O(\log(n)) = O(|n|) (e.g. expoentiation with square and multiply has |n| multiplications and at most |n| squaring operations). Therefore, the ... 4 There are two ways to solve a discrete log problem over Z^*/p, that is, given g and h, find x with h \equiv g^x \bmod p: If the point g generates a subgroup of size q, use a general Discrete Log algorithm (such as Pollard Rho) to recover x in O( \sqrt{q}) time. Use the Number Field Sieve algorithm to attack the discrete log problem in ... 4 Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of. When someone uses the term "discrete log", they can mean two things: A discrete log in the group Z^*_p; that is, given p, g and g^x \bmod p, recover x A discrete log in some other group; that is, given a group G, a ... 3 The question is not very clear about exactly what you want to prove and what is publicly known, but here's my answer, based on my best guess at what you mean: Each party should publish (R_1,S_1) and (R_2,S_2). They should also publish (R_3,S_3). Now anyone can verify that (R_3,S_3) is a correctly-formed encryption of the sum of the messages ... 3 As noted by Perseids in a comment to this answer, the formula s = r + c + x would allow an adversary (who has completed the protocol once in the role as verifier with P and already got one valid triplet t_1,c_1,s_1) to compute responses to any arbitrary challenge, simply using the formulas t_2 = t_1, s_2 = s1 + c_2 - c_1. Your other alternative s ... 3 In fact, the basic idea of Shor's algorithm for the discrete logarithm problem is reasonably simple. Assume (as in Section 4 Discrete Log: the easy case of Shor's paper) that you have an efficient quantum algorithm for the Fourier transform. Then, applying this Fourier transform twice (once for a and once for b) on a quantum superposition of values ... 3 The complexity of the number field sieve can be obtained from the expected size of the coefficients of the polynomial f(x) = x^d + c_{d-1} x^{d-1} + \ldots + c_0: if c_i \le N^{\epsilon/d}, then the expected runtime is$$ \exp\left(\left(\left(\frac{32(1 + \epsilon)}{9}\right)^{1/3} + o(1)\right) (\log N )^{1/3} (\log \log N)^{2/3}\right),$$or simply ... 3 Concerning question 3, here is an answer assuming that the coefficients of$r$are known to Bob and the coefficients of$s$hidden in an exponential representation. [This is unessential, it can be easily generalized to hidden$r$, but it simplifies the presentation]. To further simplify, let's also assume that$s$contains no constant term. In this setting, ... 3 Antoine Joux announced the computation of discrete logarithm over$\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography. According to Joux, "a direct consequence of this record is that supersingular curves (of genus 1 or 2) defined over GF(2^257) cannot be used securely for pairing-based ... 3 You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups. In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ... 3 Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently. However, the ... 3 If$(G,q)$are public authentic parameters and Alice publishes$(h,R,S)$, then if Alice later publishes$r$, Bob needs to check if$g^r=R$, which fixes$r$. Consequently, when computing$\log_g S/h^r$also fixes$h$and the exponent of$S$is fixed. Changing$m$to$m'$would require to solve$m+rx\equiv m'+r'x \pmod{q}$for$r'$. However, since$r$is fixed ... 3 You are not wrong: given any variety$V$, we can form the Jacobian$J(V)$as an abelian variety, in particular an abelian group over which we could use the Diffie-Hellman problem. However, there are several details that get in the way of doing this. First, it is necessary to compute the order of the Jacobian. We only know how to do this for elliptic curves. ... 2 Finding the corresponding$m'$using$c'$is a chosen cipher text attack. It's possible for a scheme to be semantically secure under certain types of attacks (perhaps something weaker like chosen-plaintext attack), but be broken under heavier attacks (like the chosen ciphertext attack you talk about). 2 There is no known way to compute$(g^a)^k \mod p = g^{ak} \mod p$, given only$g^k \mod p$and$g^a \mod p$as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper. 2 The answer to the final part of the question about index calculus depends on the finite field you are choosing to construct your group$G$. If the characteristic is large enough, the algorithm to use is the number field sieve. In this case, computation of individual logarithms is much faster than the initial computation that leads to logarithm of the ... 2 If a prime$q$is large enough discrete logs and CDH in$\mathbb{Z}_q$are traditional hard problems in cryptography. Your other example$\mathbb{Z}_{2^n}$is typically easy to solve because it can be solved progressively modulo increasing powers of$2$. May be you intended to consider the finite field with$2^n$elements$\mathbb{F}_{2^n}$and not ... 2 Here is a quick summary: First direction, from discrete logs modulo$N$to factoring. Assume that there is a fixed basis$g$for the method that computes logs. Choose a random$x$modulo$2N$and compute$y=g^x\pmod{N}$, then ask for the logarithm of$y$. Let$x'$denotes the answer to the discrete log problem. If$x=x'$restart, else$x'-x$is a multiple ... 2 Question #1: I know of no faster algorithms. Question #2: Minar has answered this one (breaking the scheme). Question #3: Yes, this is easy to break, assuming the polynomials$r,s$are known. We have many$(a_i,b_i)$that satisfy the equation$r(a_i) \equiv s(b_i) \pmod{q_0}$. Let$c_i = r(a_i) - s(b_i)$, where this is evaluated over the integers. ... 2 Actually, there are two known reductions among these three problems: If you can solve discrete logs in$Z^*_n$for composite$n$, you can use that to efficiently factor$n$If you can solve discrete logs in$GF(p^k)$, you can compute discrete logs in an Elliptic Curve over$GF(p)$. That's because there is a known mapping of Elliptic Curves over$GF(p)\$ ...

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