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
1 answer
47 views

Does a list of discrete log equations reveal information?

Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that ...
user avatar
  • 21
0 votes
0 answers
23 views

The appropriate smoothness bound

My question roots from another question asked in the community since I do not have enough reputation points to comment on the answer, I was hoping I could ask it here. How was the individual asking ...
user avatar
1 vote
1 answer
46 views

Secure modification of DSA?

In DSA, we compute the signature $(r,s)$ on $m$ by sampling $k\in\{1,...,q-1\}$ and then computing $r := g^k \bmod p$ $s := k^{-1}*(m+x*r) \bmod q$ During verification, we compute $v:=g^{m*s^{-1}}*y^{...
user avatar
  • 439
2 votes
1 answer
85 views

Is there a discrete log challenge?

RSA challenge is well-known and it has a wiki page. Is there a discrete log for $\mathbb F_p$ where $p$ is Sophie-Germain prime?
user avatar
4 votes
1 answer
125 views

If a curve $E/\mathbb{F}_q$ is secure, what can be said about $E/\mathbb{F}_{q^2}$

Let $E$ be a known, "secure" curve, defined over a field $\mathbb{F}_q$ where $q$ is either a prime $\geq 5$ or a power of $2$. Denote by $n$ the amount of rational points of $E$. Consider $...
user avatar
2 votes
1 answer
293 views

Security of equal discrete logs (over different bases)

I am trying to find a reduction for the following DLOG problem in generic groups. It is a simple generalization but I'm not finding any reference (the closest being the Chaum-Pedersen signature scheme ...
user avatar
0 votes
0 answers
39 views

Consider the DSA digital signature scheme. Does the intercepted message m||s||r contain all information about the signer’s private key?

Consider the DSA digital signature scheme. Does the intercepted message m||s||r contain all information about the signer’s private key? Please justify your answer carefully. Please note that the ...
user avatar
  • 1
0 votes
0 answers
81 views

How to use the CADO-NFS to calculate DLP in GF(p^2)?

I have question regarding DLP in GF(p^m) I know we can use CADO-NFS to solve the DLP in GF(p). But what if we move into the GF(p^m) and are working with polynomials? Does the Cado tools can calculate ...
user avatar
0 votes
1 answer
53 views

If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances

I am trying to prove the following: Given an ensemble $\{p_n, g_n\}$ ($p_n$ is an $n$-bit prime and $g_n \in \mathbb{Z}^*_{p_n}$ is a generator), if $A$ is a deterministic polynomial time algorithm ...
user avatar
  • 189
0 votes
0 answers
47 views

Schnorr signature | Schnorr Public Parameters

hello guys hope you are doing well :), i am trying to simulate the Schnorr Signature, but i have encountered some difficulties finding the generator, i have chosen a prime P of 1024bit and took a ...
user avatar
0 votes
0 answers
52 views

Discrete Logarithm Based algorithm

The private (secret) key in DL (discrete logarithm) based algorithms is uniformly selected from the group Zq*. This private key is then used to compute the public key. Could the opposite be done, for ...
user avatar
  • 15
2 votes
0 answers
62 views

Historical key sizes for RSA and discrete log [closed]

What is the historical pattern for key size increases for rsa vs discrete log? What are the current and future projected sizes for these?
user avatar
  • 882
2 votes
1 answer
59 views

Is the discrete log in general hard in Paillier groups?

https://en.wikipedia.org/wiki/Paillier_cryptosystem Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily. If I were to select $g \in \mathbb{Z}_{n^2}^*$ ...
user avatar
3 votes
1 answer
101 views

ElGamal discrete logarithm method to send keys

In my criptography course I was given the following exercise: ElGamal proposed the following digital signature scheme using discrete logarithms over a field $\mathbb{F}_p$, where $p$ is a large prime. ...
user avatar
  • 133
0 votes
0 answers
71 views

Algorithm for computing discrete logarithm in group of order $2^n$

In my cryptography course our teacher said that solving the discrete logarithm problem in a group of order $2^e$ is easy, and he gave us the following algorithm: Let $G$ be a cyclic group with $|G|=2^...
user avatar
  • 133
3 votes
0 answers
37 views

Polynomial Breakdown in proof of lower bounds on Discrete Log in the Generic Group

In Shoup's proof of the hardness of discrete log in the generic group in this paper, he mentions that: At any step in the game, the algorithm has computed a list $F_1,\dots,F_k$ of linear polynomials ...
user avatar
6 votes
1 answer
1k views

Why is the discrete logarithm problem hard?

Why is the discrete logarithm problem assumed to be hard? Someone else asked the same question but the answers only explain that exponentiation is in $O(\log(n))$ while the fastest known algorithms to ...
user avatar
  • 217
1 vote
1 answer
47 views

Division by $2$ or principal root with DH oracle

Assume $g$ is generator of multiplicative group modulo prime $p=2q+1$ where $q$ is prime. Assume we know $g^{2t}\bmod p$ and $g^{2}\bmod p$ and assume we can have access to a Diffie-Hellman oracle. ...
user avatar
  • 882
0 votes
1 answer
84 views

Chaum–Pedersen Protocol explanation for dummies. What I'm doing wrong?

The screenshot from a book with Chaum–Pedersen Protocol description is below. I'm trying to implement it for my own. And I don't get math here. My assumptions: Discrete Logarythm functions: The dot ...
user avatar
1 vote
1 answer
67 views

Does generic group black box model prohibit MSB of discrete logarithm?

Black box generic models prohibit calculation of discrete logarithm in groups of order $q=2p+1$ where $p,q$ are random primes to $\Omega(\sqrt{p})$ steps (refer Discrete Logarithm in the generic group ...
user avatar
  • 882
1 vote
1 answer
53 views

Embedding degree of curves of characteristic 2 and ECDLP transfer

It is known that we can transfer an ECDLP instance on a curve $E$ defined over $\mathbb{F}_p$ for prime $p$, to a discrete-log instance in $\mathbb{F}_{p^k}$ for some $k$. It is referred to as the ...
user avatar
2 votes
1 answer
179 views

Distribution of group elements with chosen bits and hardness of discrete log problem

For generator $g$ of order $n$ the group elements $y=g^x$mod $n$ are uniformly distributed because of the modulo operation. Suppose however that from the original output space $Y$, we only consider ...
user avatar
  • 164
1 vote
0 answers
55 views

Detailed Proof of Knowledge for Discrete Log

I'm having difficulty finding a detailed proof for one of the most basic protocols in cryptography, that is the Schnorr protocol, or the sigma protocol for proving knowledge of a discrete log. Most ...
user avatar
1 vote
0 answers
60 views

Recovering alternate solutions to a discrete logarithm that can be attacked using Pohlig-Hellman

In the process of studying discrete logarithms and approaches that could be taken, I saw the Pohlig-Hellman algorithm. Later when I was working with $h = g^x \mod p$ where $p-1$ is smooth, using ...
user avatar
2 votes
1 answer
74 views

Are there applications which cannot be done with only factoring trapdoor?

Suppose we only have to use factoring as trapdoor function and we are disallowed to use other trapdoors, are there applications currently deployed which cannot be done?
user avatar
  • 882
3 votes
2 answers
167 views

Common exponent problem related to discrete logarithms assuming Diffie Hellman oracle

Let $g$ be a generator of multiplicative group mod $p$ a prime. Suppose we know $$g^{a+km_1}\bmod p$$ $$g^{b-km_2}\bmod p$$ $$g^{a+k'm_3}\bmod p$$ $$g^{b-k'm_4}\bmod p$$ where $m_2m_3-m_4m_1=\phi(p)$ ...
user avatar
  • 882
2 votes
1 answer
76 views

Any way to find $g,P$ for max cycle size in Blum–Micali with $x_{i+1} = g^{x_i} \mod P $ and $x_0 = g$?

For some $g$ and prime $P$ the sequence $$x_{i+1} = g^{x_i} \mod P $$ $$ x_0 = g$$ can contain all numbers from $1$ to $P-1$ and with this it is a pseudo-random permutation of those numbers (EDIT: ...
user avatar
  • 475
2 votes
1 answer
41 views

How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$

Assuming we found a constant $g$ and a prime $P$ which is able to produce all values from $1$ to $P-1$ with it's sequence $$s_{i} = g^{s_{i-1}} \mod P$$ $$s_0 = g$$ How many steps are needed to ...
user avatar
  • 475
2 votes
1 answer
68 views

How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$

EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd. For tetration modulo prime $P$ $$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\...
user avatar
  • 475
4 votes
0 answers
73 views

Security of ECDLP using elliptic curves over an extension field

It is known that, for an elliptic curves $E$ defined over a prime field $\mathbb{F}_p$ such that $E(\mathbb{F}_p)$ is a prime number, the best algorithms (beside some specific cases) for solving the ...
user avatar
  • 141
3 votes
1 answer
143 views

Distinguishing points in elliptic curves over binary extension fields using Trace

Let $E$ be an elliptic curve curve $𝑦^2 + xy ≡ 𝑥^3+𝑎𝑥^2+𝑏$ (a Weierstrass curve) (in this case, with characteristic 2) over a binary extension field $𝐺𝐹(2^{m})$ with constructing polynomial $𝑓(...
user avatar
1 vote
1 answer
81 views

On access to a Diffie Hellman oracle

Assume $g$ is generator of multiplicative group modulo prime $p$. Assume we know $g^X\bmod p$ and $g^{XY}\bmod p$ and assume we can have access to a Diffie-Hellman oracle. Can we find $g^Y\bmod p$ in ...
user avatar
  • 882
1 vote
1 answer
55 views

Proof of knowledge of constant discrete log in the bilinear setting

Consider a pairing $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ with generators $g_1$, $g_2$ for $\mathbb{G}_1$, $\mathbb{G}_2$ respectively. The groups $\mathbb{G}_1$, $\...
user avatar
0 votes
0 answers
59 views

Given a series $g^n \mod P$. Can consecutive members be assigned to a unique value which if given the next and previous unique value can be computed

Given a safe prime $P$ and a generator $g$ which generates all values from $1$ to $P-1$ with $$g^n \mod P$$ 1.) Is there now a function $f$ which assigns a unique value to a range of members $$f(g^{i-...
user avatar
  • 475
1 vote
1 answer
45 views

Pairings for Beginners: Pohlig–Hellman attack time complexity

I'm reading Pairings for beginners by Craig Costello. I'm trying to understand this example of (what I think) is the Pohlig–Hellman algorithim (on page 31 of the book). Consider $E/\mathbb{F}_{1021}\,...
user avatar
  • 247
1 vote
2 answers
97 views

How to find the extractor in the Knowledge-of-Exponent Assumption?

From Mihir Bellare's paper Let $q$ be a prime such that $2q +1$ is also prime, and let $g$ be a generator of the order $q$ subgroup of ${Z^∗}_{2q+1}$. Suppose we are given input $q$, $g$, $g^a$ and ...
user avatar
  • 1,637
1 vote
1 answer
78 views

Hardness of a variant of the CDH problem

Given $g$, a generator of a multiplicative group (over some finite field or elliptic curve), and the group elements $\left( g^x, g^a, g^b, g^c, g^{x(a+b)}, g^{x(b+c)} \right)$, is possible to ...
user avatar
  • 461
1 vote
1 answer
84 views

Would discrete-log-based signing and encryption have been a better choice than RSA?

Diffie-Hellman can be used for key exchange, and can be used as part of an integrated encryption scheme ("DLIES"). Schnorr signatures are possible by relying only on the discrete-log problem,...
user avatar
  • 2,698
0 votes
1 answer
77 views

Is the base equally well protected by the discrete logarithm problem as the exponent?

I'd like to ask if in case of modular exponentiation, reverse engineering the base would be equally difficult, when knowing the exponent as determining the exponent is hard when the base is provided? ...
user avatar
2 votes
1 answer
114 views

Solve DLOG using a probabilistic algorithm for DLOG lsb

Following the question Can I know from a Bitcoin public key if the private key is odd or even? The answer there gives a simple algorithm for solving the Discrete Logarithm Problem when given an oracle ...
user avatar
  • 10.5k
1 vote
1 answer
88 views

Is $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ with $p$ prime (strongly) collision-free?

Let $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ for $g \in \mathbb{Z}_{p}^{*}$ where $p$ is prime. Is this function (strongly) collision-free meaning we cannot find ...
user avatar
  • 121
6 votes
1 answer
608 views

Small error in security proof on the paper On the Multi-User Security of Short Schnorr Signatures with Preprocessing

I think I found a small error in the security proof Link end of page 37. It states that $ \sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q +1)q/2+2}{p - (3q +2)^2 /4}$. But shouldn't it be $\...
user avatar
3 votes
2 answers
266 views

Time Complexity Of Solving DLog When g and P are known

This (https://en.m.wikipedia.org/wiki/Discrete_logarithm) Wikipedia article confuses me. If you have the equation a = g^n (mod P), and g, P and a are all known, then how does a brute force solving for ...
user avatar
0 votes
1 answer
66 views

What Is The Maximum Value For N In Discrete Logarithm Problems?

I have some code, which can crack a discrete logarithm problem in ~ O(0.5n) time. However, this only works if, in the following, N is less than P: G^N (mod P). To be clear, my program can figure out ...
user avatar
6 votes
1 answer
181 views

Finding large devious primes

Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could ...
user avatar
1 vote
0 answers
88 views

Modifying discrete logarithm problem in Zp by selecting a subset of group elements

Let $g$ generator of cyclic group $Z_p$ of order $p-1$, where $g$ can generate all group elements $\alpha \in Z_p$ as $\alpha = g^x$mod$p$, $x \in (0..p-1)$, where the discrete logarithm problem is ...
user avatar
  • 164
0 votes
1 answer
96 views

Solving a discrete log with BsGs

If we consider a group G with modulus p, order q with $p=2*q+1$, and generator $g=2$ ($ p$, $q$ huge prime numbers), is there a way to solve the discrete log problem $ g^x = y $ for a y given, using ...
user avatar
4 votes
1 answer
476 views

What's the main difference between the Schnorr identification scheme and its Smart-Card implementation?

This question arises because I couldn't find any official paper for the Schnorr identification scheme, but only for the Smart-Card implementation of it. Also, it seems that everyone, when talking ...
user avatar
1 vote
1 answer
161 views

Understanding Practical Differences Between ElGamal and Diffie-Hellman

I've been tasked with building a Web Assembly site that implements E2EE. I was thinking of using ElGamal Encryption to encrypt the message and Diffie-Hellman to establish the key. After doing further ...
user avatar
  • 11
1 vote
1 answer
138 views

Discrete Logarithm in the generic group model is hard - Theorem by Shoup

In Shoups well-known paper Lower bounds for Discrete Logarithms and Related Problems he proves that the Discrete Logarithm Problem is hard in the generic group model (if group operation and inverse ...
user avatar

1
2 3 4 5
12