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.
609
questions
0
votes
2
answers
70
views
Hiding property of Elgamal-like bit commitment
An Elgamal-like bit commitment scheme:
Let $\langle g \rangle$ be a group of order $n$, where $n$ is a large prime.
Let $h\in_{R}\langle g \rangle\setminus\{1\}$ denotes a random group element such ...
- 119
4
votes
2
answers
114
views
Why NIST 800-56A rev3 does not use cross secret calculation in C(2e, 2s, ECC CDH) scheme?
In the NIST 800-56A rev3 "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography" in section 6.1.1.2 "(Cofactor) Full Unified Model, C(2e, 2s, ECC ...
- 117
2
votes
2
answers
96
views
Best Known Attacks on Discrete Logarithm in Generic Groups
This is a followup to my recent question Discrete Logarithm Challenges and Records.
I am interested in confirming my understandings from the answer to that question, stated below:
For a discrete ...
- 20.1k
3
votes
1
answer
261
views
Discrete Logarithm Challenges and Records
I am wondering whether there are any current challenge problems for Discrete Logarithms.
Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups.
It turns out CERTICOM still has some ...
- 20.1k
2
votes
1
answer
83
views
Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?
Given some group in which both discrete logarithms and the computational Diffie-Hellman problem are hard. Furthermore, two random, unrelated group generators $G_1, G_2$, and a third generator defined ...
- 339
5
votes
2
answers
163
views
Method to break a baby Elliptic Curve analog to secp256k1
What would be the method of choice to compute the private key from the public key on a baby analog of secp256k1, say with $p$ and $n$ 144-bit?
What would be the pros and cons of Pollard's rho and ...
- 51
3
votes
0
answers
48
views
Prove DSA signature scheme is EUF-CMA secure
I want to prove that the DSA signature scheme is EUF-CMA secure in the random oracle model, if the discrete logarithm problem is hard. I know it can be proved by the following two parts:
Discrete ...
- 31
1
vote
1
answer
39
views
Can some cryptographic conclusions in the prime field be applied to the Galois field？
Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two ...
- 23
6
votes
1
answer
458
views
What's wrong with this simple reduction of discrete logarithms to the Diffie-Hellman problem?
This recent paper shows that discrete logarithms are solvable if you have an oracle for the Diffie–Hellman problem. However, to me, it seems there is a much simpler reduction and I wonder where I am ...
- 339
1
vote
0
answers
24
views
How can I perform a one-client MITM attack in a Diffie-Hellman key exchange? [closed]
Suppose we have intercepted a public key exchange (via Diffie-Hellman protocol). In addition to the keys A and B, the generator g and the module p are known.
Assuming that it is possible to exchange ...
- 11
3
votes
0
answers
20
views
Verifiable encryption: Comparison between FS01 and CS03
Consider the following two verifiable encryption schemes for Discrete Logarithm.
FS01: “One Round Threshold Discrete-Log Key Generation without Private Channels” by Pierre-Alain Fouque and Jacques ...
- 519
1
vote
0
answers
47
views
Is the composite order matrix-DDH secure?
I recently read a paper that proposed a matrix-DDH which is a matrix variant of DDH assumption. The brief definition is follows:
Let $G$ be a group of prime order $q$.
Then, the matrix-DDH says that ...
- 149
1
vote
1
answer
45
views
The hardness of deducing z (\in Z/pZ) from z^l and l
I am writing to request information about the difficulty of finding z in Z/pZ (where p is a large prime) given z^l and l. I am working on a project that involves this problem, and I am interested in ...
- 13
1
vote
1
answer
62
views
Trying to understand p-adic logarithm map in elliptic curves
Im following these slides from "An Introduction to the Theory of Elliptic Curves" http://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf,
but I'm having some difficulty ...
- 31
2
votes
0
answers
59
views
Discrete log problem over special primes
I am trying to find discrete log over $GF(P)$ using Cado-NFS (https://gitlab.inria.fr/cado-nfs/cado-nfs/-/blob/master/README.dlp). It works well for random primes. But if I take primes that are ...
- 23
4
votes
1
answer
100
views
Difficulty of Shor's algorithm in a Schnorr group as a function of the modulus
Consider a Schnorr group with order a prime $q$ sized for security against current computers (like $q$ of 256 bit); modulus a prime $p=q\,r+1$ large enough (e.g. 3072 to 32768-bit) that the algorithms ...
- 134k
2
votes
0
answers
75
views
Could classical computers end up breaking the ECDLP through prime factorization (GNFS)?
Is there any way in which classical computers oculd end up breaking ECDLP. I read that GNFS could through prime factorization, but I am not sure if I understood this properly.
- 51
1
vote
0
answers
54
views
They key size of the Schnorr Signature Algorithm
Based on the Schnorr signature below: What is the suitable size of lamda to generate a secure key?
- 13
3
votes
1
answer
101
views
Calculate discrete log with known phi
Is it possible to efficiently solve the discrete log problem for $r$:
$$
g^r\equiv v\pmod N
$$
When the following constants are know:
$$
N,\ g,\ v,\ \phi=(p-1)(q-1)\text{ s.t. }N=p\,q
$$
- 55
1
vote
0
answers
82
views
DDH, CDH and discrete logarithm assumptions
When we consider a group generation algorithm $\mathcal{G}$ (taken from Katz and Lindell's Introduction to Modern Cryptography), that takes as input a security parameter $1^n$ and outputs $(\mathbb{Z}...
2
votes
0
answers
52
views
Does Pohlig-Hellman algorithm work for non-prime powers?
I implemented the Pohlig-Hellman algorithm for the general case following Wikipedia but it only seem to work for prime powers (which is what the limited case is meant to solve).
My implementation ...
- 121
1
vote
1
answer
115
views
The Uniqueness of Baby-step-Giant-step Algorithm on DLP
The algorithm tells that, in the effort of solving $a^x \equiv b \text{ mod }N$:
Choose some $k \in \mathbb{N}$.
Create the baby list: $\{1,a,a^2,...,a^{k-1}\}$
Create the giant list: $\{ba^{-k},ba^...
- 145
5
votes
1
answer
500
views
How fast is Factorization reduced to a Discrete Logarithm?
Given a RSA modulus $n$, which is the product of two safe primes:
\begin{align*}
P &= 2p + 1 \quad\quad\quad
Q = 2q + 1 \\
n &= P \cdot Q = 4p q + 2 p + 2 q + 1
\end{align*}
The ...
- 339
3
votes
1
answer
158
views
How to choose Kangaroo algorithm parameters?
I am implementing pollard kangaroo to compute the discrete logarithm of a group element $G$ of generator $g$. $G$ is a$\mod p$ multiplicative group ($p$ a prime number). So, I want to solve $g^a=h$ ...
- 33
2
votes
0
answers
118
views
If $e(aP, bP) = e(P, P)^{ab}$ then how can we solve $e(P^a, P^b)$?
I'm a bit confused regarding the bilinear pairing operation. Let's say I have a Public key of a receiver $P_r = P^x$ and I want to create a symmetric key using KEM with a pairing operation. If I chose ...
- 51
0
votes
0
answers
108
views
Finding $a$ in $g^a\bmod p$ in Diffie-Hellman [duplicate]
This might be a silly question but I am unable to wrap my mind around it. In Diffie-Hellman can we find $a$ when $A = g^a\bmod p$, given we know $A$, $g$ and $p$?
user104263
0
votes
0
answers
109
views
Difference between ElGamal and Schnorr signature
A question about Schnorr group.
Am I right that this is basically a protection against discrete-log solvers?
So Schnorr signature is better than ElGamal in that sense?
0
votes
1
answer
56
views
Crypto++ Multiplicative inverses do not reciprocate in ModularArithmetic group
My mathematical assumption is $(g^rx')^x = g^r$ where $x'$ is the multiplicative inverse of $x$ and $g$ is the generator of the group. I am calculating $(g^rx')^x$ in ...
- 153
0
votes
0
answers
87
views
Cryptographic functions as feature map/kernel function?
Has there been any use of cryptographic function as a kernel function with support vector machine? There are several standard kernels to be used with SVMs each with its own scenario.
I was not able to ...
2
votes
1
answer
482
views
How to prevent the solution of a discrete logarithm problem from being found in a collision way by accident
Suppose there is a popular system that is widely used by a huge amount of people. Its security protocol provides a finite group with a generator $g$, and users need to choose a random number $r$ and ...
- 163
1
vote
1
answer
84
views
Why is the following not a ZKP for discrete log?
Before looking at the textbook ZKP for discrete log, I tried to construct one myself. This turned out quite different to the textbook one, and I've been wondering what might be wrong with it? (I was ...
- 383
0
votes
0
answers
54
views
Bruteforcing the discrete logarithm with a decomposable prime modulus
I came across an interesting challenge recently. I need to find x such as :
$s=n^x \mod m$
We suppose we have $s, n$ and $m$. The modulus $m$ is prime and $n$ is a primitive root modulo $m$.
The ...
5
votes
1
answer
170
views
Will a semi-hyperelliptic pairing be used in real-world cryptography if it is faster than state-of-the-art elliptic pairings?
Let $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ stand for three groups of the same large prime order $r$. I invented a pairing $e\!: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ (with ...
- 355
1
vote
0
answers
190
views
Assuming secp256k1 curve and given fixed (but random) $h$ and $d$ values, is it possible to calculate a $k$ such that $h\equiv(k\,G)_X\,(k-d)\pmod n$?
For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that:
$$h\equiv(k\,G)_X\,(k-d)\pmod n$$
where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) ...
3
votes
0
answers
64
views
Algorithm for checking elliptic curve discrete log
Suppose the tuple $(P, a, Q)$ is given, where $P$ and $Q$ are points on an elliptic curve (I'm more interested in Montgomery curves but other curves are also fine), $a$ is a scalar and the notation $[...
- 1,365
0
votes
0
answers
78
views
What is the best choice of the base g in El-Gamal PKC
I have just read in a book that in El-Gamal PKC, the best choice of a base g is a number whose order in the field ($\mathbb{F}_p$) is a large prime, and added: "approximately = $\frac{p}{2}$"...
1
vote
1
answer
69
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 ...
- 79
0
votes
0
answers
29
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
53
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^{...
- 519
2
votes
1
answer
126
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
155
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 $...
- 119
2
votes
1
answer
302
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
42
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
195
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
56
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 ...
- 383
0
votes
0
answers
68
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
95
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
71
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
3
votes
1
answer
148
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}^*$ ...
- 31
3
votes
1
answer
119
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