5
votes
Accepted
What's wrong with this simple reduction of discrete logarithms to the Diffie-Hellman problem?
You are essentially describing the reduction by den Boer. It works fine (i.e., your idea works), but it has the disadvantage that the runtime essentially depends on the prime factorization of $q-1$. ...
- 66
5
votes
Accepted
Calculate discrete log with known phi
As far as we know, no, there is no general method to efficiently solve the Discrete Logarithm Problem for composite $N$ even when $\phi(N)$ is given and $N$ is the product of two distinct primes†. ...
- 138k
5
votes
Accepted
Discrete Logarithm Challenges and Records
For discrete log over $\mathbb{Z}_p^{*}$, as of 2019, a discrete logarithm was computed over a 795 bit safe prime [1].
In practice, no one uses generic discrete logarithm algorithms (such as pollard ...
- 929
4
votes
Accepted
Challenges like RSA factoring challenge
Not that I am aware of.
See the Certicom ECC challenge
See the Darmstadt LWE challenge (part of a larger set of lattice challenges)
Closest is probably the decoding challenge, though this is not ...
- 21.9k
4
votes
Accepted
Multiplicative inversion of a generated point?
But can you construct $p^{-1}G$?
No, you can't if:
You're assuming that you can compute the inverse modulo an arbitrary base point (rather than a fixed one)
The CDH problem is hard.
That's because ...
- 145k
4
votes
Method to break a baby Elliptic Curve analog to secp256k1
Solving discrete logarithms in $144$-bit groups is hard
Even scaling down to 144-bits is likely beyond current capability. To my knowledge the largest elliptic curve problem tackled with "black ...
- 21.9k
4
votes
Modular multiplication of two k-bit numbers takes k^2 modular additions?
TL,DR: The quote is wrong. Repair it by changing $k^2$ to $k$, or by counting bit operations rather than modular additions.
We can perform multiplication modulo $p$ of two $k$-bit numbers $A$ and $B$ ...
- 138k
3
votes
Accepted
On a problem assuming Diffie-Hellman oracle
If the group is of known prime order $q$ (which is usually the setting in which DH is considered), then $g^{1/x} = g^{x^{q-2}}$, and the latter can be obtained with $O(\log q)$ calls to the DH oracle.
- 2,114
3
votes
Modular multiplication of two k-bit numbers takes k^2 modular additions?
We want to find $x$ such that $ g^x = h$, i.e. the discrete logarithm of $h$ to the base $g$ in $\mathbb F_p^*$ with $g$'s order $n$.
For trial-and-error, brute-force, we can start to find $g^x$ ...
- 47.6k
3
votes
discrete logarithm equality for independent groups
Here's a paper describing how to do it efficiently, with some concrete sizes depending on the size of $a$ and $b$: https://eprint.iacr.org/2022/1593, Fig. 1 (check table 1 for notation).
It uses the ...
- 31
3
votes
Accepted
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$?
Computing $xG_1$ knowing only $G_1$, $G_2$, and $xH$ is as hard as the computational Diffie-Hellman problem (CDH).
For some given $xH$ we can choose, for example, $G_1 = yH$ and $G_2 = H - G_1$. This ...
- 339
3
votes
Accepted
When does index calculus work for discrete log?
There are a various situations where index calculus can be used to solve discrete logarithms. The classic index calculus of Western and Miller can be used for multiplicative subgroups of $(\mathbb Z/n\...
- 21.9k
3
votes
Why NIST 800-56A rev3 does not use cross secret calculation in C(2e, 2s, ECC CDH) scheme?
The proposed protocol looses the Forward Secrecy that the original protocol offers. Recall that's defined in NIST SP 800-56A Rev. 3 as
Forward Secrecy (FS): Assurance obtained by one party in a key-...
- 138k
2
votes
Best Known Attacks on Discrete Logarithm in Generic Groups
The generic group model is an idealized cryptographic model for which an adversary only has access to a group oracle, which simulates a generic group of prime order. The intuition is that the group ...
- 929
2
votes
Key exchange from discrete logarithm only
The difficulty ranking from hardest to easiest is discrete logarithm, computational Diffie-Hellman, decisional Diffie-Hellman. Consequently any security property that relies on the hardness of the ...
- 21.9k
2
votes
Accepted
Finding scalar in scalar multiplication on secp256k1 elliptic curve
There is no known feasible method to find the private key $k$ for a random public key $Q$, or equivalently for $Q$ computed from a random secret $k$ in $[0,n)$, where $n$ is the known order of ...
- 138k
2
votes
Accepted
Implementing Floor Division on secp256k1 Elliptic Curve in Python
Let, us have a public base point $G$ on the curve $E$, and let us have a public key $P$ with a related secret key $k$ with $P = [k]G$.
Discrete Logarithm
Finding $k$ given $G$ and $P$ and curve ...
- 47.6k
2
votes
Why NIST 800-56A rev3 does not use cross secret calculation in C(2e, 2s, ECC CDH) scheme?
The way one avoids KCI attacks in C(2e, 2s) is to obtain assurance of the possession of a private static key as per Section 5.6.2.2.3.
In NIST SP 800-56A Rev. 3, this is unfortunately not considered ...
- 7,629
1
vote
Fast Algorithms for generalized Discrete Logarithm?
Are you looking for an algorithm that's faster or slower?
For a cyclic group I don't expect this to be faster than standard discrete log.
If you have an algorithm that can solve this generalized ...
- 1,105
1
vote
Accepted
Is it possible to forge valid proofs in this Schnorr signature-based ZKP system for proving knowledge about discrete logarithms?
E.g. let $r\in_R \mathbb{Z}_q$, we can construct a "proof" {$g^v, r$} by taking $g^v = g^r(g^{x_i})^h = g^r g^{x_i h}$ despite not knowing the value of $v$ or $x_i$.
That doesn't work. ...
- 145k
1
vote
Accepted
Can we make Discrete Log (significant) more secure by introducing non-commutative algebra (e.g. matrices, hypercomplex numbers, )
I would say that the answer is no without any significant introduction of new techniques. As stated in the comment, the question is too broad.
There was quite a bit of effort expended by community ...
- 21.2k
1
vote
Accepted
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.
Two things:
That'...
- 145k
1
vote
Accepted
Discrete log hardness when secret is multiplied by public value
is $y = g ^ {kx}$ also equally secure if the value $k$ is a publicly known value which was randomly selected from a uniform distribution ?
Here is a clearer way to look at it: suppose we have an ...
- 145k
1
vote
Accepted
Hiding property of Elgamal-like bit commitment
The decisional Diffie-Hellman (DDH) assumption is needed to prove hiding property of this ElGamal-like bit commitment scheme. This question was examined by this lecture notes [Lecture Notes ...
- 363
1
vote
Hiding property of Elgamal-like bit commitment
Breaking DDH would allow verifying the opening of a commitment x without knowing u. If the space of possible ...
- 1,701
1
vote
Best Known Attacks on Discrete Logarithm in Generic Groups
For a discrete logarithm problem in a generic group of size $N$
with no special algebraic structure, the best known attack is the Pollard's rho method.
I believe such a statement would actually ...
- 145k
1
vote
Accepted
Can some cryptographic conclusions in the prime field be applied to the Galois field？
Even the integer Discrete Log (DL) is not known to be NP complete. As pointed out in the comment by @poncho, $NP\neq coNP$ which may well be the case would imply that DL is not NP-hard.
Its exact ...
- 21.2k
1
vote
Trying to understand p-adic logarithm map in elliptic curves
What I don't understand is why is it easy to solve the discrete logarithm problem in $\mathbb{Z}/p\mathbb{Z}$. Isn't the Diffie Hellman key exchange based on the difficulty of computing discrete ...
- 11.7k
1
vote
Accepted
Difficulty of Shor's algorithm in a Schnorr group as a function of the modulus
How does the magnitude of $p$ influence the difficulty of doing this, by some useful criteria?
Well, the expensive part of Shor's algorithm is the necessity of performing $O(\log q)$ multiplications (...
- 145k
1
vote
How does the Number Field Sieve find the target number for Diffie-Hellman?
Factorization is in mathematics the process by which an algebraic expression is converted from a sum to a factor. The terms involved in the product are called factors and when multiplied together they ...
- 112
Only top scored, non community-wiki answers of a minimum length are eligible