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.
503
questions
0
votes
0answers
22 views
if they exist a relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption
We have DCRA and ECSQRT assumptions.
ECSQRT: Square roots in elliptic curve groups over Z/nZ
Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all ...
5
votes
1answer
92 views
Zero-Knowledge Proof of Equality between RSA Modulus and Prime Order Group
Assume there is an RSA public key $(e,n)$ such that factarization of $n$ is unknown to both prover and verifier parties. We also have a prime order group $G$ and a generator $g$ for the group. For $m\...
5
votes
2answers
461 views
Why are elliptic curves over binary fields used less than those over prime fields？
In practical applications, elliptic curves over $F_p$ seem to be more popular than those over $F_{2^n}$. Is it because operations over prime fields are faster than those over $F_{2^n}$ for the same ...
2
votes
1answer
80 views
Gap between DLog and CDH
Is there any concrete group in which one CDH is exponentially easier (even it's still hard) than DLog.
0
votes
1answer
57 views
Time complexity of DLP over Elliptic curve group
Consider NIST 192 elliptic curve group https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf. What is the time complexity
of discrete log problem of it? Is it Pollard $\rho$ ...
2
votes
2answers
90 views
Super basic questions to DLP and DH
This is a super basic cryptography and I don't get it. My professor only explained it to us on a very abstract level, which I just agreed to without questioning it.
The DLP says it is easy to ...
0
votes
0answers
29 views
The complexity of Pohlig-Hellman algorithm
The Wikipedia Pohlig Hellman algorithm says that the complexity of Pohlig-Hellman algorithm is
$$\displaystyle {\mathcal {O}}\left(\sum _{i}{e_{i}(\log n+{\sqrt {p_{i}}})}\right)$$
I understand that ...
0
votes
1answer
58 views
Pollard Rho pseudorandom function
In Pollard Rho's Algorithm, a function $f$ with pseudorandom properties is required. Through this property, the birthday paradox can be leveraged to find a collision. But not all functions are ...
2
votes
3answers
218 views
Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp
In the Pohlig-Hellman algorithm, we take a Discrete Log Problem (DLP) in a group & solve it in subgroups $p_1^{n_1}$, $p_2^{n_2}$, $p_3^{n_3}$ etc & then combine it with the Chinese Remainder ...
0
votes
0answers
67 views
Discrete logarithm problem and the chinese remainder theorem
Say that $G_q$ is a group of order $q = \Pi_{i=1}^{s} q_i$, where $log(q) = n$ and $q_i$ is an odd prime $\forall i$ such that $log(q_i) = O(log(n))$.
I'm tasked with arguing that $G_q$ is a cyclic ...
3
votes
2answers
143 views
Finding an elliptic curve of specific order
I wish to use elliptic curves for cryptographic operations like commitments etc. I see that most standard elliptic curves like $\operatorname{secp256k1, sect571r1}$ have a certain specific and fixed ...
4
votes
1answer
77 views
Security proof of schnorr identification scheme
I have studied the Schnorr identification scheme, and I came across the security proof.
My question is regarding the following:
$$\begin{align}
\text{Pr}\left[\text{DLog}_{\mathcal{A}',\mathcal{G}}\...
2
votes
1answer
82 views
How to factorize the group order in Pohlig-Hellman algorithm
The Pohlig-Hellman algorithm is for computing discrete logarithms in a group whose order is a smooth integer.
This algorithm requires the factorization of the group order. However we know that ...
2
votes
2answers
58 views
Independent parameters basis for torsion-groups in SIDH: Is the Weil-pairing necessary?
In the original SIDH paper by De Feo, Jao and Plût, the basis points $P_A$ and $Q_A$ are supposed to be independent points in $E(\mathbb{F}_{p^2})$ of order $\ell_A^{e_A}$ for some small prime $\ell_A$...
1
vote
1answer
91 views
Use the Index Calculus to solve for $19^x \equiv 205\pmod{337}$, using the factor base $B=\{2,3,5,7\}$
I'm supposed to use the following information to solve the question, but I don't know how.
$$\begin{align}
19^2 &\equiv 2^3 \times 3^1 \times 5^0 \times 7^0&\pmod{337}\\
19^5 &\equiv 2^5 \...
0
votes
2answers
48 views
Solution to Discrete Log as a Commitment
Is the solution to a discrete logarithm a reasonable commitment scheme?
By my analysis, the following scheme is a reasonable commitment scheme:
Let $p$ and $q$ be large primes such that $q∣(p−1)$, let ...
0
votes
1answer
49 views
Reduction to the discrete log problem
Let $G$ be a group of prime order $p$ and generator $g$.
Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, ...
0
votes
0answers
60 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
61 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....
1
vote
1answer
75 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
62 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
49 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
57 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
58 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
103 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
114 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
46 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
92 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
28 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
37 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
60 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
73 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
123 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
96 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
26 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
41 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
77 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
81 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
124 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
62 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
78 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 ...
-1
votes
1answer
98 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
52 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
99 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
342 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
20 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
828 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
83 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
127 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
101 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$...
