Skip to main content

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
0 answers
17 views

What logarithm does the "discrete logarithm problem" refer to in the context of ECC? [duplicate]

In the case of integers, solving the DLP is finding a solution to $n=\log_b(x)$ given $b$ and $x$. There's a "log" in the equation, so the name DLP makes sense. In the context of ECC, many ...
aryzing's user avatar
  • 123
1 vote
0 answers
73 views

Is generating random blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?

I know there’re many questions that ask how to safely HashToCurve, but I want to know if the method I found in an actual implementation is secured against the ...
user2284570's user avatar
0 votes
1 answer
63 views

diffie hellman key exchange compared with ECDH [closed]

I have to write a paper about the Diffie Hellman key agreement. I want to focus on the implementation with elliptic curves and comparing the safety for selected attacks such as Pollards Rho and ...
anonym's user avatar
  • 1
2 votes
1 answer
200 views

Discrete log of Goldilocks, Babybear, and Mersenne31 fields

Does anyone know if the discrete log problem of these small prime fields: Goldilocks, Babybear, Mersenne31, has been solved? If not, is there a small prime field in which the discrete log of any ...
Jason's user avatar
  • 23
4 votes
2 answers
111 views

How do I solve a discrete log using pen paper for exam without bruteforcing it?

I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this 3 = (10^XA) mod 19 now everywhere I am finding only ...
Pragyan's user avatar
  • 141
6 votes
3 answers
4k views

Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?

For RSA, we need two primes p and q to define N = pq. We will only look how long it takes to generate a prime for p because the process is similar for q. From my lecture slides, my professor states ...
nasiedlak's user avatar
0 votes
1 answer
42 views

SDLog - looking for papers

Reading trough SEC 1 V2.0 in txe appendices there is a mention of a elliptic curve semi logarithm (ECSLP) being used to forge ECDSA signatures. I am looking for papers on that problem and have been ...
immigrantswede's user avatar
1 vote
1 answer
95 views

How to use smt solvers in order to restrict the possible key search where a portion of the private key and a portion of the public key hash is known?

I’m in the following situation : I’ve a portion/first bytes of a private secp256k1 security key such as it would take minutes to fully recover it through Pollard’s Kangaroo if I had the public key. ...
user2284570's user avatar
0 votes
0 answers
71 views

Why do we use elliptic curves instead of just the discrete logarithm problem?

We have a cyclic field Fp where p is a prime number, a generator g, and an order n. A generator is an element such that $g^n=1$. A random number x has been chosen as the private key, selected from the ...
Saku's user avatar
  • 101
2 votes
2 answers
86 views

On a diffie hellman related oracle

Given an oracle that can compute $g^{x^{-1}}\bmod p$ from $g^x\bmod p$ is it possible to compute $g^{x^2}\bmod p$ in polynomial time ($p$ is a prime and $g$ generates the multiplicative group modulo $...
Turbo's user avatar
  • 930
1 vote
0 answers
57 views

Choice of algorithm for ECDLP when you have information regarding private key

Okay, I have a ECDSA public key $P$. The curve is arbitrary and not necessarily secure. The finite field of curve, $q$, is a $315$ bit prime. I know the following information regarding key: The ...
madhurkant's user avatar
0 votes
1 answer
166 views

Is the discrete root considered a hard problem?

I know that in groups from large prime order the discrete log problem is considered hard. For example, it is hard to compute $x$ from $g^x$ and $g$. Does the same holds for the root problem? For ...
Amit Keinan's user avatar
2 votes
1 answer
89 views

Example of CM field discriminant of elliptic curves

From this answer I am able to understand that if CM field discriminant for a particular curve is small then it provide us a fast endomorphism which in turn allow rho method to speed up by $\sqrt{\frac{...
madhurkant's user avatar
2 votes
1 answer
59 views

Is it hard to find m, R to make RG^H(m||R)=C?

Assuming the generator of one group $\mathbb G$ is $G$. Given an element $C\in \mathbb G$ and a cryptographic hash function $H(\cdot)$, is it hard for one adversary to find a pair of message $m$ and ...
Twiforest's user avatar
1 vote
1 answer
102 views

Discrete log problem - does luck exist?

Assume the discrete log problem: $g^x mod (p) = h$ For sure, $p$ is a prime number and $g$ is its primitive root or generator and assume that Alice sent $h$ to Bob and middle man caught it. So ...
Giorgi Lagidze's user avatar
2 votes
2 answers
94 views

One group element hybrid encryption for El Gamal

I am really curious about this one problem 10.12 from Katz/Lindell's book. It goes as follows: I am quite sure we can assume that $\textsf{Enc}_k(m) \in \mathbb{G}$, as the authors devoted the whole ...
Michael Hammer's user avatar
2 votes
0 answers
64 views

Cryptographic accumulator via function composition

I am looking for an alternative to RSA accumulators, and I am wondering if the following option based on function composition might fit the bill. It seems like an obvious tweak on RSA accumulators, ...
Carson Farmer's user avatar
2 votes
0 answers
59 views

Can Index Calculus take advantage of small unknown?

The Index Calculus algorithm solves the Discrete Logarithm Problem of finding $x$ with $g^x\bmod p=b$ given $g$, $b$, and prime $p$. Assume $g$ is a generator, so that $x$ is uniquely defined in $[1,p)...
fgrieu's user avatar
  • 142k
2 votes
1 answer
353 views

How long would it take to calculate discrete log modulo a number modulo prime of 78 digits?

I am new to cryptography and encountered the discrete log problem. Given generator $g$, a prime $p$ and an integer $b$ calculate $x$ such that: $g^x \equiv b\mod{p}$ I have read that such a problem ...
esteregg's user avatar
2 votes
2 answers
361 views

Cost of solving multiple Discrete Logarithm Problems in the same group

We consider the Discrete Logarithm Problem of finding integer $x$ random in $[0,n)$ where $n$ is the group order, given $Y=G^x$ (or $Y=xG$) computed in the group noted multiplicatively (or additively),...
fgrieu's user avatar
  • 142k
0 votes
1 answer
332 views

Implementing Floor Division on secp256k1 Elliptic Curve in Python

I understand that the // operator is used for floor division in regular arithmetic result = 7 // 3 # This will result in 2 but ...
Favour's user avatar
  • 41
3 votes
2 answers
488 views

Modular multiplication of two k-bit numbers takes k^2 modular additions?

In Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman's book An Introduction to mathematical cryptography, 2nd edition, page 78, there is: If we are working in the group $\mathbb F^∗_p$ and if ...
fa william's user avatar
1 vote
1 answer
367 views

Finding scalar in scalar multiplication on secp256k1 elliptic curve

In elliptic curve cryptography using the secp256k1 curve, how can I determine the number of times the base point $G$ has been multiplied to derive a new point? The formula is as follow: $k * G = Q$ ...
Aviril Smith's user avatar
0 votes
1 answer
128 views

Can we make Discrete Log (significant) more secure by introducing non-commutative algebra (e.g. matrices, hypercomplex numbers, )

$$g^a = c \bmod{N} \text{ }\rightarrow \text{ }G_{i_1}G_{i_2}G_{i_3}...G_{i_n} = C \bmod N $$ At the Discrete Log problem we try to find the exponent ($a$) of a generator ($g$) over a finite filed....
J. Doe's user avatar
  • 453
1 vote
1 answer
206 views

Elliptic Curve Cryptography : discrete log and Diffie-Hellman

Here's my current understanding of how ECC works. There is a recipient and a sender - Alice and Bob and each has a public and private key - (Alice's private key is denoted by a and public key is ...
Laksh Sharma's user avatar
1 vote
0 answers
39 views

Disjunctive ZK Proof of knowledge of discrete log

I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements: $(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$ , the prover knows at least one ...
drydrydesert's user avatar
0 votes
0 answers
47 views

Practical deployments of ECC with cofactor of elliptic curves $4$ or $8$?

Are cofactor $4$ and $8$ ECC schemes widely used in practical deployments such as those in cryptocurrencies? Can you name some practical settings where there curves are used and cryptocurrencies where ...
Turbo's user avatar
  • 930
0 votes
1 answer
34 views

Higher least significant bits with larger multiple of 2 order

If order of the cyclic group on which discrete logarithm is done is $2q$ where $q$ is a prime such that $2q+1$ is a prime, then using square root identification we can get the lsb. How about if the ...
Turbo's user avatar
  • 930
0 votes
1 answer
71 views

On a problem assuming Diffie-Hellman oracle

If we have a Diffie-Hellman oracle then given $g^x$ and $g^y$ we can construct $g^{xy}$. Can we construct $g^{x^{-1}}$ given $g^x$?
Turbo's user avatar
  • 930
1 vote
1 answer
225 views

Fast Algorithms for generalized Discrete Logarithm?

I know the standard algorithms for D-log. Pollard-rho, Baby-step-big-step, Pollig-Hellman, index calculus, etc. I'm looking for fast algorithms to find a relation for the generalized discrete ...
mtheorylord's user avatar
1 vote
1 answer
59 views

Is it possible to forge valid proofs in this Schnorr signature-based ZKP system for proving knowledge about discrete logarithms?

I am currently reading the paper "A 2-round anonymous veto protocol" and have run into some trouble verifying the claims made about the zero knowledge proofs presented within. My knowledge ...
user7308228's user avatar
2 votes
1 answer
141 views

Prove with ZKP that I have encrypted a message $v + random\_number\cdot c$ given an RSA public key?

I want to create an application in which users can cast vote to blockchain in encrypted form using RSA. The private key will be revealed only after completion of the election. My major use case is as ...
P S's user avatar
  • 71
0 votes
1 answer
77 views

Multiplicative inversion of a generated point?

Let's say I have a public generator $G$, an unknown, private $p$ and a public point $pG$ on an elliptic curve. Given $pG$ it's easy to construct $-pG$ by just taking the negative. But can you ...
mtheorylord's user avatar
1 vote
1 answer
87 views

Interpolating polynomial discrete log

This is taken from page 16 of Stacking Sigmas Essentially, let $0<t<\ell$ be integer values smaller than a certain prime modulus $q$. We have a set $\mathcal{X}$ with $|\mathcal{X}|=\ell-t+1$, $[...
Cristian Baeza's user avatar
0 votes
0 answers
32 views

Cryptographic Applications of Composite Modular Exponentiation

I've developed an algorithm for fast modular exponentiation modulo composite numbers with known factorization. I'm not very well versed in cryptography, so I'm wondering if any of you know of an ...
TheBestMagician's user avatar
2 votes
1 answer
92 views

Discrete log hardness when secret is multiplied by public value

Given y = g ^ x is discrete log hard on some finite field, is y = g ^ (kx) also equally secure if the value ...
ManishB's user avatar
  • 23
3 votes
1 answer
216 views

When does index calculus work for discrete log?

Reading about index calculus for discrete logarithm, I noticed that it works for $(\mathbb Z / p \mathbb Z)^*$. Is this the only situation in which it works? If not, please give examples of other ...
Craig Feinstein's user avatar
0 votes
2 answers
103 views

Key exchange from discrete logarithm only

Diffie-Hellman key exchange is sometimes informally said to be hard under the discrete logarithm assumption in the chosen group. But if I am reading literature correctly, it actually uses a stronger ...
Ilk's user avatar
  • 233
1 vote
1 answer
507 views

Challenges like RSA factoring challenge

RSA factoring challenge is a famous one and is still not completely solved. Are there similar challenges for Discrete log over $\mathbb Z_p^*$? Discrete log over Elliptic curves? LWE? LPN?
Turbo's user avatar
  • 930
0 votes
2 answers
167 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
163 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
390 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
  • 22.7k
5 votes
1 answer
527 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
  • 22.7k
2 votes
1 answer
98 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
6 votes
2 answers
508 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
211 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
44 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
566 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
73 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
26 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
  • 655

1
2 3 4 5
13