# Questions tagged [discrete-logarithm]

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.

429 questions
Filter by
Sorted by
Tagged with
78 views

### Why discrete logarithm modulo composite moduli not popular and not defined in standards?

The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$. The demerit of this approach seems ...
46 views

### Pohlig-Hellman on ECDLP over extension field $\mathbb{F_p}^6$

Suppose there is an elliptic curve $E$ in form $y^2=x^3+b$ defined over $\mathbb{F_p}$, where $p$ is large prime. #$E(\mathbb{F_p})$ is also a large prime but #$E(\mathbb{F_p})\ne p$. ECDLP on this ...
39 views

### Which groups are secure for DL-Problem?

I was wondering why some groups provide more security to cryptosystems relying on DL-Problem. It is not clear to me whether it is just due to the known attacks or if there are some other reasons. So ...
76 views

### Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?

The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group ...
41 views

### Computing discrete logarithms in the subgroup generated by 1 + N

When I read about DLP, I found that there are groups where the computation is easy. I found that it is known that computing discrete logarithms in the subgroup generated by 1 + N is easy. For example :...
24 views

52 views

### MOV attack when $E(\mathbb{F}_q)$ is cyclic

Suppose $P\in E(\mathbb{F}_q)$ and $R=dP$. In the MOV attack, we compute $\alpha=e(P,T)$ and $\beta=e(R,T)$ and try to solve the discrete logarithm problem for $\alpha$ and $\beta$ in the finite ...
157 views

### Find prime $p$ such that $a^x\equiv b\pmod p$ for many $x\in[1,p)$

Given haphazard large integers $a$ and $b$ (like few thousand bits), can we efficiently find (and how) some integer triplet $(p,x,k)$ with $p$ a large prime (like a thousand bits) $a^x\equiv b\pmod p$...
724 views

### Small exponents and the RSA problem

I need some help with the following statement from the book A Graduate Course in Applied Cryptography* - Dan Boneh and Victor Shoup, in 8.10.1 The key derivation problem, page 320 of v0.5: ...
57 views

### Excluding specific factors for Pohlig-Hellman

I want to use Pohlig-Hellman and BSGS to solve the discrete log of an Elliptic Curve which has a composite order generator. The ...
51 views

I'm following this description of the MOV attack: https://people.cs.nctu.edu.tw/~rjchen/ECC2009/19_MOVattack.pdf (slide 6/8) by implementing it. However, sometimes the computed dlog $k$ (which is ...
42 views

### Knowledge of discrete log is needed in the proof of Cramer-Shoup public key scheme?

In the proof of the Cramer-Shoup public key scheme , I understand that the adversary's view can be seen as equations such as $\log c = x_1 + w x_2, \log d = y_1 + w y_2$ and so on (equation 1 and 2 ...
21 views

### How to construct Undeniable Signature behind and its alternative response and verification

When I am working on Undeniable Signature, I am thinking what is the purpose and how to construct each step. Here is the details of Undeniable Signature For signature $z=m^x$ and $m$ is the message ...
130 views

### Variant of Schnorr Protocol (Difference pair of response and verification)

When I am trying to learn deeper to Schnorr Protocol. I found that for deference there is more than one response and verify pair. But I am not sure am I right. We will use Schnorr Protocol to prove ...
50 views

### Small complex multiplication field discriminant for solving ECDLP

I've seen from the SafeCurve criteria that one should try to avoid small complex multiplication field discriminant as it can speedup the discret log computation via the Polard Rho method. However, I ...
84 views

### How to reduce Computational Diffie–Hellman problem and Decisional Diffie–Hellman problem to Discrete logarithm problem

I'm supposed make some reductions but don't even know where to start. Any help would or explanation on how to do this would be much appreciated.
141 views

51 views

161 views

### Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y?

My understanding is that $a^b \bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $\log_y x \bmod p$. For instance, if we are trying to compute ...
31 views

### If they exist a relation between decisional Diffie-Hellman assumption and composite decisional residuosity assumption

From the cryptographic hardness assumptions, we have DDH and CDR assumptions. It is known that the composite decisional residuosity assumption is related to a factoring problem, while the DDH is ...
127 views

### Index Calculus for Discrete Logarithm

I'm studying the Index Calculus method for Discrete Logarithm. In the book "Introduction to Cryptography with Coding Theory" by Trappe it's told that, if $$\alpha^k\equiv \prod p_i^{a^i} \mod p$$ ...
64 views

### Why does using a prime-order subgroup in DLP improve security?

Let's consider a discrete logarithm $\beta \equiv \alpha ^{x} \bmod \,\, p$ We can solve it using Pohlig-Hellman algorithm. And, if $p-1 = tq$ where $q$ is a large prime factor, we can avoid any ...
109 views

### Weakness in Pohlig-Hellman algorithm

Let's try to solve a discrete logarithm: $\beta \equiv \alpha ^{x} \bmod \,\, p$ using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that ...
76 views

### Identity Based Encryption: Known Random Value

Let's consider a situation whereby: Alice generates a ciphertext c from a message m using Bob’s ID. An attacker Carol can get c from the open channel. She knows that c is generated by using ...
52 views

### Discrete log problem in $N$ and $Z$

Is the discrete log problem hard in $N$ or $Z$?
37 views

### For discrete elliptic curves, can you find G, if you are given b and B?

I know you cannot find $b$ if you are given $B$ and $G$, where $B = [b]G$, but can you find $G$ given $b$ and $B$?
65 views

### Elliptic curve discrete logarithm problem

I'd like to know what is the maximum bits of the finite field that we can solve the ECDLP in a "regular" computer in trivial time. Is there any recent data about this?
77 views

### How does the order of Q affect the time it takes to solve ECDLP?

I use Sagemath's built-in function discrete_log() to solve ECDLP and according to the documentation it uses Pohling-Hellman algorithm to solve an ECDLP. This is ...
50 views

### Does the discrete log assumption hold if k > p

In discrete log cryptosystems like ElGamal it is noted that the "private key" $k$ should be chosen as any element of the group $G$ i.e. $k < p-1$. Does the integrity of the cryptosystem rely on $k$ ...
50 views

### Retrieving correct ciphertext from additive ElGamal

I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$. From what I've read, the ...
174 views

### How do I interpret the CADO-NFS output for discrete logarithm calculation in GF(p)?

I'm using CADO-NFS to calculate discrete logarithm in a finite field GF(p). The problem is when I type ...
121 views

### Attacking any one in many public keys

The problem of finding private key from public key is typically studied in the one-key setup: what's the expected cost of breaking one key (e.g. by factoring a public modulus, or solving a discrete ...
I understand that the discrete log problem is defined as $G^y \bmod p = x$ Speaking generally, $G$ here is a generator for the group zp*, where $G$ is able to ...
### Pollard's Kangaroo: How random does $f$ have to be?
I'm implementing Pollard's kangaroo algorithm as described here. Wikipedia's description of the protocol says that you should have "a pseudorandom map $f:G\rightarrow S$." Does anyone know what ...