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.
0
votes
1answer
60 views
How should one refer to the smallest remainders generated by a modulus within DH or DLP?
It's my understanding that the integer base and exponents chosen to create the initial public keys in DH are from the remainders of a modulus.
For example, if the value of the modulus is $N=11$, a ...
4
votes
1answer
112 views
Digital Signature Algorithm (DSA) with medium fields
I understand it when we have to solve Discrete Logarithm Problem $a^x\equiv b\pmod p$, where $a$ and $b$ are given integers and we have to find secret integer $x$ that makes the equation true for some ...
-1
votes
1answer
93 views
Can Shamir’s Trick crack the cryptographic strength of ECDSA?
Recently stumbled upon a discussion in the forum "MyMathForum"
What is Shamir’s Trick used for?
Are there any such examples?
3
votes
1answer
64 views
In NIST modulus and key size recommendations is `group` equivalent to modulus and `key` equivalent to exponent?
Looking at the following NIST recommendations for a discrete logarithm, for 2016-2030 and beyond they list 3072-bit number for the group and 256-bit for the ...
3
votes
1answer
162 views
Diffie-Hellman private key recover with non-prime modulus
Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key:
p,g,y
Where $p$ is the modulus, $g$ is the base, $y$ is the ...
-2
votes
1answer
49 views
Elliptical Curve Actual Encryption
Im havirng a had time understanding ECC. For example, I have the equation below:
...
2
votes
0answers
55 views
Distributed key generation (for discrete-log based cryptosystems) with fake shares
Under the definition of Gennaro et al (link), a DKG protocol needs to satisfy “correctness” and “secrecy”. Correctness is divided into three sub-properties:
C1. All subsets of $t+1$ shares provided ...
0
votes
0answers
88 views
Using division polynomials to prove that EC discrete log is even
This question is related to the other question I recently asked. I'm trying to figure out if it is possible to use division polynomials to prove that knowing $A = a \cdot G$ we can prove that $a$ is ...
-1
votes
1answer
108 views
How does Diffie Hellman protocol work in Bitcoin Blockchain Transactions?
Greetings to all! Please explain how the Diffie-Hellman protocol works in Bitcoin?
That is, in Blockchain Transactions, there is also a total number of "K" recipient and sender?
"K" the recipient and ...
0
votes
0answers
12 views
Are compressed pairings used for Barreto-Naehrig curves in practice?
In 2009 Galbraith and Lin wrote the article "Computing Pairings Using x-Coordinates Only" https://link.springer.com/article/10.1007/s10623-008-9233-3, where they proposed to compute pairings on ...
2
votes
2answers
78 views
Random Self-reducibility in Discrete Log
I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is
how does it show that DL is hard in the average case.
The probability of success of an ...
0
votes
0answers
40 views
Discrete Logarithm within DH exchange - finding out A and B secret number [duplicate]
How would i find out Alices or Bobs private number from the details exchanged in public.
prime - g = 7
primitive root - n = 3
Alice - A = 3
Bob - B = 4
The details visible in public exchange are:
...
1
vote
1answer
70 views
Continuous logarithms in cryptography
Cryptographic procedures seem to almost exclusively use discrete logarithms rather than continuous logarithms. Hence, I assume there are good and sound reasons for this.
In essence, answers provided ...
3
votes
1answer
116 views
Why is Diffie-Hellman Insecure If Order of the Generator Has Only Small Prime Factors?
In this post from security SE, Tom Leek mentioned that, for Diffie-Hellman to be secure order of the group $g$ should have a prime factor at least $2k$ bits long, where $k$ is the security parameter.
...
2
votes
2answers
132 views
What prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic?
Does the size of base, exponent, and modulus thwart the Giant-step/Baby-step algorithm in solving DLP using modular arithmetic or is it the use of a property of a particular prime as the modulus, or ...
2
votes
0answers
47 views
Proving key equivalence across different elliptic curves
We can use the technique described in this answer to prove key equivalence across two elliptic curves of different order. I'm wondering if modifying the technique as described below would compromise ...
0
votes
1answer
38 views
Collisions in Diffie-Hellman private keys
Given a generator $g$, a large, safe prime $P$ and a result of the DH key exchange $g^{xy} \mod P$, how would I come up with two different $x', y'$ s.t. $g^{x'y'} = g^{xy} \mod P$
0
votes
0answers
37 views
Algorithm to compute DLOG for elliptic curve $E(F_p)$ with order p
I was reading about elliptic curves in this pdf. Page 55 of the pdf states that if number of points on elliptic curve #$E(F_p) = p$, then there exists a p-adic logarithmic map that homomorphically ...
2
votes
1answer
113 views
Solving discrete log in partially known group
Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,...
0
votes
4answers
89 views
Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is
$(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
4
votes
0answers
78 views
Use of randomness in an Elgamal like encryption
Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
1
vote
0answers
70 views
Security of BLS under additional information on the secret key
Question A
Is the BLS signature scheme still secure if an adversary in addition to the public key $ pk = g_2 \, sk \in \mathbb{G}_2 $ also obtains additional information on the private key $ sk $, ...
-1
votes
1answer
79 views
Find $F(2x)$ from $F(x) = a^x \bmod p$
Given $F(x) = a^x \bmod p$, where $a$ is a primitive root of $p$,
Is it possible to work out what $F(2x)$ or $F(3x)$, etc if you know
what $F(x)$ is but not $x$.
If you use $F(x)$ then $F(2x)$, etc ...
2
votes
1answer
76 views
Pedersen commitments, what happens if I choose $H$ such that $H = a\times G$?
For Pedersen commitments of the form $C = x\times G + r\times H$, what is the worst thing I can do if I already know $H$ such that $H = a\times G$ ?
For standard curves, there are specifications for ...
4
votes
1answer
165 views
Is there a group where CDH is easy but DLog is hard?
The question is quite simple:
Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?
Refresher on the problems:
CDH:...
0
votes
1answer
143 views
What math should I learn to get in depth with Elliptic Curve Cryptography research?
My background is computer scientist. I have done applied cryptography research for a while. Currently, I'm working on Elliptic curve cryptography.
To understand the idea and how to use Elliptic curve ...
0
votes
0answers
48 views
Discrete logarithm for a range
I previously asked this question on the math site but didn't get a response.
Are there any efficient algorithms for solving the following problem?
Let $b\leq m<n$, what is the smallest value for $...
1
vote
0answers
68 views
Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?
I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you.
"...
0
votes
1answer
75 views
Solving discret log problem
Can the discret log problem be solved when the modulus is a hard to factor composite number, i.e. when modulus $n=p*q$, where $p$ and $q$ are two large prime numbers?
-1
votes
1answer
85 views
Is this problem still as hard as discrete logarithm (modified ElGamal)?
I am trying to find a vulnerability or proof for the following problem:
ElGamal part.
Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate ...
2
votes
1answer
134 views
Understanding the Pohlig-Hellman algorithm
The paper has the following relation:
$$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$
where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation ...
4
votes
0answers
120 views
Zero knowledge proof for a discrete logarithm
Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows:
Pick $g$ as a random element from $Z_N^*$
Pick $x$ as a ...
4
votes
1answer
190 views
Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes
The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this ...
1
vote
1answer
57 views
Galois Field multiplication instead of Diffie Hellmans discrete logarithm
I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I ...
1
vote
1answer
67 views
Is this problem same as discrete logarithm?
Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds.
Take the problem given $g,g',h$ where $g^z\equiv h\...
3
votes
0answers
71 views
How many qbits are required to break Diffie-Hellman over a multiplicative group
There have been comparisons between RSA and ECDH with regards to the number of qbits (qubits) required to break the algorithm with a specific key size. But how many qbits are required to break "...
2
votes
2answers
657 views
How to solve this ECDLP?
The Problem is as follows:
$E: y^2=x^3+17230x+22699 \pmod{23981} $
$p=23981$ is prime number
point $G$
$G$'s order $109$ : prime number
Alice creates a public key by ...
-1
votes
1answer
90 views
Is that right what I understand about MOV attack?
There is an elliptic curve. $y^2 = x^3 +ax+b \pmod p$ ($p$ is prime number)
To solve DLP, need to find $r$ from given points $G$, $rG$. ($G$'s order is $q$ and $q$ is prime number)
The MOV attack ...
0
votes
1answer
68 views
If the order of g is a prime number, is Pollard-rho the best?
If the bit size is 128 bits, I know that BSGS is not possible due to memory issues.
I know that the complexity of Pollard-rho for 128 bits is 2^64.
and I know that it is not possible to do 2 ^ 64 ...
1
vote
1answer
68 views
Can I use Pollard'-Rho even when the order is not a Prime?
I am now solving the ECDL problem.
I want to use [discrete_log_rho] in SageMath, but I can not use it because ORDER is not a prime number.
Can I change it to a decimal number close to ORDER at my ...
-2
votes
1answer
52 views
Diffie Hellman Key Exchange Security wrt the hardness of discrete Logarithm
Hi I am very new to this field and I was wondering how one would prove or disprove the following statements:
1) if the DH key exchange protocol is secure for a finite cyclic group G, then computing ...
1
vote
1answer
63 views
Does knowledge of equal exponents decrease security?
Say I have a group $G$ with two different generators $g_1$ and $g_2$, where the discrete log from one to another is unknown.
Also, there are two public commitments $g_1^{r}$ and $g_2^{r}$, where it ...
2
votes
1answer
137 views
Finding missing bits mathematicaly in a DLP situation (full problem)
In a preparatory question we had to recover decimal digits $@$ of $r$ and $s$ given
$g=51234$, $h=90403$, $N=111649$, $r=3@497$, $s=276@3$,
with $r$ and $s$ the smallest positive solutions to $g^r\...
2
votes
1answer
101 views
Finding missing bits mathematicaly in a DLP situation
Here is a DLP exercice
$g = 51234,\; h = 90403 ,\; N = 311 \cdot 359 = 111649$.
Define $r$ as the smallest positive integer with $g^r \equiv h \pmod N$.
Define $s$ as the smallest positive integer ...
1
vote
1answer
107 views
BLS hash as a group element exponent?
In BLS short signatures paper, the authors describe a hash function $H\colon\ \{0, 1\}^∗ → G^∗$, where $G$ is a Gap-Diffie-Hellman group.
They present a structure where a standard hash is used on a ...
2
votes
0answers
73 views
Explanation of a proof of one of Shoup's lemmas
In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma:
Lemma 1 Let $p$ be prime and let $t \ge 1$. Let $F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \...
1
vote
1answer
39 views
Discrete Log with regard to a random base
Suppose DL is hard in $G=\langle g \rangle$. For a uniformly random group element $r \in G$ (suppose $r=g^a$), is it hard to find $s$ given $r^s$ and $r$? Does the computational assumption have a well ...
4
votes
1answer
106 views
Trouble understanding the correctness of this Zero-Knowledge proof of posession of a discrete log
I came across the following protocol for a "Zero-Knowledge Proof of a Discrete Logarithm" in Bruce Schneier's Applied Cryptography (second edition) book. I simply cannot prove to myself that this ...
0
votes
2answers
87 views
Specific discrete logarithm question
I came across a DL that I need to solve...
5^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587)
The modulus is a 124 bit ...
0
votes
1answer
124 views
Sigma protocol ZK-proof of a pair of pedersen commitments
Let's say you are using a $\Sigma$ protocol ZK proof to prove knowledge of $x_1, x_2$ so that $Y = g_1^{x_1}g_2^{x_2}$. Of course $g_1$, $g_2$ are generators within cyclic group G of prime order q, ...
