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
1answer
66 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
587 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
246 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
51 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
53 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
68 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
465 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
85 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
297 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
398 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
102 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
98 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
196 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
87 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
89 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
348 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
81 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
76 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
112 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
54 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
155 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
574 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
66 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
50 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
87 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
272 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
148 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$...
1
vote
1answer
122 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
69 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 ...

1
2 3 4 5
11