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.
575
questions
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 ...
- 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 ...
- 35
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^{...
- 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?
- 21
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 $...
- 79
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 ...
- 47
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 ...
- 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 ...
- 1
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 ...
- 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 ...
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 ...
- 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?
- 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}^*$ ...
- 21
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.
...
- 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^...
- 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 ...
- 31
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 ...
- 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.
...
- 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 ...
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 ...
- 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 ...
- 47
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 ...
- 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 ...
- 313
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 ...
- 11
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?
- 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)$ ...
- 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: ...
- 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 ...
- 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\...
- 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 ...
- 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 $𝑓(...
- 115
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 ...
- 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$, $\...
- 188
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-...
- 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}\,...
- 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 ...
- 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 ...
- 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,...
- 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? ...
- 37
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 ...
- 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 ...
- 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
$\...
- 379
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 ...
- 33
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 ...
- 33
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 ...
- 362
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 ...
- 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 ...
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 ...
- 111
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 ...
- 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 ...
- 379