# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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$ ...
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....
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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$?
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
52 views

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 ...
1 vote