We’re rewarding the question askers & reputations are being recalculated! Read more.

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
0
votes
1answer
28 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
0answers
129 views

Factorization or discrete logarithm is difficult for an attacker?

I have read that difficulty in breaking many algorithms are based either on Factorization or discrete logarithm. I am reading about schemes that are similar to RSA which make use of integer ...
13
votes
4answers
8k 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
37 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
47 views

Discrete log problem in $N$ and $Z$

Is the discrete log problem hard in $N$ or $Z$?
0
votes
1answer
35 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
53 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
52 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 ...
1
vote
1answer
35 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 ...
2
votes
1answer
43 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$ ...
3
votes
1answer
111 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 ...
1
vote
1answer
59 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 ...
8
votes
3answers
3k views

What does “export grade” cryptography mean? And how is this related to the Logjam attack?

I am doing some research on the Logjam attack, and I need help in learning some terms that are new for me. What does "export grade" cryptography mean? And how is this related to the Logjam attack?
0
votes
1answer
95 views

Find $F(2x)$ from $F(x) = a^x \bmod p$

Given $F(x) = a^x \bmod p$, where $a$ is a primitive root of $p$, Is it possible to work out what $F(2x)$ or $F(3x)$, etc if you know what $F(x)$ is but not $x$. If you use $F(x)$ then $F(2x)$, etc ...
8
votes
1answer
175 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
83 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
55 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
476 views

Pollard's Rho - Constructing the random function

Suppose we are aiming to solve the discrete logarithm problem $\alpha^x=\beta$ in some cyclic group $G=<\alpha>$. Then we are looking for a (uniformly) random sequence of elements of the form $\...
0
votes
0answers
49 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 ...
2
votes
1answer
88 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
1answer
65 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
36 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 ...
1
vote
2answers
66 views

Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions. Q1. when it refers to "El Gamal signature scheme", The key generation algorithm: it ...
0
votes
1answer
76 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
118 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, ...
1
vote
1answer
82 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 ...
0
votes
2answers
84 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 ...
2
votes
1answer
76 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 ...
24
votes
3answers
970 views

Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?

I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime. Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete ...
13
votes
1answer
366 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 ...
3
votes
1answer
134 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
73 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 ...
0
votes
1answer
73 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(\...
1
vote
1answer
170 views

Proving Sigma Protocol on a Schnorr Protocol Variant

Let p, q be chosen as in Schnorr's protocol, and let $g_1, g_2, h$ be elements in $Z^*_P$ of order q. Assume that the prover P gets as input $w_1,w_2$ where $h = (g_1^{w_1}g_2^{w_2}) \mod q$. ...
8
votes
1answer
1k views

Pollard's kangaroo attack on Elliptic Curve Groups

Let's say I've intercepted some bits of a Diffie-Hellman private key: $x = n \mod r$. I can get the remaining bits by doing a kangaroo search. This algorithm works over $\mathbb{F}_p$. Can it be ...
0
votes
2answers
63 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
1answer
130 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 ...
3
votes
0answers
51 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 ...
7
votes
1answer
320 views

How safe is a prime with $P=2 \cdot Q \cdot R \cdot S \cdot t+1$ for discrete logarithm? How to enhance/compare?

To get some certain properties for my use case I need a prime $P$ which has the form: $P=2\cdot Q \cdot R \cdot S \cdot t+1$ with $Q,R,S,t$ primes as well. Why that form - Use case Together with ...
3
votes
1answer
149 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
74 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
69 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)$....
5
votes
1answer
261 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 ...
10
votes
0answers
264 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. ...
2
votes
1answer
137 views

Testing PRNG quality from ECC public keys?

Having a large set of ECC public keys $P_i = n_iB$ on a fixed curve $E$ over a prime field, is there a way to determine if coefficients $n_i$ were generated using a bad PRNG? In other words, can a ...
1
vote
1answer
96 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$ ...
2
votes
1answer
106 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 ...
6
votes
1answer
101 views

why a group used in cipher based on DLP must be Abelian group?

I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too. thank you very much for read my question
2
votes
1answer
95 views

Bit-strength of discrete logarithm for a group of integers modulo a safe prime

Preliminaries Let $p$ be a safe prime number. Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$. We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ . Let $g \...
3
votes
1answer
179 views

What information does $g^x$ reveal about $x$?

Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with order $q$ - again a large prime. Let $g$ be a generator of $G$. Consider the following standard protocol for ...