Tag Info

Hot answers tagged

18

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


10

$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

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other). If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you ...


5

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


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


5

The bad news is that projective coordinates do not work with Pollard's Rho like you want it to. Rho needs an unambiguous point representation to find meaningful collisions, and in projective coordinates each point can have up to $p-1$ valid distinct representations. The good news is that, sticking to affine coordinates, you can avoid most of the cost of the ...


4

Not at all. It's very trivial: $$(g^{ab})^{b^{-1}}=g^a$$


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

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

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


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

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

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

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$). Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it ...


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 question as currently worded, and considering comments by its author, would boil down to: is it a hard problem finding $g^a\bmod p$, given large prime $p$ large integer $g$ less than $p$ that is a generator of $\mathbb Z_p$ [see note 1] prime $r$ less than $p$ knowledge that unknown $a$ is a positive integer less than $r$ positive integer $b$ less than ...


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

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

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

Are you limited to working with $g$ and $h$ being generators of the entire group $\mathbb{Z}_p^*$? In that case you have a problem with knowledge extraction in the proof of knowledge (basically, since you are not working in a field "in the exponent", but in $\mathbb{Z}_{p-1}$, the required multiplicative inverses might not exist). However, when you work ...


2

Given the definition of a zero-knowledge proof, it must satisfy three properties: Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, ...


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


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

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

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

Should '$a$' be always an integer or can it be a group element itself?? Well, $aP$ is defined to be: $aP \equiv \underbrace{P + P + \ldots + P}_\text{a times}$ From that definition, we see that this makes sense only if $a$ is an integer; it needs to be a count of the number of $P$'s to add together.


2

The published ciphertext is $(R,S) = (g^r,h^r g^m)$. Now Alice publishes $r$. But since Bob can check if $g^r=R$ holds, she cannot cheat at this point. If the public key $h$ is fixed and known, the message can be decrypted: $m=log (S/h^r)$. So concerning your questions: Yes, it's enough if Alice publishes $r$ and she can not cheat. The difference to ...


2

Being new to cryptography is one thing, but you are supposed to do some research on your own before asking questions here (see How to Ask), and D.W. gave you the right directions already. But since you wanted names and links: The first stop should be discrete logarithm on Wikipedia, and it lists several algorithms on this topic. As a beginner, start with ...



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