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.

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 :...
4
votes
2answers
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?
1
vote
0answers
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 ...
0
votes
0answers
23 views

When will the random bit sequence start to repeat in pseudo random number generator

Let's say we have the Blum-Micali pseudorandom number generator. from wikipedia: Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$. Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ ...
1
vote
1answer
40 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 [1], 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 ...
3
votes
1answer
47 views

Mapping a value $g^x \bmod p$ to a small interval $[1…H]$

My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$. Let's ...
0
votes
1answer
31 views

implications of shor's algorithm on $F_{2^m}$ elliptic curves and GHASH

The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security ...
5
votes
2answers
368 views

Discrete Logarithm problem with inverse

Let $\mathbb G$ be a cyclic group of order $q$. The Discrete Logarithm Problem (DLP) is, given $g, g^x \in \mathbb G$, to compute $x \in \mathbb Z_q $. I'm interested to know if there is a known ...
0
votes
3answers
67 views

What is the discrete logarithm assumption and why it is not easy with Shank's baby-step/giant-step

When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time. But I also read that there are several algorithms in $\mathcal{O}(\sqrt{n})$...
4
votes
0answers
68 views

Inverse Public Key Proof

Alice has a private key, $x$, and a public key $P = [x] \cdot G$ in a group of order $n$. Alice would like to also publish her inverse public key (inverted modulo the group order) $P_{inv} = [x^{-1} \...
5
votes
1answer
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
6
votes
2answers
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 ...
4
votes
1answer
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$...
3
votes
1answer
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: ...
15
votes
4answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
50 views

MOV attack on ellipic curves with the correct dlog in the finite field, but wrong dlog in the EC group

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 ...
3
votes
1answer
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: ...
3
votes
2answers
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 ...
7
votes
2answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
13
votes
1answer
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 ...
0
votes
1answer
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.
1
vote
1answer
140 views

The dth root unity in the Pollard Rho Algorithm

In the original paper of Pollard's Monte Carlo Methods for Index Computation (mod p): When the epact is reached, i.e. $$x_i = x_{2i}.$$ then the following equation is formed $$q^m \equiv r^n \pmod p,...
1
vote
2answers
65 views

Standards for finite-field discrete log cryptography

The NIST and TLS standards for Diffie-Hellman key exchange over a finite field all work in a subgroup of ${\mathbb Z}_p^*$ having prime order $q$, where $p = 2q+1$. On the other hand, DSA has a larger ...
0
votes
2answers
45 views

Better understanding what big O is referring to

I thought I understood big-O notation relatively well, but now I'm not sure. In particular, I've seen several posts like this discussing how the discrete logarithm problem is (probably) hard since our ...
0
votes
0answers
31 views

How to Solve Discret Log Computation Problem

Given $g^a$ in $Z_p$, it is hard to get the solution $a$. Everyone says yes, I wonder why it is hard. Could anyone give a specific mathematical way to show it is indeed hard?
2
votes
1answer
102 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 ...
1
vote
1answer
65 views

Decisional Discrete Logarithm problem?

Has the decisional version of the discrete logarithm problem been studied somewhere? I mean, for known $G$ in a group, distinguishing $xG$ and $Y$ for unknown integer $x$ and group element $Y$?
0
votes
1answer
25 views

Rounding down in the exponent of group element

I have been struggling to find the algorithm $\mathcal{A}$ in the following. Let $(G,g,q)$ be the group parameter, $p << q$, $x\in \mathbb{Z}_q$, can we build the following algorithm: $$\...
0
votes
1answer
51 views

Discrete log problem exponential runtime

I am trying to understand the runtime complexity of the discrete log problem (in the most basic sense). So, if we have $\langle g \rangle = G$ and are trying to find $g^x = a, a \in G, 0 < x < ...
0
votes
1answer
105 views

Factorization problem

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$? Note that, either $a$ or $b$ can be reused to ...
0
votes
2answers
103 views

Verify the discrete log of ECDSA is in range

Is it possible to verify the discrete log in elliptic curve is within range without uncovering it? I need to verify that $x$ is within $1$, $2^{64}$ for $xG=P$.
1
vote
1answer
53 views

How to find a small generator with small inverse? Does it have negative impact to security? (for Schnorr subgroup of $\mathbb{Z}/P\mathbb{Z}$)

Given a prime $P$ with $$P= r \cdot q+1$$ with $q$ prime as well. I'm looking for a generator $g$ of the Schnorr subgroup with order $q$ which is small by value and has a inverse (to $\bmod P$) which ...
1
vote
1answer
78 views

Double discrete logarithm on elliptic curve

Background: I am attempting to implement the paper Publicly Verifiable Secret Sharing. I managed to get it working using modular groups, but when I want to make it more efficient by transferring to ...
0
votes
0answers
22 views

Lifting point to quadratic twisted curve

How to lift point to it’s quadratic twisted curve? I use secp256k1. Is the diiscrete log still same? Thanks before
1
vote
1answer
93 views

Given generator $g$ with prime order $k$ in $\bmod P$. Does increasing $P = 2 \cdot c \cdot k +1$ decrease security? Increasing $g$ increase security?

An adversary wants to find $a$ in $$m \equiv g^a \bmod P$$ He knows prime $P = 2 \cdot c \cdot k +1$ with it's primes $c,k$, value $m$ and $g$. And he also knows that $g$ only has an order of $k$, ...
3
votes
1answer
103 views

Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$?

Let $P$ be a prime and $g$ a value between $2$ and $P$. Let $M$ be the set of numbers which can be generated with $g$: $$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$ If $g$ is a prime root of $...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
17
votes
2answers
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 ...
2
votes
1answer
122 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$$ ...
0
votes
1answer
60 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 ...

1
2 3 4 5
9