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

1
2 3 4 5
10