In cryptography, a discrete logarithm is the number of times a generator of a group must be multiplied by itself to produce a known number. By choosing certain groups, the task of finding a discrete logarithm can be made intractable.
6
votes
3answers
464 views
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.
RSA labs makes a similar statement:
The discrete logarithm problem bears the same ...
3
votes
3answers
464 views
What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?
How are the three problems Discrete Logarithm, Computational Diffie-Hellman and Decisional Diffie-Hellman related?
From my understanding, since the Discrete Log (DL) Problem is considered hard, then ...
8
votes
1answer
188 views
Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?
A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using ...
13
votes
3answers
814 views
How robust is discrete logarithm in $GF(2^n)$?
"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime p. However, there exist other finite fields out there, in ...
7
votes
1answer
221 views
Security of pairing-based cryptography over binary fields regarding new attacks
In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$.
Pairing-based cryptography using binary ...
10
votes
2answers
276 views
Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?
I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime.
Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete ...
3
votes
1answer
102 views
Trying to better understand the failure of the Index Calculus for ECDLP
So I'm going to give you guys my understanding and then if you would be so kind as to tell me where I'm off the mark (hopefully I'm not completely wrong).
So basically the index calculus for the ...
3
votes
1answer
71 views
iterated discrete log problem
Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$
For $i=1$ this is the discrete log problem and is assumed to to have ...
4
votes
0answers
83 views
RSA security assumptions - does breaking the DLP also break RSA? [duplicate]
Possible Duplicate:
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, ...
3
votes
1answer
71 views
How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$
Use the notations form the Wikipedia article Paillier Cryptosystem
, assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?
3
votes
1answer
180 views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
3
votes
0answers
127 views
Finding where I am in a linear recurrence relation
Suppose I have a linear recurrence relation
$$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$
where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as ...
2
votes
2answers
115 views
Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset
Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ ...
2
votes
0answers
167 views
Is there a practical zero-knowledge proof for this special discrete log equation?
We have a multiplicative cyclic group $G$ with generators $g$ and $h$, as in El Gamal. Assume $G$ is a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$. There are two parties, Alice and Bob:
Alice knows: ...
2
votes
1answer
224 views
Why are elliptic curve variants of RSA “chiefly of academic interest”?
Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My ...
