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.
411
questions
1
vote
1answer
29 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
61 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
132 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
62 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
44 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
28 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
55 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
23 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
48 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
103 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
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
67 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
20 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
92 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
96 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 $...
1
vote
1answer
137 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
27 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
106 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
53 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
90 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
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
51 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
59 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
64 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
46 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
42 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
131 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
...
3
votes
1answer
118 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 ...
0
votes
1answer
98 views
Group in the context of elliptic curve crypto [duplicate]
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 ...
0
votes
0answers
88 views
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 ...
0
votes
0answers
57 views
DLP instances for given number of congruences
Let $S$ be the set of $k$ congruences of the type $g_{i}^{x_i} \equiv h_i \pmod{n_i}, \quad \forall i,1\leq i \leq k$
What would be the best way to describe such set $S$ with a term in literature. ...
0
votes
1answer
66 views
structure in modular arithmetic
I was playing around with modular arithmetic when I noticed something.
\begin{align}
g^k &= a \bmod n\\
g^{k+0.5(n-1)} &= b \bmod n
\end{align}
Then $a + b = n$, so you can also write
$$g^{...
1
vote
1answer
42 views
Questions regarding random values in Schnorr authentication
In Chapter 21.3 of Schneier, Applied Cryptography I read the following about the Schnorr Authentication Protocol:
To generate a key pair, first choose two primes, $p$ and $q$, such that $q$ is a ...
8
votes
1answer
208 views
Simultaneous Discrete Logarithm with Small Exponent
Given two distinct safe primes $p_1 = 2 \cdot q_1 + 1$, $p_2 = 2 \cdot q_2 +1$, consider the following two instances of the discrete logarithm problem with the same unknown exponent $x$.
$$ g_1^x \...
0
votes
1answer
123 views
Proof Dlog is hard in generic group model
I want to know a proof for why the dlog problem is hard in the generic group model. But i can't find any resources online. Can someone please provide me a link or an explanation?
1
vote
1answer
97 views
Discrete logarithm problem particularly hard for Schnorr groups?
The Wikipedia article on Discrete Logarithm just states without source:
In some cases (e.g. large prime order subgroups of groups ($\mathbb{Z}_p)^×$) there is not only no efficient algorithm known ...
1
vote
1answer
172 views
Finding tetration in a multiplicative group modulo p
I have a variant on the discrete logarithm problem, involving finding tetration in a multiplicative cyclic group of integers modulo a large prime $p$:
$$a = x^x \mod p$$
Where $a$ and $p$ are known, ...
0
votes
2answers
126 views
Why are some group representations much easier to compute discrete logarithm for? [duplicate]
The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative ...
3
votes
1answer
141 views
Does knowing that the exponent is in a certain range help solving discrete log?
given:
$c=g^i \bmod P$
$g$ generator for group with group size $\varphi(P)$
$g,P,\varphi(P)$,c is known by the attacker
He wants to know $i$.
Now the attacker also knows $j,k$ with $j<i<k$
$k-j$...
-1
votes
1answer
105 views
How do discrete logarithm with modulo a prime and a non-prime compare?
Let
$c_N = g^i \mod N$ and $N=p \cdot q$
and
$c_P = f^j \mod P$ and $P$ a prime
We assume $N,P$ has the same bit-length. $P$ is the best type of prime you can choose (e.g. safe prime). $N$ is a ...
2
votes
1answer
125 views
Elliptic Curve Discrete Log in a Composite Ring
Elliptic curves are usually defined over prime rings (fields), but what if we chose a ring of composite order? Let $n = pq$ for $p,q$ large primes. Say I have elliptic curve $y^2 = x^3 + ax + b$ over ...
0
votes
1answer
85 views
Elliptic curve with prime subgroup equal to field size
I am aware that when the equation $\#E(\mathbb{Z}_p) = p$ holds for prime $p$, the elliptic curve is called "anomalous" and is insecure do to "Smart's attack".
Consider the similar case that $E(\...
2
votes
1answer
102 views
Understanding the Definition of Most Significant Bits in the Hidden Number Problem
Boneh's and Venkatesan's "Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes" defines the Hidden Number Problem (HNP). The HNP shows that computing ...
0
votes
2answers
71 views
Bulletproof - Is it possible to do range proof only from public key?
is it possible to proof x in range (2^1,2^64) from xG=Q with bulletproof or something else only from Q? I’m new in this subject, so thanks before.
3
votes
0answers
55 views
Subexponential algorithms that apply only one of factoring and discrete logarithm?
Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...
3
votes
1answer
151 views
Why is the NIST recommendation for the private key exponent so much smaller than the modulus?
NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. This question answered how the modulus was chosen/calculated, however, why isn't the private key size closer to the ...
0
votes
2answers
97 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
0answers
101 views
How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?
Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element?
In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....
11
votes
0answers
369 views
How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?
There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time.
...
