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.
539
questions
1
vote
1answer
62 views
Hardness of a variant of the CDH problem
Given $g$, a generator of a multiplicative group (over some finite field or elliptic curve), and the group elements $\left( g^x, g^a, g^b, g^c, g^{x(a+b)}, g^{x(b+c)} \right)$, is possible to ...
1
vote
1answer
72 views
Would discrete-log-based signing and encryption have been a better choice than RSA?
Diffie-Hellman can be used for key exchange, and can be used as part of an integrated encryption scheme ("DLIES"). Schnorr signatures are possible by relying only on the discrete-log problem,...
0
votes
1answer
75 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
60 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
77 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
602 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
256 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
55 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
164 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
59 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
75 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
468 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
105 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
75 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
61 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
309 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
457 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
52 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
118 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
97 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
103 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
33 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
206 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
95 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
98 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
352 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
85 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
59 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
56 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
95 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
133 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
35 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
60 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
96 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
53 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
186 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
663 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
112 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
72 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
98 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
57 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
92 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
292 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
213 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
85 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}}\...
