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.
432
questions
0
votes
0answers
3 views
Pohlig Hellman and small subgroup attacks
While studying Curve25519 I read about the small subgroup attack in chapter 3. So far i know, that you need a point with a small subgroup to do such an attack. Curve25519 has a basepoint with prime ...
4
votes
1answer
84 views
Sage vs. Magma on DLP
Generally speaking, Magma is faster than Sage on several crypto-related computations, however, I have encountered a DLP instance where Sage is significantly faster than Magma.
Take the DLP over $GF(p)$...
6
votes
0answers
111 views
What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)
Assume that $G$ is any cyclic group where the discrete log problem is hard, such as the elliptic curve group. Let $g$ be some generator of $G$.
The problem is as follows:
Given $(g, g^x)$ for unknown $...
0
votes
1answer
101 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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
77 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
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 :...
0
votes
0answers
24 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}\ ...
4
votes
2answers
80 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?
3
votes
1answer
48 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
34 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 ...
0
votes
3answers
70 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
70 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} \...
1
vote
1answer
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 ...
4
votes
1answer
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$...
3
votes
1answer
726 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:
...
2
votes
1answer
58 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
51 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 ...
1
vote
1answer
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 [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 ...
0
votes
0answers
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
...
3
votes
1answer
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 ...
1
vote
1answer
51 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 ...
0
votes
1answer
85 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
142 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
66 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?
1
vote
1answer
66 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 ...
1
vote
1answer
54 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
94 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
164 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 ...
0
votes
0answers
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 ...
2
votes
1answer
129 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
65 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 ...
2
votes
1answer
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 ...
3
votes
1answer
78 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
53 views
0
votes
1answer
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$?
1
vote
0answers
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?
2
votes
1answer
79 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 ...
2
votes
1answer
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$ ...
1
vote
1answer
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 ...
1
vote
1answer
175 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
...
