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

68 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $\log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at ...
227 views

### Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
293 views

### Finding $x$ such that $g^x\bmod p<p/k$?

In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for ...
466 views

### Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
380 views

### How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time. ...
124 views

### Software timing attack using Kocher method

What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$? I'm working from this paper: Volker ...
195 views

### Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve ...
255 views

114 views

### Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
103 views

### How many qbits are required to break Diffie-Hellman over a multiplicative group

There have been comparisons between RSA and ECDH with regards to the number of qbits (qubits) required to break the algorithm with a specific key size. But how many qbits are required to break "...
91 views

### Implications of TLS-SRP client with improper N validation?

During development of a client side application of TLS-SRP, i noticed a bug that allows an attacker spoofing as the server to send custom, but non-arbitrary $N$ values, with the client accepting them. ...
925 views

### How does the Number Field Sieve find the target number for Diffie-Hellman?

I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by ...
56 views

### Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
147 views

### Are analog quantum computers a threat to RSA and DLP?

We already know that D-WAVE's "quantum computers" can't really run the Shor's algorithm, because the way they're built doesn't qualify them as universal quantum computers. Now researchers actually ...
51 views

59 views

### Does secure LWE implementation leak bit information?

We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
90 views

### Is the representation problem as hard as the discrete logarithm problem?

I found the assumtion that finding a representation in a cyclic Group G for a randomly chosen value y is as difficult as solving the DL problem. That assumption was without proof so I am not sure if ...
244 views

### Frey-Rück Attack (FR-Reduction) - Tate Pairing

I am trying to understand the Frey-Rück attack and found different ways of a possible implementation. Since I am not yet very familiar with the Tate-Lichtenbaum pairing and the theory of divisors I ...
138 views

73 views

### Recover secret $x$ when $c\equiv m^x \pmod p$ with public $p$ (modified)

Given an encryption system where $c\equiv m^x \pmod p$, $p$ is a known prime, 1. Is it possible to recover $x$ with a known plaintext attack? Given $(p,\text{factorization of }\varphi(p),m,c)$ 2. Is ...
184 views

### Cost of attack on DSA with attack on DLP

Are there any (recent) estimates of cost of attack on DSA by solving the discrete logarithm? I'm especially interested in attacks that use Pollard's rho algorithm. Are there any optimized ...
106 views

### Reliability of a single-pass deniable authentication protocol?

I look for one-pass deniable authentication protocol with a short message payload for my project and find a solution: ...
37 views

### Which groups are secure for DL-Problem?

I was wondering why some groups provide more security to cryptosystems relying on DL-Problem. It is not clear to me whether it is just due to the known attacks or if there are some other reasons. So ...
46 views

### MOV attack when $E(\mathbb{F}_q)$ is cyclic

Suppose $P\in E(\mathbb{F}_q)$ and $R=dP$. In the MOV attack, we compute $\alpha=e(P,T)$ and $\beta=e(R,T)$ and try to solve the discrete logarithm problem for $\alpha$ and $\beta$ in the finite ...
40 views

### Knowledge of discrete log is needed in the proof of Cramer-Shoup public key scheme?

In the proof of the Cramer-Shoup public key scheme , I understand that the adversary's view can be seen as equations such as $\log c = x_1 + w x_2, \log d = y_1 + w y_2$ and so on (equation 1 and 2 ...
63 views

### Elliptic curve discrete logarithm problem

I'd like to know what is the maximum bits of the finite field that we can solve the ECDLP in a "regular" computer in trivial time. Is there any recent data about this?
116 views

### How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?

Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element? In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....
### Breaking the discrete logarithm problem in subgroups of $G$
I need to find the discrete logarithm of 20 modulo 71 where the generator of the group is 7. I need to break the group $|G|=2 \times 5 \times 7$ in subgroups $|G_1|=2, |G_2|=5, |G_3|=7$. I am new to ...