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.
538
questions
0
votes
1answer
57 views
Is the base equally well protected by the discrete logarithm problem as the exponent?
I'd like to ask if in case of modular exponentiation, reverse engineering the base would be equally difficult, when knowing the exponent as determining the exponent is hard when the base is provided? ...
2
votes
1answer
44 views
Solve DLOG using a probabilistic algorithm for DLOG lsb
Following the question Can I know from a Bitcoin public key if the private key is odd or even?
The answer there gives a simple algorithm for solving the Discrete Logarithm Problem when given an oracle ...
1
vote
1answer
70 views
Is $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ with $p$ prime (strongly) collision-free?
Let $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ for $g \in \mathbb{Z}_{p}^{*}$ where $p$ is prime. Is this function (strongly) collision-free meaning we cannot find ...
6
votes
1answer
592 views
Small error in security proof on the paper On the Multi-User Security of Short Schnorr Signatures with Preprocessing
I think I found a small error in the security proof Link end of page 37. It states that
$ \sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q +1)q/2+2}{p - (3q +2)^2 /4}$.
But shouldn't it be
$\...
3
votes
2answers
251 views
Time Complexity Of Solving DLog When g and P are known
This (https://en.m.wikipedia.org/wiki/Discrete_logarithm) Wikipedia article confuses me. If you have the equation a = g^n (mod P), and g, P and a are all known, then how does a brute force solving for ...
0
votes
1answer
53 views
What Is The Maximum Value For N In Discrete Logarithm Problems?
I have some code, which can crack a discrete logarithm problem in ~ O(0.5n) time. However, this only works if, in the following, N is less than P:
G^N (mod P). To be clear, my program can figure out ...
6
votes
1answer
155 views
Finding large devious primes
Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could ...
1
vote
0answers
56 views
Modifying discrete logarithm problem in Zp by selecting a subset of group elements
Let $g$ generator of cyclic group $Z_p$ of order $p-1$, where $g$ can generate all group elements $\alpha \in Z_p$ as $\alpha = g^x$mod$p$, $x \in (0..p-1)$, where the discrete logarithm problem is ...
0
votes
1answer
72 views
Solving a discrete log with BsGs
If we consider a group G with modulus p, order q with $p=2*q+1$, and generator $g=2$ ($ p$, $q$ huge prime numbers), is there a way to solve the discrete log problem $ g^x = y $ for a y given, using ...
4
votes
1answer
467 views
What's the main difference between the Schnorr identification scheme and its Smart-Card implementation?
This question arises because I couldn't find any official paper for the Schnorr identification scheme, but only for the Smart-Card implementation of it. Also, it seems that everyone, when talking ...
1
vote
1answer
91 views
Understanding Practical Differences Between ElGamal and Diffie-Hellman
I've been tasked with building a Web Assembly site that implements E2EE. I was thinking of using ElGamal Encryption to encrypt the message and Diffie-Hellman to establish the key. After doing further ...
1
vote
1answer
71 views
Discrete Logarithm in the generic group model is hard - Theorem by Shoup
In Shoups well-known paper Lower bounds for Discrete Logarithms and Related Problems he proves that the Discrete Logarithm Problem is hard in the generic group model (if group operation and inverse ...
0
votes
0answers
60 views
How to get a common coordinate from two different coordinates on Elliptic Curves? [duplicate]
I am trying to write a SageMath script that multiplies two coordinates on Elliptic Curves into one common coordinate.
SageMath Elliptic curves over finite fields ...
3
votes
1answer
299 views
problem with a discrete logarithm/cyclic groups example... can anyone clarify this concept for me?
I was watching this really short video about the discrete logarithm example: https://www.youtube.com/watch?v=SL7J8hPKEWY
and at 0:38 they show all the possible values that you can get if $p = 17$ and $...
0
votes
0answers
19 views
Group Signature by Camenisch and Stadler
Page 8, Paper: "Efficient Group Signature Schemes for Large Groups" by Camenisch and Stadler
(1)
I was trying to understand membership certificate part. I am have only basic knowledge of ...
2
votes
2answers
402 views
How is the difficulty of discrete logarithm problem related to elliptic curve cryptography?
By definition, the discrete logarithm problem is to solve the following congruence for $x$ and it is known that there are no efficient algorithm for that, in general.
$$\begin{align*}
b^x\equiv r&\...
1
vote
0answers
39 views
CDH in a group of square matrices
This paper says the CDH problem in a group of square matrices can be solved by a generalized Chinese remainder theorem. I wonder how this problem might be solved?
DH protocol in the cyclic group of ...
1
vote
1answer
106 views
How to find integer point of a ec curve in a given range?
I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a ...
0
votes
1answer
85 views
Setting up the discrete logarithm framework
The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
0
votes
1answer
32 views
Domain parameters in the Schnorr identification scheme
I have been recently studying the Schnorr identification scheme. The book Cryptography: Theory and Practice by Stinson and Paterson states the following about the domain parameters in the Schnorr ...
0
votes
1answer
29 views
Congruence in the Schnorr identification scheme
I have been looking at the Cryptography: Theory and Practice book by Stinson and Paterson and when I came to the Schnorr identification scheme, I read the sentence that goes something like this:
...
4
votes
1answer
99 views
Why does Index Calculus work?
I understand how the Index Calculus algorithm works - I know & understand the steps. I understand how the steps are derived. However, I am not able to figure out why it works.
I can understand why ...
0
votes
0answers
32 views
Does breaking CDH also break DLP? [duplicate]
Does breaking the computational Diffie-Hellman problem in a group also always break discrete logarithms in that group?
3
votes
0answers
198 views
Uniqueness and Schnorr signatures
I am trying to analyse a "uniqueness" game around Schnorr signatures. The game is described in $\textbf{B.}$ and I try to provide in $\textbf{1.}$ and $\textbf{2.}$ some incomplete answers ...
1
vote
1answer
89 views
How to choose the appropriate Smoothness Bound while using the Index Calculus method
While implementing the Quadratic Sieve, the textbooks give a rough formula for what Smoothness bound you should use in your Factor Base.
To factor a number N using the Quadratic Sieve, we can use the ...
3
votes
1answer
93 views
Why is an ephemeral key required to prove possession of a static private key in Key-Establishment Schemes
In the NIST 800-56A rev3 "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography" in section 5.6.2.2.3.2 "Recipient Obtains Assurance [of the ...
3
votes
2answers
349 views
Recognize whether two random values are raised to the same power
Alice selects two random numbers from a finite field $Z_p$ : $a$ and $b$.
Bob does one of the two following steps randomly (sometimes he does step 1; sometimes step 2):
He chooses a random number $r$ ...
0
votes
1answer
41 views
Equivalence between "Discrete Log Relation" and Discrete Log
I am trying to understand Bulletproofs and it uses the following assumption (Section 2.1):
Note: $\mathbb{G}$ is of prime order $p$.
My question is about the last sentence in the image -- I cannot ...
0
votes
1answer
82 views
Zero Knowledge Discrete Logarithm on Elliptic Curves
Can the Discrete Logarithm ZK be implemented on elliptic curves? It seems that such an implementation should look like the following:
$Y = \alpha G$
Random pick $v$
$t = vG$
$c = H(G, y, t)$
$r = v - ...
0
votes
2answers
56 views
Discrete Logarithm Fiat-Shamir Parameters Selection
According to Fiat–Shamir heuristic there are two parameters of the algorithm: big prime number $p$ and primitive root $g$. Thus several questions arise:
How big should the prime number $p$ be? How to ...
0
votes
1answer
50 views
Several Discrete Logarithm Zero Knowledge Proof
According to Wiki there is an approach for proving knowledge of $x$ such that $g^x = y$. How can I prove that I know $x_1, x_2$ such that $g^{x_1} = y_1, g^{x_2}=y_2$. Of course, I can make these ...
0
votes
0answers
77 views
The security level on BN254 and BLS381
Does BLS12-381 still provide 128bits security level?
How about BN12-254? 112bits? Is there any references about the security level on pairing?
4
votes
2answers
114 views
Large prime numbers in ECC and discrete logarithm
In elliptic curve cryptography using Diffie-Hellman protocol, we need to use large prime numbers.
So my question is what makes discrete logarithm hard to solve when we use large prime numbers.
I guess ...
2
votes
0answers
27 views
Can one prove that a particular public key is part of an aggregated (MuSig) public key?
The MuSig paper (2018) describes a Schnorr signature key aggregation scheme which lets a set of individual public keys to be merged into a single, "aggregated" public key.
In the protocol ...
1
vote
1answer
56 views
Linking Decisional Diffie-Hellman, Discrete Logarithm, and Knowledge of Exponent Assumptions
I'm curious about the relation between the Discrete Logarithm and Decisional Diffie-Hellman. Is it safe to have an assumption like the following to link the two?
Given uniformly and independently ...
1
vote
2answers
92 views
Different modulus in the exponent
Given two values $g^{a_1}, g^{a_2}$ where $a_1, a_2 \in \mathbb{Z}_q$ and $g$ is a generator of group $\mathbb{G}$ of order $q$. Discrete logarithm is assumed to be hard in $\mathbb{G}$.
Is there a ...
1
vote
0answers
50 views
Is there any 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
158 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\...
6
votes
2answers
608 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
106 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
67 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
95 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
51 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
88 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
275 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
82 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
187 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
84 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
153 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
66 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$...
