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.
491
questions
-1
votes
0answers
32 views
Is any of this new? or is it already well established knowledge? [closed]
I have done some research into the functions
a^floor(x) mod p
floor(x)^e mod n
and wanted to share my results and see if this is new to anyone?
Here is a pdf of it in a nice format (can be viewed ...
0
votes
0answers
32 views
Zero Knowledge Proof: Prove correct ElGamal encryption without leaking message
I know it is possible to prove zero knowledge that a given ElGamal ciphertext $(c,d)$ encrypts a plaintext belonging to some set ($\{0,1\}$ is frequently used for electronic voting applications).
Next ...
1
vote
1answer
38 views
ElGamal Encryption over a Subgroup
Say for instance we are encrypting over a subgroup of ($Z_{67}^*, \bmod 67$).
To perform a round of El Gamal's encryption scheme we should:
Choose a subgroup of ($Z_{67}^*, \bmod 67$), of prime order....
0
votes
1answer
58 views
Problem about complexity of Chinese remainder theorem
I have a question about CRT.
Assuming, that we have this system (S):
x=a0 mod n0
x=a1 mod n1
with N=n0*n1 and n0,n1 are two distinct prime numbers.
Then the complexity in terms of binary operation is ...
1
vote
0answers
42 views
Security of an ECDSA Adaptor Signature Implementation
I'm currently working on an implementation of ECDSA Adaptor Signatures, and part of the signature scheme calls for a NIZK proof to verify knowledge of exponent over two public keys that share a ...
0
votes
1answer
40 views
Is this an instance of a Diffie-Hellman problem?
Let $\mathbb{G}$ be a cyclic group of order $p$ with generator $g$, and let $m\in\mathbb{G}$.
Problem: Given $c=m.g^{k.a}$ and $v=g^a$, where $k,a \in \mathbb{Z}^*_p$, output $k$.
Is this an instance ...
2
votes
0answers
55 views
Is there any way to encrypt the path in between a small number of 3D positions?
Or more general: given two valid random cipher $c_0, c_1$ a function $D$ with
$$D(c_0,c_1) = (a,b,c)$$
should exist but hard to compute (for most cases). The result $(a,b,c)$ represents the path from $...
0
votes
0answers
49 views
Proof of knowledge of discrete log
Suppose that $P = pG = H(rK)G$, where $P$ is a point on an elliptic curve, $H$ is a hash function, $rK = kR$ is a shared secret between the party that knows $r$ and the party that knows $k$, and $G$ ...
2
votes
2answers
94 views
In which case number field sieve/index calculus is faster for solving discrete logarithm?
Given the normal discrete logarithm problem:
$$a = b^c \mod{P}$$
with prime $P$ and numbers $a,b,c$
For which kind of $P,b$ the NFS/IC algorithm is faster than Baby-Step/Giant-Step+ Pollard's Rho ($\...
1
vote
1answer
101 views
How does the security of Elliptic curve compare to normal discrete logarithm?
Intro:
EC are often compared with RSA but how about a more safe version of the discrete logarithm?
All 3 can be reduced to the problem:
$$b = g^a \mod{P}$$
In RSA $P$ is a product of two primes. To ...
1
vote
1answer
40 views
Clarification of Advantage vs Probability/Success of an Adversary
In cryptography, for a polynomial time-bounded adversary $\mathcal{A}$, given a scheme $\Pi$, the success or probability of succeeding $\mathcal{A}$ is the likelihood for $\mathcal{A}$ to break $\Pi$, ...
3
votes
0answers
82 views
How can the Number Field Sieve attack the discrete log in $\mathbb Z_p^*$ of DSA?
The Digital Signature Algorithm (DSA) uses $L$-bit prime $p$ and $N$-bit prime $q$ with $q| p-1$, i.e., $p = r\cdot q +1$ ( Schnorr group if $r>2$ and safe prime if $r=2$).
In a way, the security ...
1
vote
0answers
24 views
what is the probability for an adversary to find the new key after adding new entropy in a group where computational diffie hellman is hard?
Let's say I have an Elliptic curve group $E(\mathbb{F}_q)$ with base Point $G$ and large prime order $n$. Computational Diffie-Hellman is assumed to be hard in that group.
$H: \{0,1\}^*\rightarrow \{...
1
vote
0answers
32 views
How hard will it be to solve an equation in elliptic curve group/ cyclic group where Discrete Logarithm is hard?
Given an Elliptic curve group $E(\mathbb{F}_q)$ where the Discrete Logarithm Problem (DLP) is hard and a base point $G \in E(\mathbb{F}_q)$ with large prime order $n$, what will be the advantage of a ...
1
vote
0answers
77 views
Find solution to discrete logarithm equation
Task: Find $x$ with $3^{x}\equiv5\pmod p$, where
(a): $p-1=2\cdot 3\cdot 101$;
(b): $p-1=2\cdot 3\cdot 101\cdot 103\cdot 107^2$.
I found a solution using online calc., but is there anyway except (...
1
vote
0answers
36 views
How to reconstruct the static private key of a Diffie Hellman client, when I can freely choose A, g and p?
I am struggling with a Diffie Hellman crypto challenge based on a client that uses a static private key. My goal is to trick the client into revealing enough information to reconstruct the private key ...
1
vote
1answer
66 views
Does this describe an invalid key share attack?
I recently came across a mention of invalid key share attacks on this site. It is done with DH groups over $\mathbb{ℤ}_p$ :prime $p$, where $p = qh + 1$, where $q$ is the prime order of DH subgroup ...
1
vote
1answer
120 views
Modular equation system
I have $N=p\cdot q$ and the following system where I know $A,B,C,D, k$:
$$A = B \cdot q^k \pmod N$$
and
$$C = D \cdot p^k \pmod N$$
Is there an easy way to recover $p$ and $q$?
0
votes
1answer
80 views
Discrete logarithm with 2 solutions? A clarification request
I need some clarification on the discrete logarithm problem...
When a friend and I were solving for the discrete logarithm problem of 9 = 2 ^ x mod 11, we got two ...
0
votes
0answers
24 views
Does resuing pederson commitment preserve the hiding property?
Assume you have a pedersen commitment scheme where the commitment is:
$$\mathcal C_1 =C(m,r)=g^m\cdot h^r$$
with $g,h$ being public generators in a public group $(G,\cdot)$ in which the discrete ...
1
vote
0answers
35 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
72 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 ...
0
votes
0answers
76 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
111 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
58 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
72 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
77 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
35 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
86 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
294 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 ...
10
votes
2answers
803 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
79 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
95 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
84 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
123 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
33 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
91 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
187 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
38 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
21 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
81 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
28 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
61 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
194 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
197 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
51 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
110 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
70 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 ...
