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.

learn more… | top users | synonyms

15
votes
3answers
797 views

What is so special about elliptic curves?

There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used. But what I'd like to know is why these particular curves are so ...
15
votes
3answers
1k 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 ...
13
votes
2answers
403 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 ...
12
votes
1answer
457 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 ...
12
votes
1answer
377 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 ...
8
votes
3answers
348 views

Mapping between subgroups and the integers

This question is a companion to the equivalent question on elliptic curves. Preliminaries Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime ...
8
votes
1answer
171 views

Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$

Suppose, for some security parameter $n$ you choose a prime $p$ such that $p = 2^n+c$ for some relatively small $|c| < 2^m << 2^n$. I have seen such primes being called Pseudo-Mersenne Primes ...
8
votes
0answers
160 views

Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at ...
7
votes
3answers
3k views

What should be the size of a Diffie-Hellman private key?

I'm implementing the SRP-6 protocol, which relies on discrete logarithms for it's security (essentially Diffie-Hellman). The RFC documents state: The private values $a$ and $b$ SHOULD be at least ...
7
votes
3answers
620 views

Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?

In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization ...
7
votes
3answers
1k 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 ...
6
votes
1answer
496 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 ...
6
votes
1answer
176 views

Are there security issues with discrete logarithm keys not being uniformly distributed?

Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both ...
6
votes
1answer
164 views

What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithm

There is a paper from Peter W. Shor from 1994: http://www.csee.wvu.edu/~xinl/library/papers/comp/shor_focs1994.pdf "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", and I have a ...
6
votes
1answer
228 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 ...
5
votes
4answers
1k 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 ...
5
votes
2answers
2k views

How to calculate the time it'll take to crack RSA or DH?

Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
5
votes
2answers
484 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: ...
5
votes
3answers
466 views

Perfect zero knowledge for the Schnorr protocol?

Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?
5
votes
1answer
310 views

What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA

After just reading the post Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use? I was a bit confused. DSA, ElGamal and others are based on ...
5
votes
2answers
247 views

Why would this method of discrete logarithm finding not work?

Say we do know $b$ but not $k$, and are given $g$ such that $g\equiv b^k\pmod p$. And say there exist factors $E = e + m'p$ ($e \equiv b^i \bmod p$) and $F = f + m''p$ ($f \equiv b^j \bmod p$) of $g$. ...
5
votes
1answer
119 views

Is it possible to determine or estimate the period for Blum-Micali PRG?

The Blum-Micali is a cryptographically secure pseudorandom number generator. The construction (from wikipedia): Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$. Let $x_0$ be a ...
5
votes
1answer
303 views

Safe generator for ElGamal signature

What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)? I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ ...
4
votes
3answers
332 views

Discrete log problem, when we have many examples

Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem? Oh, heck, I should be more precise. ...
4
votes
1answer
186 views

Why is the Pedersen commitment computationally binding?

This is how the Pedersen commitment seems to work: Let $p$ and $q$ be large primes such that $q \mid (p-1)$, let $g$ be a generator of the order-$q$ subgroup of $Z_p^{\star}$. Let $a$ be a random ...
4
votes
1answer
170 views

How much do we trust KEA1 Assumption?

Let $$(g,h=g^s,q)$$ be a tuple such that $g$ is a generator for a group $\mathbb{G}$ of ord $q$ and $s$ is uniformly random in $\mathbb{Z}_q$. The KEA1 Assumption saies that for any adversary ...
4
votes
1answer
2k views

How to practically find solutions to a discrete logarithm?

Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit ...
4
votes
1answer
100 views

Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates

My implementation of the parallelized Pollard's Rho algorithm is using Jacobian coordinates to avoid the costly inversion operation when performing point addition. I am wondering if there are any ...
4
votes
1answer
279 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 ...
4
votes
2answers
410 views

How can I solve the discrete logarithm modulo 2q+1 if I can solve it in the subgroup of order q?

As part of my cryptography course I came across an exercise that neither me or my friends could figure out. The problem statement is as follows: Let $p$ be a large prime of the form $p = 2q + 1$ ...
4
votes
1answer
383 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 ...
4
votes
1answer
102 views

Hardness of CDH in different groups

What is the difference of the CDH problem in different groups? In particular, given a group $\mathbb{G}_1$ of order $q$ that is a subgroup of $\mathbb{Z}_q^*$, $q$ prime, and another group ...
4
votes
2answers
330 views

An Elliptic curve cryptography implementation which can be terminated

I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken. One idea would be to use ...
3
votes
3answers
117 views

SRP-6 vulnerabilities when N is small

I'm one of the developers of an application which uses SRP-6 as the authentication mechanism. The authentication part of the code is very old and uses N with only 256 bits (all arithmetic is done in ...
3
votes
1answer
271 views

Why is the discrete log problem easy when the exponent comes from a binomial distribution?

I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial ...
3
votes
2answers
137 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 ...
3
votes
1answer
207 views

Security equivalent to Diffie–Hellman problem?

I've been doing the security proof for one of my Theorem. Basically, given $g^a$, $g^b$, $g^{cb}$, $g$ and $c$ as known values. Is the problem of computing $g^{acb^{-1}}$ equivalent to the Diffie ...
3
votes
2answers
378 views

Why is the discrete logarithm problem assumed to be hard?

This might be a quite stupid question: since a naive brute force algorithm to solve the discrete logarithm problem will only take O(n) time for a group G with order ...
3
votes
2answers
271 views

Decrypting without using the private key

Let $g$ be a generator of a multiplicative group $G$ of order $q$, $x$ be a private key, and $h=g^x$ be a public key of an exponential ElGamal cryptosystem. Given a ciphertext $c$ produced as the ...
3
votes
2answers
208 views

Efficiency of finding sub group order vs factorization

Suppose you got a prime $p = 2\mathbb\Pi_{i=0}^{n-1}q_i+1$, where $2^{k-1} \lt q_i \lt 2^k$ for some $k$ and all $0 \le i \lt n$, and that you also got a generator $g$ of one of the prime order sub ...
3
votes
1answer
106 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
655 views

Why can't I break ElGamal encryption by brute-forcing the secret exponent?

I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system. I am using the terms as defined in Wikipedia. Alice publishes $g$ and $g^x$. ...
3
votes
2answers
138 views

Could this be a valid variation of the Schnorr protocol?

The Schnorr protocol is a 3-steps proof of knowledge of a discrete logarithm, whose interactive version works as follows. Let $p$ and $q$ be two public primes, such that $q \mid (p-1)$, and let $G$ ...
3
votes
2answers
186 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$ ...
3
votes
1answer
207 views

Stream ciphers based on discrete logs

Blum Blum Shub is a stream cipher that is provably reducible to the difficulty of factoring integers. I'm wondering whether there is a similar construction for discrete logs? For example, I could ...
3
votes
2answers
144 views

Finite fields in elliptic curve

I have an elliptic curve defined over finite field where $S_1=aP$ . Is it valid to say that $S_1P$ can also be computed. $P$ is the generator of the group. What my real question is that. Should '$a$' ...
3
votes
1answer
152 views

Chosen ciphertext insecurity in an ElGamal variant

I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but ...
3
votes
1answer
47 views

NIZK Proof of knowledge N of M discrete logarithms (threshold)

It is well known how to produce a NIZK that curvepoints $aG$ and $aP$ have the same discrete logarithm $a$ with respect to the curvepoints they are multiplied by. There is also a way to prove that a ...
3
votes
0answers
38 views

Can anyone explain how the modified r-adding walk works?

I was going through a paper titled “Accelerating Pollard's Rho Algorithm on Finite Fields” by Jung Hee Cheon et al. I understand the table(Ml) creation part of it, but after that I somehow fail to ...
3
votes
0answers
128 views

Do Gap-CDH groups exist?

A Gap-CDH group is such that, given group elements $g, a = g^x, b = g^y$, it is hard to compute $g^{xy}$, but, given a group element $c$, easy to verify if $c = g^{xy}$. While such groups have been ...