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

428 questions
Filter by
Sorted by
Tagged with
37 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 ...
71 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 ...
39 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 :...
72 views

### Can zksnark prove DLP?

Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?
29 views

### Canonical lift of Elliptic curve in Smart attack [migrated]

From the answer to why the Smart attack fails for a particular lift, the answer provided along with the journal version of Smart's paper regarding the smart attack seems to suggest that when the ...
23 views

527 views

### Relations between RSA and Generalized Diffie-Hellman (GDH), factoring and GDH

Definition: (The generalized Diffie-Hellman problem) Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$. (1) Is there a known reduction from the GDH problem to ...
320 views

### Given $g,g^t$ in an RSA group modulo $N=pq$, is it hard to compute $g^{t^{-1}}$?

Suppose we have an RSA groug $G=\mathbb{Z}^{*}_{N}$, where $N=pq$ , where $p,q$ are primes. Let $g$ be a random element of $G$ and $t\in \mathbb{Z}^{*}_{N}$. Having $g$ and $g^t$, it seems to be very ...
46 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 ...
489 views

### Zero knowledge proof for a discrete logarithm

Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows: Pick $g$ as a random element from $Z_N^*$ Pick $x$ as a ...
150 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$...
719 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: ...
9k 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 ...
52 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 ...
50 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 ...
139 views

### Primitive root in a finite field

Wen-Her Yang and Shiuh-Pyng Shieh proposed two password authentication schemes by employing smart cards, one is timestamp-based and the other one is nonce-based. Their scheme consists of 3 phases: ...
826 views

### Using Pedersen commitment for a vector

I'm reading Bootle/Groth. I'm trying to understand how they are committing to a vector using Pedersen commitment. Here's my understanding of Pedersen commitment in the context of this paper: We have ...
9k views

### How to test if a number is a primitive root?

How to test if a number is a primitive root, assuming the $\text{mod}\enspace m$ where $m$ is a prime? And if not? Is it not enough if the number is relatively prime to the modulus or prime? I'll ...
20 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 ...
129 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 ...
42 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 ...
466 views

### Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
80 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.
140 views

51 views

158 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 ...
72 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 ...
30 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 ...
2k views

### Security of Schnorr signature versus DSA and DLP

The Schnorr signature scheme is a randomized signature scheme with appendix. The signature is $3t$-bit for conjectured $t$-bit security in a chosen-messages setup, with at most $2^{t/2}$ queries to a ...
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$$ ...
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 ...