As of May 31, 2023, we have updated our Code of Conduct.

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
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 ...
user1035648's user avatar
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 ...
obareey's user avatar
  • 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 ...
kodlu's user avatar
  • 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 ...
kodlu's user avatar
  • 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 ...
RobinLinus's user avatar
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 ...
shy-student's user avatar
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 ...
Vincent's user avatar
  • 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 ...
ZhuJerry's user avatar
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 ...
RobinLinus's user avatar
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 ...
Albert's user avatar
  • 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 ...
mti's user avatar
  • 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 ...
filter hash's user avatar
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 ...
Nserser's user avatar
  • 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 ...
Rui 's user avatar
  • 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 ...
Sanu's user avatar
  • 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 ...
fgrieu's user avatar
  • 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.
Pau T's user avatar
  • 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?
Shi Li's user avatar
  • 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 $$
rozi's user avatar
  • 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}...
Caio Nogueira's user avatar
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 ...
nickponline's user avatar
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^...
youngeAn's user avatar
  • 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 ...
RobinLinus's user avatar
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$ ...
Rudeus's user avatar
  • 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 ...
Alia's user avatar
  • 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$?
user avatar
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?
Arthur Strong's user avatar
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 ...
Neel Basu's user avatar
  • 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 ...
Omar Shehab's user avatar
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 ...
Z. Chen's user avatar
  • 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 ...
Anon's user avatar
  • 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 ...
rudeus123's user avatar
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 ...
Dimitri Koshelev's user avatar
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) ...
J. Smitherson's user avatar
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 $[...
lamba's user avatar
  • 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}$"...
Hesham Abdelgawad's user avatar
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 ...
Doron's user avatar
  • 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 ...
Dave Kent 's user avatar
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^{...
mti's user avatar
  • 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?
Guest007's user avatar
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 $...
zugzwang's user avatar
  • 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 ...
crypcrypcryp's user avatar
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 ...
Edward's user avatar
  • 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 ...
SrcMiLe's user avatar
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 ...
Anon's user avatar
  • 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 ...
Amir Amara's user avatar
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 ...
Leli's user avatar
  • 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?
Turbo's user avatar
  • 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}^*$ ...
user101299's user avatar
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. ...
Marcos's user avatar
  • 133

1
2 3 4 5
13