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
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 ...
Favour's user avatar
  • 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 ...
fa william's user avatar
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$ ...
Aviril Smith's user avatar
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....
J. Doe's user avatar
  • 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 ...
Laksh Sharma's user avatar
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 ...
drydrydesert's user avatar
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 ...
Turbo's user avatar
  • 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 ...
Turbo's user avatar
  • 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$?
Turbo's user avatar
  • 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 ...
mtheorylord's user avatar
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 ...
user7308228's user avatar
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 ...
P S's user avatar
  • 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 ...
mtheorylord's user avatar
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$, $[...
Cristian Baeza's user avatar
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 ...
TheBestMagician's user avatar
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 ...
ManishB's user avatar
  • 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 ...
Craig Feinstein's user avatar
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 ...
Ilk's user avatar
  • 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?
Turbo's user avatar
  • 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 ...
user1035648's user avatar
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 ...
obareey's user avatar
  • 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 ...
kodlu's user avatar
  • 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 ...
kodlu's user avatar
  • 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 ...
RobinLinus's user avatar
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 ...
shy-student's user avatar
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 ...
Vincent's user avatar
  • 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 ...
ZhuJerry's user avatar
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 ...
RobinLinus's user avatar
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 ...
Albert's user avatar
  • 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 ...
mti's user avatar
  • 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 ...
filter hash's user avatar
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 ...
Nserser's user avatar
  • 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 ...
Rui 's user avatar
  • 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 ...
Sanu's user avatar
  • 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 ...
fgrieu's user avatar
  • 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.
Pau T's user avatar
  • 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?
Shi Li's user avatar
  • 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 $$
rozi's user avatar
  • 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}...
Caio Nogueira's user avatar
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 ...
nickponline's user avatar
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^...
youngeAn's user avatar
  • 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 ...
RobinLinus's user avatar
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$ ...
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
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$?
user avatar
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?
Arthur Strong's user avatar
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 ...
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
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 ...
Z. Chen's user avatar
  • 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 ...
Anon's user avatar
  • 383

1
2 3 4 5
13