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.
1
vote
0answers
6 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\...
2
votes
0answers
37 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
1answer
91 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 ...
0
votes
0answers
41 views
Compute discrete logarithm with prime modulus
Given a cyclic group $G=<g>$ with known order which is divisible by $3$.
How can we efficiently compute the discrete logarithm $x$ to base $g$ modulo $3$ of an arbitrary element $y=g^x\in G$?
...
-1
votes
1answer
53 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 ...
1
vote
1answer
36 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
46 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
32 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
60 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
121 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
91 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
73 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
65 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
33 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 ...
0
votes
1answer
55 views
Zero knowledge proof for a double discrete log
I would appreciate some help with the following:
Let $v = a^c$ and $c = g^s h^r$, where $g$ and $h$ are generators. Is there an "easy way" to prove knowledge of $a, c, s, r$ that satisfy the ...
3
votes
1answer
68 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
63 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
58 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, ...
0
votes
1answer
43 views
Describing Discrete Logarithm Assumption
I'd like to work out how exactly we should describe the discrete logarithm assumption (say, if we are writing a paper).
Consider this:
Let Gen be a group-generation algorithm on input $1^n$, which ...
3
votes
2answers
73 views
Discrete Logarithm in a specific group
I am considering a setting similar to the one of the Paillier cryptosystem, where we sample two distinct odd primes $p,q$, we set $n=pq$, we generate $a \leftarrow \mathbb{Z}_{n^2}^*$ and finally we ...
-2
votes
1answer
45 views
Breaking DDH assumption
DDH says that: $(g,g^a,g^b,g^c)$ should be indistinguishable from $(g,g^a,g^b,g^{ab})$ assuming $a,b,c\in Z_P$.
However, since $Z_p$ is finite and has $p-1$ elements, can we not just try $n^2$ ...
3
votes
0answers
90 views
Cryptographically Secure Elliptic Curve
What are the properties a cryptographically secure Elliptic Curve must have?
I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far:
A curve ...
2
votes
2answers
68 views
Number of bits specified in standards implementation?
Currently deployed RSA and discrete logarithm implementation uses $1024$ to $2048$ bits.
Hypothetically speaking if a crypto team produces a faster algorithm that moves current factoring and discrete ...
-1
votes
2answers
53 views
about DL hash function proof
$$h(m) = g^m(\bmod p)$$
where $p$ is a prime number, how can I prove that this is a one way function and collision free?
$$h(m) = g^m(\bmod n) $$
where $n=pq$ for two distinct primes $p,q$, how can I ...
0
votes
1answer
36 views
Discrete logarithm problem - Pohlig Hellman $GF(2^p)$
I would like to ask how to modify Pohlig Hellman algorithm if I need to work with polynomials $GF(2^{60})$ I know how this algorithm works with numbers, but I am not able to imagine how to do some ...
4
votes
1answer
163 views
Solving the discrete logarithm problem for a weak group
I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always ...
4
votes
3answers
546 views
How can there be insecure elliptic curves if the discrete logarithm problem is hard?
The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure ...
0
votes
1answer
138 views
Schnorr signature using discrete logarithm / problem with python implementation [closed]
For educational purposes (by purpose with small values for the prime order q), I tried to write a small Python implementation of the Schnorr signature described in the Wikipedia article https://en....
1
vote
1answer
25 views
DLP-based keyed one-way function
I am trying to understand if it possible to use DLP to build a keyed one-way function with the following properties:
$H_a(H_b(M)) = H_c(M)$, where $a$ and $b$ are the keys, and $c=a*b$
The output of ...
6
votes
1answer
132 views
Is Pohlig-Hellman Cipher the only option?
I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
0
votes
0answers
55 views
Information sharing using interactive zero-knowledge system
I am trying to build a system that would allow information sharing in a kind of zero-knowledge way. Here is the set up:
Let's say there is a trusted third party that has Alice's sensitive info M (e.g....
0
votes
1answer
34 views
Breaking a modified version of Diffie Hellmann Protocol
I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt ...
3
votes
1answer
117 views
How hard is the following q-Strong Diffie-Hellman problem?
From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard.
For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the ...
4
votes
1answer
52 views
Is a composition of computational hardness problems still hard?
It is well known that both $g^x$ and $x^2$ are computational hardness problems in certain rings. But I wonder if the composition of them is still hard?
Namely, given $(g, g^x, x^2)$ in a ring $Z_n$ ...
3
votes
1answer
80 views
Complexity of Discrete Logarithms in binary fields without special exponents or special structure
There has been recent work, due to Joux, Gologlu, Zumbragel and others which has developed efficient algorithms for discrete logarithms in small (and specifically binary) characteristics, where the ...
3
votes
1answer
76 views
Primitive root in a finite field
Wen-Her Yang and Shiuh-Pyng Shieh proposed two password authentication schemes by employing smart cards, one is timestamp-based and the other one is nonce-based. Their scheme consists of 3 phases: ...
0
votes
0answers
26 views
Looking for a HINT. Trying to prove that a generalized Pedersen commitment is computationally binding [duplicate]
Let $G$ be a finite cyclic group of prime order $q$ with generators $g,h_1,h_2,...,h_n$ whose discrete logs with respect to one another is not known. A generalized Pedersen commitment to messages $m_1,...
2
votes
2answers
203 views
Using Pedersen commitment for a vector
I'm reading Bootle/Groth. I'm trying to understand how they are committing to a vector using Pedersen commitment. Here's my understanding of Pedersen commitment in the context of this paper:
We have ...
2
votes
1answer
61 views
Malicious DH parameters without using composite numbers
I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite ...
3
votes
0answers
44 views
Does secure LWE implementation leak bit information?
We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
5
votes
1answer
86 views
Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?
Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$.
Is it possible to determine in polynomial time ...
1
vote
1answer
101 views
Elliptic curve representation
According to this page, Edward's curve point doubling can be represented in a different way by assuming $c=1$ and $d = r^2$.
It then says we can represent $x y$ as $Y Z$ satisfying $r\cdot y = \frac ...
2
votes
2answers
239 views
Schnorr identification protocol security proof
I read about security proof of Schnorr identification protocol against impersonation attack. For the sake of comprehensibility let me sum up the protocol: Given group $G$ with generator $g$. Verifier ...
9
votes
0answers
112 views
Fewest qubits required for the discrete logarithm problem and integer factorization
According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
0
votes
1answer
118 views
Why is calculating the discrete logarithm harder than calculating the public key?
A noob question, I know, but given n in range [0,q-1], and given an elliptic curve point P, we calculate the public key Q=nP. By doing so, we calculate P+P=2P, 2P+P = 3P, and so we get the values P,2P,...
3
votes
1answer
189 views
baby-step, giant-step vs Pollard-rho
I'm studying algorithms that solve the discrete logarithm problem over elliptic curve. Reading online, it seems that people use the bsgs algorithm when the order of the curve is "low" and P-rho when ...
1
vote
0answers
96 views
breaking DLOG with special prime
This question is not directly about cryptography, but I feel that it is most suitable for this site.
DLOG problem: Given a prime $p$, $g$ a multiplicative generator of $\mathbb{Z}_p^\star$ and an ...
3
votes
1answer
249 views
Why aren't there function based discrete log problems?
If discrete logarithm is based on the fact that finding $x$ for $a^x$ is difficult, wouldn't it be difficult to find $n$ such that if $f(x_1) = x_2$ then $f(x_2) = x_3 ... = x_n$ if $x$ is a generator ...
0
votes
1answer
64 views
CDH between two groups implies weakness of El-Gamal
Let $G$ a cyclic group of prime order $p$ with a generator $g$.
Let $H$ a cyclic group of prime order $p$ with a generator $h$.
Suppose that you have an algorithm $\mathcal{A}$ that given two ...
4
votes
2answers
138 views
Why are theoretical hash constructions based on the hardness of the discrete logarithm problem not really used in practice?
In an old 2010 Q&A at StackOverflow, Pornin states:
… a good hash function "should not" allow a property such as surjectivity to be actually proven.
This makes sense to me when looking at, for ...
