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.
469
questions
1
vote
0answers
27 views
Question about hiding commitment scheme for integers
Given a generic group $\mathbb{G}$ of an unknown order (such as a $3000$-bit RSA group) and a randomly generated element $g \in \mathbb{G}$, is the commitment scheme $\mathrm{Com}(x)= g^x$ not ...
1
vote
1answer
59 views
Computing $g^y\bmod p$ from $g^{y^2}\bmod p$ if Diffie-Hellman is compromised?
Given generator $g$ of a multiplicative group mod a prime $p$ the Diffie Hellman problem is to find $$g^{xy}\bmod p$$ from $g^x\bmod p$ and $g^y\bmod p$. The best way to solve this is through discrete ...
-1
votes
0answers
32 views
Applications utilizing either $\mathsf{RSA}$ or Diffie-Hellman but not together
What are the applications which utilize
Only $\mathsf{RSA}$ but not Diffie-Hellman (applications which can be rendered useless by breaking $\mathsf{RSA}$ alone)?
Only Diffie-Hellman but not $\mathsf{...
0
votes
0answers
67 views
A card game (for mental poker or any other card game)
I thought of a way to produce trustless card game in a flexible way. One feature that I want is it should be flexible (It should work for any type of card game, though I indeed started it as a ...
1
vote
2answers
89 views
Question about the proof of the change of base formula for the discrete logarithm
I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent).
In the intruduction, the paper states:
Let $F_q$ be a finite field of order ...
1
vote
1answer
57 views
By what modulo calculations with discrete logarithms are performed?
For odd prime $p$, I have been given a group $\mathbb{Z}_p^*$ of all invertible elements from $\mathbb{Z}_p$. Basically, $\mathbb{Z}_p^* = \{1,2,\ldots , p-1 \}$. I also have $a$ and $b$, which are ...
0
votes
2answers
71 views
Show how an efficient algorithm for computing discrete logarithms with base a can be used to efficiently compute discrete logarithms with base b
I have an exercise that says the following:
Let $p$ be an odd prime, and let $a$ and $b$ be generators $\mathbb{Z}_p^*$. Suppose that we have an efficient algorithm $A$ for computing discrete ...
0
votes
1answer
64 views
Breaking Elgamal private key
I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than ...
0
votes
0answers
30 views
Is there a concept of Pedersen commitment “in the base”?
This question Can Elgamal be made additively homomorphic and how could it be used for E-voting?
says ElGamal can be made homomorphic over multiplication. So you can have $(g^r, h^r g^m)$ (i.e., ...
1
vote
0answers
75 views
Where is factoring if discrete logarithm is broken?
Assume given $g^X\equiv h\bmod p$ where $g$ is of order $\frac{\lambda(p)}2$ where $\lambda(p)$ is Carmichael Lambda function applied to prime $p$ (so $2$ is invertible in exponent) we can compute $X$ ...
5
votes
1answer
270 views
Why do the discriminant and primality of the group order of an elliptic curve affect security?
In a book about cryptography and elliptic curves, there was a mention that not all curves are secure, and a statement than in order to pick a secure curve the curve must satisfy 3 requirements.
The ...
0
votes
0answers
15 views
Is it hard to determine an automorphism when the mapped value by several compositions of the automorphism is given
Generalization of the Discrete logarithm problem to non-abelian groups is discussed by many authors. One of the generalizations is shown in MOR cryptosystem as in the below link, by considering the ...
11
votes
2answers
781 views
What is a “constant time” work around when dealing with the point at infinity for prime curves?
I've been working for some time, on designing a constant time solution for dealing with the "point at infinity" for prime curves. So, far I'm using the Standard Projective Coordinates for ...
3
votes
1answer
77 views
Why is this signature independent of the message?
Assume that we have the following signature scheme CL Signature:
Choose a cyclic group $G = \langle g \rangle$ of order $q$.
Uniformly and randomly choose two elements $x,y \in \mathbb{Z}_q$, and ...
0
votes
2answers
55 views
The Generator point and Mod P in ECDSA
I've been reading about The discrete logarithm problem as of recent and i decided to try it out on a small portion of numbers myself and i actually came to a mental gridlock after watching this Video....
2
votes
1answer
76 views
How does $g^{x^2} \bmod p$ help you find $x$?
I was thinking about the Diffie-Hellman key exchange. One fact that we seem to know is that given a group generator $g$, a prime $p$ and the expression $g^x \bmod p$ its believed to be hard to find $x$...
1
vote
1answer
112 views
Solving Diffie-Hellman vs DLP
I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP).
Obvisously solving the DLP (discrete log) is at least as hard as solving the DH ...
0
votes
0answers
32 views
Strong Diffie-Hellman Problem
While reading the following paper about the Strong Diffie-Hellman Problem, i got curious about ways to compute $ g^{x^{l}} $ for unknown $x$ in an elliptic curve, without first solving the discrete ...
4
votes
1answer
84 views
Are there any public-key encryption schemes based on DLog?
There are public-key encryption schemes based on many different mathematical hardness assumptions, like the hardness of Decisional Diffie-Hellman problem, the hardness of the Factoring problem, the ...
2
votes
1answer
185 views
Discrete Logarithm problem with selected order
If the order of group ($p$)selected by attacker then discrete logarithm is still hard?
0
votes
0answers
33 views
Zero knowledge proof of Paillier cryptosystem
I have read the paper recently and I am curious about part 3. According to part 3, Bob sends a zero-knowledge proof such that $c_B=b\times_{E}c_A+_E E_A(\beta')$. Then Alice should first decrypt the ...
0
votes
1answer
19 views
On the hardness of addition when the elements of a field is represented by the powers of generator and possible any existant scheme
We can represent elements of a finite field $F$ in various ways polynomial basis and normal basis. There is one other; generator-based representation and this is based on the fact that the ...
0
votes
1answer
72 views
Problem related to the discrete logarithm problem
Let $G$ be a generator of a cyclic group in which the discrete logarithm problem is hard and $x$ and $u$ be scalars of the group such that $X = xG$ and $U = uG$, respectively. We want to compute $J = ...
0
votes
0answers
27 views
What are the consequences of Diffie Hellman problem in P?
Computational Diffie Hellman problem wants to know $g^{ab}$ given $g^a$, $g^b$ and $g$ while the discrete logarithm problem wants to know $x$ from $g^x$ and $g$.
The latter resolvable in polynomial-...
1
vote
1answer
54 views
DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus
$g^{ab} \pmod{p} = B^a \pmod{p}$ where all variables are known except $a$. In this case, I have an equivalent value for $a'*b'$, but this is not the same as the real values of $a*b$ due to the modulus....
6
votes
0answers
162 views
RSA like trapdoor permutations in Discrete logarithm
In RSA, given only $(n,e)$, where $n =pq$ and $e$ is the public exponent, it is hard to find $p$ and $q$. It also seems hard to find $d$. So we came up the RSA conjecture that is RSA defines a ...
5
votes
2answers
156 views
Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?
In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
2
votes
1answer
47 views
Is matrix elliptic curve discrete logarithm problem quantum-safe?
I can't be the first one to think of this and there must be a reason nobody design cryptosystem off this problem.
Let's define MECC as matrix of elliptic curve points, and MI as matrix of non-negative ...
0
votes
1answer
97 views
Proof of (in)distinguishability based on DDH/CDH/DL
I am wondering whether or not it is known that the following problem is computationally infeasible while working in a group for which the DDH (or CDH or DL) assumption holds (as usual, g is a group ...
0
votes
0answers
43 views
Is that proved that breaking ECDSA as hard as solving ECDLP? [duplicate]
Is that proved that breaking ECDSA (Elliptic Curve Digital Signature Algorithm) as hard as solving ECDLP(Elliptic Curve Discrete Logarithm Problem)?
0
votes
1answer
68 views
May an adversary be fooled by a random-looking input that in reality is fixed?
I want to prove the EUF-CMA-security of a signature scheme. It is a variation on an established scheme, therefore I would ideally like to reduce the new-scheme-security to the old-scheme-security.
the ...
0
votes
0answers
80 views
Zero Knowledge Set Membership proof
ZK set membership:
I am trying to create my own zero knowledge set membership proof for a commitment to an element in the set for small sets. I am a beginner in such works, so can someone help me find ...
2
votes
1answer
87 views
Factoring kind of problem
Let's say we will choose some 256-bit random $b$ and we will find the smallest $d$ such that:
$\frac {2^{d}-1}{b} = s$
Now compute $z \equiv s \pmod{2^{128}}$. If I will give you only $z$ - is it ...
9
votes
1answer
165 views
Is the one-more discrete log problem hard in the Generic Group Model?
In the Generic Group Model (GGM), a concrete cyclic group of (known) order $n$ is replaced with an idealized version: a random encoding for group elements is chosen, and the adversary only gets access ...
14
votes
0answers
180 views
The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020
Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field
Computation of a 30 750-Bit Binary Field Discrete Logarithm, Robert Granger and Thorsten ...
2
votes
0answers
63 views
What is a formula of a twist?
With the curve secp256k1, the order of the twist is 3×197×1559×96769×146849×2587814237219×375925338294461779×101009178936527559588563023359
But I can't understand what is formula of this twist(twist ...
1
vote
1answer
200 views
Smart's attack for secp256k1 does not work
This is the Sage code that I use, and the results I get:
...
4
votes
1answer
169 views
Diffie-Hellman: difficulty of computing $g^{x^2}$ given $g^x$?
Hoepfuly a simple question.
Given a group where the CDH problem is hard, if the adversary sees a public key $g^x$, is it easy or hard for the adversary to compute $g^{x^2}$?
My intuition says it ...
1
vote
1answer
48 views
I want to know the hardness of computing a or b given $g^{b^{-1}}$ and ab in cyclic groups with large prime order
$G$ is a multiplicative cyclic group of a large prime order $p$ and $g$ is a generator of $G$
Theorem 1: Given $g^{b^{-1}}$ and $ab$, it's hard to compute $a$ or $b$, where $a$ and $b$ are randomly ...
1
vote
1answer
312 views
Pohlig Hellman and small subgroup attacks
While studying Curve25519 I read about the small subgroup attack in chapter 3. So far i know, that you need a point with a small subgroup to do such an attack. Curve25519 has a basepoint with prime ...
5
votes
1answer
244 views
Sage vs. Magma on DLP
Generally speaking, Magma is faster than Sage on several crypto-related computations, however, I have encountered a DLP instance where Sage is significantly faster than Magma.
Take the DLP over $GF(p)$...
11
votes
1answer
226 views
What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)
Assume that $G$ is any cyclic group where the discrete log problem is hard, such as the elliptic curve group. Let $g$ be some generator of $G$.
The problem is as follows:
Given $(g, g^x)$ for unknown $...
0
votes
1answer
155 views
Why discrete logarithm modulo composite moduli not popular and not defined in standards?
The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$.
The demerit of this approach seems ...
1
vote
0answers
66 views
Pohlig-Hellman on ECDLP over extension field $\mathbb{F_p}^6$
Suppose there is an elliptic curve $E$ in form $y^2=x^3+b$ defined over $\mathbb{F_p}$, where $p$ is large prime. #$E(\mathbb{F_p})$ is also a large prime but #$E(\mathbb{F_p})\ne p$. ECDLP on this ...
3
votes
1answer
117 views
Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?
The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group ...
0
votes
0answers
42 views
Computing discrete logarithms in the subgroup generated by 1 + N
When I read about DLP, I found that there are groups where the computation is easy. I found that it is known that computing discrete logarithms in the subgroup generated by 1 + N is easy. For example :...
0
votes
0answers
38 views
When will the random bit sequence start to repeat in pseudo random number generator
Let's say we have the Blum-Micali pseudorandom number generator.
from wikipedia:
Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ ...
4
votes
2answers
97 views
Can zksnark prove DLP?
Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?
3
votes
1answer
51 views
Mapping a value $g^x \bmod p$ to a small interval $[1…H]$
My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$.
Let's ...
0
votes
1answer
41 views
implications of shor's algorithm on $F_{2^m}$ elliptic curves and GHASH
The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security ...
