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

400 questions
Filter by
Sorted by
Tagged with
74 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$, ...
58 views

### please explain how can i solve it? give me a solotion [closed]

To obtain pseudorandom numbers in the simplest stream cipher, a recurrence relation was used Ri = A×Ri-1 + B mod C During the analysis of the system it was possible to determine the values of A, B, C. ...
90 views

96 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 ...
65 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.
52 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 ...
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 ...
78 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$.
78 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)$....
339 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. ...
103 views

### How is the recommended NIST modulus for DLP chosen/calculated?

NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. From this answer it appears that the range of private key numbers is derived by calculating a prime modulus via $2⋅p$ ...
128 views

### Pollard's Kangaroo— What is the failure probability (assuming random functions)?

I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group. He has a Kangaroo Algorithm (page 4) which allows you, if you ...
131 views

### What can be said about the self-power map on groups based on DLP?

Introduction I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...