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.
626
questions
0
votes
1
answer
153
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 ...
- 9
3
votes
2
answers
454
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 ...
- 31
1
vote
1
answer
171
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$
...
- 21
0
votes
1
answer
101
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....
- 573
1
vote
1
answer
142
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 ...
- 13
1
vote
0
answers
31
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 ...
- 21
0
votes
0
answers
43
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 ...
- 908
0
votes
1
answer
32
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 ...
- 908
0
votes
1
answer
60
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$?
- 908
1
vote
1
answer
88
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 ...
- 135
1
vote
1
answer
30
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 ...
- 13
2
votes
1
answer
99
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 ...
- 71
0
votes
1
answer
54
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 ...
- 135
1
vote
1
answer
52
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$, $[...
- 187
0
votes
0
answers
30
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 ...
- 113
2
votes
1
answer
81
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 ...
- 23
3
votes
1
answer
157
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 ...
- 227
0
votes
2
answers
78
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 ...
- 223
1
vote
1
answer
483
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?
- 908
0
votes
2
answers
103
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 ...
- 363
4
votes
2
answers
148
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
166
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 ...
- 21.2k
4
votes
1
answer
364
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 ...
- 21.2k
2
votes
1
answer
90
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
287
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
110
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
42
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
497
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
53
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
23
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 ...
- 529
1
vote
0
answers
73
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
48
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
111
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
78
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
125
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 ...
- 138k
2
votes
0
answers
100
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.
- 61
1
vote
0
answers
84
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
136
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
88
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
75
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
125
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
544
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
210
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
109
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
135
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
63
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
484
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 ...
- 185
1
vote
1
answer
96
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