# 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.

575 questions
Filter by
Sorted by
Tagged with
1 vote
47 views

### Does a list of discrete log equations reveal information?

Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that ...
• 21
23 views

### The appropriate smoothness bound

My question roots from another question asked in the community since I do not have enough reputation points to comment on the answer, I was hoping I could ask it here. How was the individual asking ...
1 vote
46 views

• 79
293 views

### Security of equal discrete logs (over different bases)

I am trying to find a reduction for the following DLOG problem in generic groups. It is a simple generalization but I'm not finding any reference (the closest being the Chaum-Pedersen signature scheme ...
39 views

### Consider the DSA digital signature scheme. Does the intercepted message m||s||r contain all information about the signer’s private key?

Consider the DSA digital signature scheme. Does the intercepted message m||s||r contain all information about the signer’s private key? Please justify your answer carefully. Please note that the ...
81 views

### How to use the CADO-NFS to calculate DLP in GF(p^2)?

I have question regarding DLP in GF(p^m) I know we can use CADO-NFS to solve the DLP in GF(p). But what if we move into the GF(p^m) and are working with polynomials? Does the Cado tools can calculate ...
53 views

### If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances

I am trying to prove the following: Given an ensemble $\{p_n, g_n\}$ ($p_n$ is an $n$-bit prime and $g_n \in \mathbb{Z}^*_{p_n}$ is a generator), if $A$ is a deterministic polynomial time algorithm ...
• 189
47 views

### Schnorr signature | Schnorr Public Parameters

hello guys hope you are doing well :), i am trying to simulate the Schnorr Signature, but i have encountered some difficulties finding the generator, i have chosen a prime P of 1024bit and took a ...
52 views

### Discrete Logarithm Based algorithm

The private (secret) key in DL (discrete logarithm) based algorithms is uniformly selected from the group Zq*. This private key is then used to compute the public key. Could the opposite be done, for ...
• 15
62 views

### Historical key sizes for RSA and discrete log [closed]

What is the historical pattern for key size increases for rsa vs discrete log? What are the current and future projected sizes for these?
• 882
59 views

https://en.wikipedia.org/wiki/Paillier_cryptosystem Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily. If I were to select $g \in \mathbb{Z}_{n^2}^*$ ...
101 views

### ElGamal discrete logarithm method to send keys

In my criptography course I was given the following exercise: ElGamal proposed the following digital signature scheme using discrete logarithms over a field $\mathbb{F}_p$, where $p$ is a large prime. ...
• 133
71 views

• 247
1 vote
97 views

### How to find the extractor in the Knowledge-of-Exponent Assumption?

From Mihir Bellare's paper Let $q$ be a prime such that $2q +1$ is also prime, and let $g$ be a generator of the order $q$ subgroup of ${Z^∗}_{2q+1}$. Suppose we are given input $q$, $g$, $g^a$ and ...
• 1,637
1 vote
78 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 ...
• 461
1 vote
84 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,...
• 2,698
77 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? ...
• 37
114 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 ...
• 10.5k
1 vote
88 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 ...
• 121
608 views

476 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
161 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 ...
• 11
1 vote