# 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
Filter by
Sorted by
Tagged with
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? ...
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 ...
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 ...
592 views

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 ...
402 views

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&\... 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 ... 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 ... 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... 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 ... 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: ... 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 ... 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? 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 ... 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 ... 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 ... 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 ... 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 ... 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 - ... 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 ... 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 ... 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? 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 ... 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 ... 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 ... 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 ... 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 ... 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\... 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 ... 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. 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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}}\...
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$...